Job release with multiple constraints

• US 20050096770A1
• Filed: 11/01/2004
• Published: 05/05/2005
• Est. Priority Date: 10/30/2003
• Status: Active Grant

• Current Assignee: Agency For Science Technology and Research
• Original Assignee: Agency For Science Technology and Research
• Inventors: Chua, Tay Jin, Wang, Feng Yu, Cai, Tian Xiang, Liu, Ming Wei William
• Granted Patent: US 7,174,232 B2
• Time in Patent Office: Days
• US Class Current: 700/102
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/32258 Resource, machine assignment preferences, actual and anticipated load
• CPC Class Codes: G05B 2219/32269 Decision, of job release, select job to be launched next in shop
• CPC Class Codes: G05B 2219/32309 Shortest remaining capacity
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y02P 90/80 Management or planning

Abstract

To schedule the release of jobs from a pool of pending jobs, machine information and information about items to be processed are used to determine available machine capacity. Available machine capacity is allocated to jobs subject to multiple job release constraints. Allocation may be performed first for any pending jobs which were partially released during a previous time interval, and then to new jobs in decreasing order of determined job rank. If different operative constraints dictate different numbers of units of a job to be released, the minimum number of units meeting each constraint may be released. After the number of units to be released has been determined for a job, machine information is updated to account for available capacity consumed by the release of the selected number of units of the job. Updated information may be used for job release scheduling of the next job.

Claims

1. A method of scheduling the release of jobs from a pool of pending jobs, the method comprising:

selecting a job;

determining available machine capacity for said job based on job characteristics of said job and machine information including machine availability information about one or more machines capable of processing said job;

allocating at least some of said available machine capacity to said job subject to multiple job release constraints; and

updating said machine availability information to reflect said allocating.

2. The method of claim 1 further comprising:

repeating said selecting, said determining, said allocating and said updating until either said available capacity is exhausted or until said allocating has been performed for each of said pending jobs of said pool.

3. The method of claim 2 wherein said job characteristics include a specified number of items to be processed and wherein said machine information further includes an indication of a processing rate for each of one or more machines for processing said items.

4. The method of claim 3 wherein said job characteristics include characteristics of an item associated with said job.

5. The method of claim 3 wherein said available capacity is expressed as a number of units of said item capable of being processed during a time interval.

6. The method of claim 2 wherein said determining and said allocating is performed for a current time interval and wherein said selecting comprises, if said pending jobs include at least one job which has been partially released during a preceding time interval, selecting said at least one job before selecting a job which has not been fully or partially released as of the current time interval.

7. The method of claim 2 wherein said determining and said allocating is performed for a current time interval and wherein said selecting comprises, if said pending jobs include at least one job which has either been partially released during a preceding time interval or designated for full release during one or more preceding time intervals without yet being physically released, selecting said at least one job before selecting a job which has not been either partially released during a preceding time interval or designated for full release during one or more preceding time intervals without yet being physically released.

8. The method of claim 2 wherein said determining and said allocating is performed for a current time interval and further comprising ranking any pending jobs which have not been fully or partially released as of the current time interval, and wherein said selecting is performed in decreasing order of said ranking.

9. The method of claim 8 wherein said ranking is based on selected job ranking criteria.

10. The method of claim 9 wherein said job ranking criteria comprise primary job ranking criteria for grouping said jobs into categories and secondary job ranking criteria for ranking jobs within said categories.

11. The method of claim 9 wherein said job ranking criteria are selected from the group consisting of whether a committed customer forecast for processing a job has been specified, whether a job is expected to meet a desired shipment date or time, whether a job is expected to meet a desired loading date or time, a job priority, whether a master production schedule includes a job, a customer priority associated with a job, and either or both of a date and time on which a job is received.

12. The method of claim 3 wherein said job release constraints include a baseline capacity constraint specifying a maximum quantity of items to be released during a time interval for jobs whose characteristics match a specified set of member characteristics.

13. The method of claim 12 wherein said baseline capacity constraint specifies two or more sets of member characteristics, each of said sets of characteristics having an associated maximum quantity of items to be released during said time interval for jobs whose characteristics match said member characteristics.

14. The method of claim 13 wherein if the maximum quantity of items associated with a first one of said two or more sets of member characteristics differs from the maximum quantity of items associated with a second one of said two or more sets of member characteristics, the maximum quantity of items of a job which characteristics match both of said first and said second sets of member characteristics to be released during said time interval is deemed to be the lesser maximum quantity.

15. The method of claim 12 wherein said member characteristics are physical characteristics of the items to be processed.

16. The method of claim 1 wherein said machine information further includes a suitability of said one or more machines for processing said job and wherein said job release constraints include a machine preference constraint specifying that said allocating is further subject to said suitability.

17. The method of claim 16 wherein said job characteristics include a specified number of items to be processed and wherein said suitability of said machine comprises a preference of said one or more machines for processing said items.

18. The method of claim 16 wherein said suitability comprises a preference level selected from a range of preference levels.

19. The method of claim 18 wherein said allocating is performed for a machine having a high preference level for processing said job before it is performed for a machine having a low preference level for processing said job.

20. The method of claim 17 wherein each of said one or more machines requires a fixture to be capable of processing a job, wherein said machine information includes information about an available number of fixtures, wherein said job release constraints include a fixture capacity constraint indicating that the maximum quantity of items to be released during a time interval at a work center for said job is a maximum quantity of items capable of being processed during said time interval based on said available number of fixtures and the existence of machines having said available machine capacity that are capable of using said fixtures to process said job.

21. The method of claim 3 wherein said one or more machines comprise multiple machines grouped into a plurality of work centers, each of said work centers for performing a job processing operation, and wherein said job release constraints include a bottleneck capacity constraint indicating that, for said job, the maximum quantity of items to be released during a time interval at each work center is a smallest one of a maximum quantity of items capable of being processed during said time interval at any work center for performing a processing operation of said job.

22. The method of claim 2 wherein said job release constraints include a work-in-process (WIP) balancing constraint specifying an optimal WIP quantity for said job, and wherein said allocating is performed such that said optimal WIP quantity is not exceeded for said job.

23. The method of claim 2 wherein said optimal WIP quantity is cumulative for all job processing operations associated with said job.

24. The method of claim 2 wherein said one or more machines comprise multiple machines grouped into a plurality of work centers, each of said work centers for performing a job processing operation, and wherein said optimal WIP quantity is associated with one of said work centers.

25. The method of claim 3 wherein said job release constraints include a job-specific committed forecast constraint specifying a maximum number of items of said job to be processed during a time interval, said maximum number of items being based on an apportionment of the processing of a desired number of items over multiple time intervals.

26. The method of claim 2 wherein said method is for scheduling the release of jobs during a current time interval and wherein said job release constraints include a loading pattern constraint specifying a required degree of similarity between the characteristics of one or more jobs released for processing during an immediately preceding time interval and the characteristics of a job to be released during said current time interval.

27. The method of claim 26 wherein said loading pattern constraint specifies first and second required degrees of similarity between the characteristics of one or more jobs released for processing during an immediately preceding time interval and the characteristics of a job to be released during said current time interval, said first required degree of similarity being higher than said second required degree of similarity, and wherein said allocating comprises allocating said available machine capacity to a pending job having said first degree of similarity to one or more jobs released for processing during an immediately preceding time interval before allocating any of said available machine capacity to a pending job having said second degree of similarity to one or more jobs released for processing during an immediately preceding time interval.

28. The method of claim 26 wherein said characteristics of a job are physical characteristics of an item to be processed.

29. The method of claim 1 further comprising:

identifying a raw material necessary for processing said job; and

assessing an amount of said raw material in inventory, and wherein said allocating is performed only to the extent that said amount of raw material in inventory is sufficient to process said job.

30. The method of claim 6 further comprising:

determining a time interval during which said job is to be fully released or partially released with no remaining portion left to be released, said time interval being referred to as a processing start time interval; and

adding an expected processing duration for processing said job to said processing start time interval determine a committed finished goods time.

31. The method of claim 30 further comprising:

adding a shipment lead time to said committed finished goods time to determine a committed shipment time.

32. The method of claim 6 further comprising forecasting a time interval during which said job is to be fully released or partially released with no remaining portion left to be released, said time interval being referred to as a forecast processing start time interval, and wherein said determining available machine capacity for said job comprises reserving a portion of said available machine capacity, said reserving resulting in reserved machine capacity, and wherein said allocating allocates said reserved machine capacity to said job only if said forecast processing start date matches a current date.

33. The method of claim 3 wherein said job release constraints include two or more of:

a baseline capacity constraint specifying a maximum quantity of items to be released during a time interval for jobs whose characteristics match a specified set of member characteristics;

a machine preference constraint specifying that said allocating is further subject to a suitability of said one or more machines for processing said job;

a bottleneck capacity constraint indicating that, for said job, the maximum quantity of items to be released during a time interval at each of a plurality of work centers including one or more machines is a smallest one of a maximum quantity of items capable of being processed during said time interval at any work center for performing a processing operation of said job;

a work-in-process (WIP) balancing constraint specifying an optimal WIP quantity for said job, wherein said allocating is performed such that said optimal WIP quantity is not exceeded for said job;

a job-specific committed forecast constraint specifying a maximum number of items of said job to be processed during a time interval, said maximum number of items being based on an apportionment of the processing of a desired number of items over multiple time intervals; and

a loading pattern constraint specifying a required degree of similarity between the characteristics of one or more jobs released for processing during an immediately preceding time interval and the characteristics of a job to be released during a current time interval.

49. The machine-readable medium of claim 1 wherein said machine information further includes a suitability of said one or more machines for processing said job and wherein said job release constraints include a machine preference constraint specifying that said allocating is further subject to said suitability.

50. The machine-readable medium of claim 49 wherein said job characteristics include a specified number of items to be processed and wherein said suitability of said machine comprises a preference of said one or more machines for processing said items.

51. The machine-readable medium of claim 49 wherein said suitability comprises a preference level selected from a range of preference levels.

52. The machine-readable medium of claim 51 wherein said allocating is performed for a machine having a high preference level for processing said job before it is performed for a machine having a low preference level for processing said job.

53. The machine-readable medium of claim 50 wherein each of said one or more machines requires a fixture to be capable of processing a job, wherein said machine information includes information about an available number of fixtures, wherein said job release constraints include a fixture capacity constraint indicating that the maximum quantity of items to be released during a time interval at a work center for said job is a maximum quantity of items capable of being processed during said time interval based on said available number of fixtures and the existence of machines having said available machine capacity that are capable of using said fixtures to process said job.

34. A machine-readable medium including code for scheduling the release of jobs from a pool of pending jobs, comprising:

machine-executable code for selecting a job;

machine-executable code for determining available machine capacity for said job based on job characteristics of said job and machine information including machine availability information about one or more machines capable of processing said job;

machine-executable code for allocating at least some of said available machine capacity to said job subject to multiple job release constraints; and

machine-executable code for updating said machine availability information to reflect said allocating.

35. The machine-readable medium of claim 34 further comprising:

machine-executable code for repeating said selecting, said determining, said allocating and said updating until either said available capacity is exhausted or until said allocating has been performed for each of said pending jobs of said pool.

36. The machine-readable medium of claim 35 wherein said job characteristics include a specified number of items to be processed and wherein said machine information further includes an indication of a processing rate for each of one or more machines for processing said items.

37. The machine-readable medium of claim 35 wherein said job characteristics include characteristics of an item associated with said job.

38. The machine-readable medium of claim 36 wherein said available capacity is expressed as a number of units of said item capable of being processed during a time interval.

39. The machine-readable medium of claim 35 wherein said determining and said allocating are for a current time interval and wherein said selecting comprises, if said pending jobs include at least one job which has been partially released during a preceding time interval, selecting said at least one job before selecting a job which has not been fully or partially released as of the current time interval.

40. The machine-readable medium of claim 35 wherein said determining and said allocating are for a current time interval and wherein said selecting comprises, if said pending jobs include at least one job which has either been partially released during a preceding time interval or designated for full release during one or more preceding time intervals without yet being physically released, selecting said at least one job before selecting a job which has not been either partially released during a preceding time interval or designated for full release during one or more preceding time intervals without yet being physically released.

41. The machine-readable medium of claim 35 wherein said determining and said allocating are for a current time interval and further comprising machine-executable code for ranking any pending jobs which have not been fully or partially released as of the current time interval, and wherein said selecting is performed in decreasing order of said ranking.

42. The machine-readable medium of claim 41 wherein said ranking is based on selected job ranking criteria.

43. The machine-readable medium of claim 42 wherein said job ranking criteria comprise primary job ranking criteria for grouping said jobs into categories and secondary job ranking criteria for ranking jobs within said categories.

44. The machine-readable medium of claim 42 wherein said job ranking criteria are selected from the group consisting of whether a committed customer forecast for processing a job has been specified, whether a job is expected to meet a desired shipment date or time, whether a job is expected to meet a desired loading date or time, a job priority, whether a master production schedule includes a job, a customer priority associated with a job, and either or both of a date and time on which a job is received.

45. The machine-readable medium of claim 35 wherein said job release constraints include a baseline capacity constraint specifying a maximum quantity of items to be released during a time interval for jobs whose characteristics match a specified set of member characteristics.

46. The machine-readable medium of claim 45 wherein said baseline capacity constraint specifies two or more sets of member characteristics, each of said sets of characteristics having an associated maximum quantity of items to be released during said time interval for jobs whose characteristics match said member characteristics.

47. The machine-readable medium of claim 46 wherein if the maximum quantity of items associated with a first one of said two or more sets of member characteristics differs from the maximum quantity of items associated with a second one of said two or more sets of member characteristics, the maximum quantity of items of a job which characteristics match both of said first and said second sets of member characteristics to be released during said time interval is deemed to be the lesser maximum quantity.

48. The machine-readable medium of claim 45 wherein said member characteristics are physical characteristics of the items to be processed.

54. The machine-readable medium of claim 35 wherein said one or more machines comprise multiple machines grouped into a plurality of work centers, each of said work centers for performing a job processing operation, and wherein said job release constraints include a bottleneck capacity constraint indicating that, for said job, the maximum quantity of items to be released during a time interval at each work center is a smallest one of a maximum quantity of items capable of being processed during said time interval at any work center for performing a processing operation of said job.

55. The machine-readable medium of claim 35 wherein said job release constraints include a work-in-process (WIP) balancing constraint specifying an optimal WIP quantity for said job, and wherein said allocating is performed such that said optimal WIP quantity is not exceeded for said job.

56. The machine-readable medium of claim 35 wherein said optimal WIP quantity is cumulative for all job processing operations associated with said job.

57. The machine-readable medium of claim 35 wherein said one or more machines comprise multiple machines grouped into a plurality of work centers, each of said work centers for performing a job processing operation, and wherein said optimal WIP quantity is associated with one of said work centers.

58. The machine-readable medium of claim 36 wherein said job release constraints include a job-specific committed forecast constraint specifying a maximum number of items of said job to be processed during a time interval, said maximum number of items being based on an apportionment of the processing of a desired number of items over multiple time intervals.

59. The machine-readable medium of claim 35 wherein said code for scheduling the release of jobs is code for scheduling the release of jobs during a current time interval and wherein said job release constraints include a loading pattern constraint specifying a required degree of similarity between the characteristics of one or more jobs released for processing during an immediately preceding time interval and the characteristics of a job to be released during said current time interval.

60. The machine-readable medium of claim 59 wherein said loading pattern constraint specifies first and second required degrees of similarity between the characteristics of one or more jobs released for processing during an immediately preceding time interval and the characteristics of a job to be released during said current time interval, said first required degree of similarity being higher than said second required degree of similarity, and wherein said allocating comprises allocating said available machine capacity to a pending job having said first degree of similarity to one or more jobs released for processing during an immediately preceding time interval before allocating any of said available machine capacity to a pending job having said second degree of similarity to one or more jobs released for processing during an immediately preceding time interval.

61. The machine-readable medium of claim 59 wherein said characteristics of a job are physical characteristics of an item to be processed.

62. The machine-readable medium of claim 34 further comprising:

machine-executable code for identifying a raw material necessary for processing said job; and

machine-executable code for assessing an amount of said raw material in inventory, and wherein said allocating is performed only to the extent that said amount of raw material in inventory is sufficient to process said job.

63. The machine-readable medium of claim 39 further comprising:

machine-executable code for determining a time interval during which said job is to be fully released or partially released with no remaining portion left to be released, said time interval being referred to as a processing start time interval; and

machine-executable code for adding an expected processing duration for processing said job to said processing start time interval determine a committed finished goods time.

64. The machine-readable medium of claim 63 further comprising:

machine-executable code for adding a shipment lead time to said committed finished goods time to determine a committed shipment time.

65. The machine-readable medium of claim 39 further comprising machine-executable code for forecasting a time interval during which said job is to be fully released or partially released with no remaining portion left to be released, said time interval being referred to as a forecast processing start time interval, and wherein said determining available machine capacity for said job comprises reserving a portion of said available machine capacity, said reserving resulting in reserved machine capacity, and wherein said allocating allocates said reserved machine capacity to said job only if said forecast processing start date matches a current date.

66. The machine-readable medium of claim 36 wherein said job release constraints include two or more of:

a baseline capacity constraint specifying a maximum quantity of items to be released during a time interval for jobs whose characteristics match a specified set of member characteristics;

a machine preference constraint specifying that said allocating is further subject to a suitability of said one or more machines for processing said job;

a bottleneck capacity constraint indicating that, for said job, the maximum quantity of items to be released during a time interval at each of a plurality of work centers including one or more machines is a smallest one of a maximum quantity of items capable of being processed during said time interval at any work center for performing a processing operation of said job;

a work-in-process (WIP) balancing constraint specifying an optimal WIP quantity for said job, wherein said allocating is performed such that said optimal WIP quantity is not exceeded for said job;

a job-specific committed forecast constraint specifying a maximum number of items of said job to be processed during a time interval, said maximum number of items being based on an apportionment of the processing of a desired number of items over multiple time intervals; and

a loading pattern constraint specifying a required degree of similarity between the characteristics of one or more jobs released for processing during an immediately preceding time interval and the characteristics of a job to be released during a current time interval.

67. A computing device comprising a processor and persistent storage memory in communication with said processor storing machine-readable code for directing said device to schedule the release of jobs from a pool of pending jobs, comprising:

means for selecting a job;

means for determining available machine capacity for said job based on job characteristics of said job and machine information including machine availability information about one or more machines capable of processing said job;

means for allocating at least some of said available machine capacity to said job subject to multiple job release constraints; and

means for updating said machine availability information to reflect said allocating.

68. The computing device of claim 67 wherein said job release constraints include two or more of:

a baseline capacity constraint specifying a maximum quantity of items to be released during a time interval for jobs whose characteristics match a specified set of member characteristics;

a machine preference constraint specifying that said allocating is further subject to a suitability of said one or more machines for processing said job;

a bottleneck capacity constraint indicating that, for said job, the maximum quantity of items to be released during a time interval at each of a plurality of work centers including one or more machines is a smallest one of a maximum quantity of items capable of being processed during said time interval at any work center for performing a processing operation of said job;

a work-in-process (WIP) balancing constraint specifying an optimal WIP quantity for said job, wherein said allocating is performed such that said optimal WIP quantity is not exceeded for said job;

a job-specific committed forecast constraint specifying a maximum number of items of said job to be processed during a time interval, said maximum number of items being based on an apportionment of the processing of a desired number of items over multiple time intervals; and

a loading pattern constraint specifying a required degree of similarity between the characteristics of one or more jobs released for processing during an immediately preceding time interval and the characteristics of a job to be released during a current time interval.