Finite capacity scheduling using job prioritization and machine selection

• US 20050154625A1
• Filed: 01/14/2004
• Published: 07/14/2005
• Est. Priority Date: 01/14/2004
• Status: Active Grant

• Current Assignee: Agency For Science Technology and Research
• Original Assignee: Agency For Science Technology and Research
• Inventors: Cai, Tianxiang, Zhu, Juping, Chua, Tay Jin, Yin, Xiaofeng
• Granted Patent: US 7,904,192 B2
• Time in Patent Office: Days
• US Class Current: 705/7
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

In a method, device, and computer-readable medium for finite capacity scheduling, heuristic rules are applied in two integrated stages: Job Prioritization and Machine Selection. During Job Prioritization (“JP”), jobs are prioritized based on a set of JP rules which are machine independent. During Machine Selection (“MS”), jobs are scheduled for execution at machines that are deemed to be best suited based on a set of MS rules. The two-stage approach allows scheduling goals to be achieved for performance measures relating to both jobs and machines. For example, machine utilization may be improved while product cycle time objectives are still met. Two user-configurable options, namely scheduling model (job shop or flow shop) and scheduling methodology (forward, backward, or bottleneck), govern the scheduling process. A memory may store a three-dimensional linked list data structure for use in scheduling work orders for execution at machines assigned to work centers.

Claims

1. A method of scheduling work orders defined by one or more operations at a plurality of work centers, each work center having a group of machines, each work center for performing an operation, the method comprising:

receiving a shop model indication comprising one of a job shop model and a flow shop model;

receiving an indication of a methodology comprising one of a forward scheduling methodology, a backward scheduling methodology, and a bottleneck scheduling methodology; and

scheduling operations of said work orders based on said receiving a shop model indication and said receiving an indication of a methodology.

2. The method of claim 1 wherein said receiving a shop model indication comprises receiving a job shop model and wherein said scheduling comprises:

(a) classifying each of said work orders as a candidate for scheduling at one of said work centers, said classifying resulting in one or more candidate work orders;

(b) assigning a priority to each of said candidate work orders based on a set of job prioritization rules;

(c) selecting a highest priority candidate work order having a priority that is at least as high as any priority assigned to any other candidate work order; and

(d) attempting to schedule an operation of said highest priority candidate work order at a machine of a work center at which said highest priority work order is a candidate based on a set of machine selection rules.

3. The method of claim 2 further comprising, if said attempting fails to schedule said operation, canceling any previously scheduled operation of said highest priority candidate work order and refraining from further attempting to schedule any other operation of said highest priority candidate work order.

4. The method of claim 2 wherein said indication of a methodology is an indication of a forward scheduling methodology and wherein said classifying classifies each of said work orders as a candidate for scheduling at the work center associated with its first operation.

5. The method of claim 4 further comprising, if said attempting succeeds in scheduling said operation for execution at said machine:

if said highest priority candidate work order has a successor operation;

reclassifying said highest priority candidate work order as a candidate for scheduling at the work center associated with said successor operation, said reclassifying resulting in a reclassified candidate work order; and

assigning a priority to said reclassified candidate work order based on said set of job prioritization rules.

6. The method of claim 2 wherein said indication of a methodology is an indication of a backward scheduling methodology and wherein said classifying classifies each of said work orders as a candidate for scheduling at the work center associated with its last operation.

7. The method of claim 6 further comprising, if said attempting succeeds in scheduling said operation at said machine,

if said highest priority candidate work order has a predecessor operation:

reclassifying said highest priority candidate work order as a candidate for scheduling at the work center associated with said predecessor operation, said reclassifying resulting in a reclassified candidate work order; and

assigning a priority to said reclassified candidate work order based on said set of job prioritization rules.

8. The method of claim 2 further comprising repeating (c) and (d) until no candidate work orders remain.

9. The method of claim 2 wherein said job prioritization rules are based on at least one of earliest due date, shortest processing time, and same family code as preceding work order.

10. The method of claim 2 wherein said job prioritization rules comprise a plurality of rules and wherein said assigning a priority comprises progressively applying said plurality of rules until a unique priority is assigned to each candidate work order.

11. The method of claim 2 wherein said attempting to schedule an operation of said highest priority candidate work order comprises:

categorizing the machines of the work center for performing said operation into suitability categories based on a determined suitability of each machine for completing said operation of said highest priority candidate work order;

for each suitability category, identifying a candidate machine of the machines in said suitability category based on said set of machine selection rules, said identifying resulting in one or more candidate machines;

identifying a best candidate machine from said one or more candidate machines based on said set of machine selection rules; and

scheduling said operation of the work order at said best candidate machine.

12. The method of claim 11 wherein said suitability category is chosen from the set consisting of Must, Dedicated Preferred, Shared Preferred, No Preference, and Must Not.

13. The method of claim 12 wherein, if said categorizing has categorized any machine into the Must suitability category, said identifying identifies said machine as said best candidate machine.

14. The method of claim 12 wherein, if said categorizing has categorized any machine into the Must Not suitability category, said identifying will not identify said machine as said best candidate machine.

15. The method of claim 11 wherein said machine selection rules are based on at least one of meeting a work order due date with maximum stock remaining, smallest loss time, smallest difference between actual and latest start time, and most balanced loading across machines.

16. The method of claim 1 wherein said receiving a shop model indication comprises receiving a flow shop model indicating that the operations of each work order follow a common sequence and wherein said scheduling comprises:

(a) selecting one of said work centers based on said common sequence, said selecting resulting in a selected work center;

(b) assigning a priority to each of said work orders having an operation associated with the selected work center based on said set of job prioritization rules;

(c) identifying a highest priority work order having an assigned priority that is at least as high as any priority assigned to any other work order at the selected work center; and

(d) attempting to schedule an operation of said highest priority work order at a machine of said selected work center.

17. The method of claim 16 further comprising, if said attempting fails to schedule said operation for execution at said machine, canceling any previously scheduled operation of said highest priority work order and deeming said highest priority work order ineligible for any further attempting to schedule at said plurality of machines.

18. The method of claim 17 wherein a work order that is not ineligible is eligible and further comprising repeating (c) and (d) until no eligible work orders with an unscheduled operation associated with the selected work center remain.

19. The method of claim 18 wherein said indication of a methodology is an indication of a forward scheduling methodology and wherein said selected work center is for performing a first operation in said common sequence.

20. The method of claim 19 further comprising, if at least one eligible work order having an unscheduled operation remains:

based on said common sequence, selecting the next work center for performing an unscheduled operation of an eligible work order, said selecting resulting in a new selected work center; and

assigning a priority to each eligible work order having an unscheduled operation associated with said selected work center based on said set of job prioritization rules.

21. The method of claim 20 further comprising repeating (c) and (d) until no eligible work orders remain with an unscheduled operation associated with the selected work center.

22. The method of claim 18 wherein said indication of a methodology is an indication of a backward scheduling methodology and wherein said selected work center is for performing a last operation in said common sequence.

23. The method of claim 22 further comprising, if at least one eligible work order having an unscheduled operation remains:

based on said common sequence, selecting the preceding work center for performing an unscheduled operation of an eligible work order, said selecting resulting in a new selected work center; and

assigning a priority to each eligible work order having an unscheduled operation associated with said selected work center based on said set of job prioritization rules.

24. The method of claim 23 further comprising repeating (c) and (d) until no eligible work orders remain with an unscheduled operation associated with the selected work center.

25. The method of claim 16 wherein said job prioritization rules are based on at least one of earliest due date, shortest processing time, and same family code as preceding work order.

26. The method of claim 16 wherein said attempting to schedule an operation of said highest priority work order comprises:

categorizing the machines of the selected work center for performing said operation into suitability categories based on a determined suitability of each machine for completing said operation of said highest priority work order;

for each suitability category, identifying a candidate machine of the machines in said suitability category based on a set of machine selection rules, said identifying resulting in one or more candidate machines;

identifying a best candidate machine from said one or more candidate machines based on said set of machine selection rules; and

scheduling said operation of the work order at said best candidate machine.

27. The method of claim 26 wherein said suitability category is chosen from the set consisting of Must, Dedicated Preferred, Shared Preferred, No Preference, and Must Not.

28. The method of claim 27 wherein, if said categorizing has categorized any machine into the Must suitability category, said identifying identifies said machine as said best candidate machine.

29. The method of claim 27 wherein, if said categorizing has categorized any machine into the Must Not suitability category, said identifying will not identify said machine as said best candidate machine.

30. The method of claim 26 wherein said machine selection rules are based on at least one of meeting a work order due date with maximum stock remaining, smallest loss time, smallest difference between actual and latest start time, and most balanced loading across machines.

31. The method of claim 2 wherein said set of job prioritization rules is work centre specific.

32. The method of claim 1 wherein said scheduling comprises assigning a priority to each work order of said work orders based on a set of job prioritization rules.

33. The method of claim 32 wherein said indication of a scheduling methodology is an indication of a forward scheduling methodology.

34. The method of claim 33 wherein said assigning a priority comprises, for each work order, determining an earliest start time at which each operation of the work order can be commenced.

35. The method of claim 34 wherein each work order specifies a number of units to be completed and wherein said determining an earliest start time for a first operation of a work order comprises:

computing a total processing time for executing all operations of the work order;

computing a total transit time for transporting all of the units of the work order between the operations of the work order;

computing a total maximum buffer stock time for producing a maximum permissible number of work-in-progress units between operations of the work order; and

setting said earliest start time to a due date of the work order less said total processing time, said total transit time, and said total maximum buffer stock time.

36. The method of claim 34 wherein each work order specifies a number of units to be completed and wherein no operation of any work order is capable of overlapped execution with a preceding or succeeding operation of the work order and wherein said determining an earliest start time comprises, for an operation succeeding the first operation of a work order:

determining an assigned end time at which an immediately preceding operation is scheduled to be completed;

determining a transit time for transporting the units of the work order from the immediately preceding operation to a current operation;

determining a minimum buffer stock time for producing a minimum permissible number of work-in-progress units between the immediately preceding operation and the current operation; and

setting said earliest start time to said assigned end time plus said transit time plus said minimum buffer stock time.

37. The method of claim 34 wherein each work order specifies a number of units to be completed and wherein each operation of a work order is capable of overlapped execution with a preceding or succeeding operation of the work order.

38. The method of claim 37 wherein said determining an earliest start time comprises, for an operation succeeding a first operation of the work order which has an equal or longer processing time than a processing time of an immediately preceding operation:

determining an assigned start time at which the immediately preceding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from the immediately preceding operation to a current operation;

determining a minimum buffer stock time for producing a minimum permissible number of work-in-progress units between the immediately preceding operation and the current operation; and

determining a unit run time for processing a single unit of the work order at the immediately preceding operation.

39. The method of claim 38 further comprising, if said processing time of said immediately preceding operation is greater than or equal to said minimum buffer stock time, setting said earliest start time to said assigned start time plus said transit time plus said minimum buffer stock time plus said unit run time.

40. The method of claim 38 further comprising, if said processing time of said immediately preceding operation is less than said minimum buffer stock time, setting said earliest start time to said assigned start time plus said transit time plus said processing time of said immediately preceding operation plus said unit run time.

41. The method of claim 37 wherein said determining an earliest start time comprises, for an operation succeeding a first operation of the work order which as a shorter processing time than a processing time of an immediately preceding operation:

determining an assigned start time at which the immediately preceding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from the immediately preceding operation to a current operation;

determining a minimum buffer stock time for producing a minimum permissible number of work-in-progress units between the immediately preceding operation and the current operation;

determining a unit run time for processing a single unit of the work order at the immediately preceding operation; and

determining a differential processing time consisting of the time required to process all units of the work order at the immediately preceding operation less the time required to process all units of the work order at the current operation.

42. The method of claim 41 further comprising, if said processing time of said immediately preceding operation is greater than or equal to said minimum buffer stock time, setting said earliest start time to said assigned start time plus said transit time plus said minimum buffer stock time plus said unit run time plus said differential processing time.

43. The method of claim 41 further comprising, if said processing time of said immediately preceding operation is less than said minimum buffer stock time, setting said earliest start time to said assigned start time plus said transit time plus said processing time of said immediately preceding operation plus said unit run time plus said differential processing time.

44. The method of claim 33 wherein said assigning a priority comprises, for each work order, determining a latest start time at which each operation of the work order can be commenced.

45. The method of claim 44 wherein each work order specifies a number of units to be completed and wherein said determining a latest start time for a first operation of a work order comprises:

computing a total processing time for executing all operations of the work order;

computing a total transit time for transporting all of the units of the work order between the operations of the work order;

computing a total minimum buffer stock time for producing a minimum permissible number of work-in-progress units between operations of the work order; and

setting said latest start time to a due date of the work order less said total processing time, said total transit time, and said total minimum buffer stock time.

46. The method of claim 44 wherein each work order specifies a number of units to be completed and wherein no operation of any work order is capable of overlapped execution with a preceding or succeeding operation of the work order and wherein said determining a latest start time comprises, for an operation succeeding the first operation of a work order:

determining an assigned end time at which an immediately preceding operation is scheduled to be completed;

determining a transit time for transporting the units of the work order from the immediately preceding operation to a current operation;

determining a maximum buffer stock time for producing a maximum permissible number of work-in-progress units between the immediately preceding operation and the current operation; and

setting said latest start time to said assigned end time plus said transit time plus said maximum buffer stock time.

47. The method of claim 44 wherein each work order specifies a number of units to be completed and wherein each operation of a work order is capable of overlapped execution with a preceding or succeeding operation of the work order.

48. The method of claim 47 wherein said determining a latest start time comprises, for an operation succeeding a first operation of the work order which has an equal or longer processing time than a processing time of an immediately preceding operation:

determining an assigned start time at which the immediately preceding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from the immediately preceding operation to a current operation;

determining a maximum buffer stock time for producing a maximum permissible number of work-in-progress units between the immediately preceding operation and the current operation;

determining a unit run time for processing a single unit of the work order at the immediately preceding operation; and

setting said latest start time to said assigned start time plus said transit time plus said maximum buffer stock time plus said unit run time.

49. The method of claim 47 wherein said determining a latest start time comprises, for an operation succeeding a first operation of the work order which has a shorter processing time than a processing time of an immediately preceding operation:

determining an assigned start time at which the immediately preceding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from the immediately preceding operation to a current operation;

determining a maximum buffer stock time for producing a maximum permissible number of work-in-progress units between the immediately preceding operation and the current operation;

determining a unit run time for processing a single unit of the work order at the immediately preceding operation;

determining a differential processing time consisting of the time required to process all units of the work order at the immediately preceding operation less the time required to process all units of the work order at the current operation; and

setting said latest start time to said assigned start time plus said transit time plus said maximum buffer stock time plus said unit run time plus said differential processing time.

50. The method of claim 32 wherein said indication of a scheduling methodology is an indication of a backward scheduling methodology.

51. The method of claim 50 wherein said assigning a priority comprises, for each work order, determining an earliest start time at which each operation of the work order can be commenced.

52. The method of claim 51 wherein each work order specifies a number of units to be completed and wherein no operation of any work order is capable of overlapped execution with a preceding or succeeding operation of the work order and wherein said determining an earliest start time comprises, for an operation preceding a last operation of a work order:

determining an assigned start time at which an immediately succeeding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from a current operation to the immediately succeeding operation;

determining a maximum buffer stock time for producing a maximum permissible number of work-in-progress units between the current operation and the immediately succeeding operation;

determining a current operation processing time required to process all units of the work order at the current operation of the work order; and

setting said earliest start time to said assigned start time less said transit time, said maximum buffer stock time and said current operation processing time.

53. The method of claim 51 wherein each work order specifies a number of units to be completed and wherein each operation of a work order is capable of overlapped execution with a preceding or succeeding operation of the work order.

54. The method of claim 53 wherein said determining an earliest start time comprises, for an operation preceding a last operation of the work order which has an equal or shorter processing time than a processing time of an immediately succeeding operation:

determining an assigned start time at which the immediately succeeding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from the current operation to the immediately succeeding operation;

determining a maximum buffer stock time for producing a maximum permissible number of work-in-progress units between the current operation and the immediately succeeding operation;

determining a unit run time for processing a single unit of the work order at the current operation; and

setting said earliest start time to said assigned start time less said transit time, said maximum buffer stock time and said unit run time.

55. The method of claim 53 wherein said determining an earliest start time comprises, for an operation preceding a last operation of the work order which has a longer processing time than a processing time of an immediately succeeding operation:

determining an assigned start time at which the immediately succeeding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from the current operation to the immediately succeeding operation;

determining a maximum buffer stock time for producing a maximum permissible number of work-in-progress units between the current operation and the immediately succeeding operation;

determining a unit run time for processing a single unit of the work order at the current operation;

determining a differential processing time consisting of the time required to process all units of the work order at the current operation less the time required to process all units of the work order at the immediately succeeding operation; and

setting said earliest start time to said assigned start time less said transit time, said maximum buffer stock time, said unit run time and said differential processing time.

56. The method of claim 50 wherein said assigning a priority comprises, for each work order, determining a latest start time at which each operation of the work order can be commenced.

57. The method of claim 56 wherein each work order specifies a number of units to be completed and wherein no operation of any work order is capable of overlapped execution with a preceding or succeeding operation of the work order and wherein said determining a latest start time comprises, for an operation preceding a last operation of a work order:

determining an assigned start time at which an immediately succeeding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from a current operation to the immediately succeeding operation;

determining a minimum buffer stock time for producing a minimum permissible number of work-in-progress units between the current operation and the immediately succeeding operation;

determining a current operation processing time required to process all units of the work order at the current operation of the work order; and

setting said latest start time to said assigned start time less said transit time, said minimum buffer stock time, and said current operation processing time.

58. The method of claim 56 wherein each work order specifies a number of units to be completed and wherein each operation of a work order is capable of overlapped execution with a preceding or succeeding operation of the work order.

59. The method of claim 58 wherein said determining a latest start time comprises, for an operation preceding a last operation of the work order which has an equal or shorter processing time than a processing time of an immediately succeeding operation:

determining an assigned start time at which the immediately succeeding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from the current operation to the immediately succeeding operation;

determining a minimum buffer stock time for producing a minimum permissible number of work-in-progress units between the current operation and the immediately succeeding operation; and

determining a unit run time for processing a single unit of the work order at the current operation.

60. The method of claim 59 further comprising, if the processing time of the current operation is greater than or equal to said minimum buffer stock time, setting said latest start time to said assigned start time less said transit time, said minimum buffer stock time and said unit run time.

61. The method of claim 59 further comprising, if the processing time of the current operation is less than said minimum buffer stock time, setting said latest start time to said assigned start time less said transit time, said processing time of said current operation and said unit run time.

62. The method of claim 58 wherein said determining a latest start time comprises, for an operation preceding a last operation of the work order which has a longer processing time than a processing time of an immediately succeeding operation:

determining an assigned start time at which the immediately succeeding operation is scheduled to be commenced;

determining a transit time for transporting the units of the work order from the current operation to the immediately succeeding operation;

determining a minimum buffer stock time for producing a minimum permissible number of work-in-progress units between the current operation and the immediately succeeding operation;

determining a unit run time for processing a single unit of the work order at the current operation; and

determining a differential processing time consisting of the time required to process all units of the work order at the current operation less the time required to process all units of the work order at the immediately succeeding operation.

63. The method of claim 62 further comprising, if the processing time of the current operation is greater than or equal to said minimum buffer stock time, setting said latest start time to said assigned start time less said transit time, said minimum buffer stock time, said unit run time and said differential processing time.

64. The method of claim 62 further comprising, if the processing time of the current operation is less than said minimum buffer stock time, setting said latest start time to said assigned start time less said transit time, said processing time of said current operation, said unit run time and said differential processing time.

65. The method of claim 1, wherein said indication of a methodology is an indication of a bottleneck scheduling methodology and wherein said scheduling comprises, for each work order:

classifying operations that are either a bottleneck operation or an operation succeeding said bottleneck operation into a first set of operations and classifying operations preceding said bottleneck operation into a second set of operations.

66. The method of claim 65 further comprising classifying each work order having an operation in said first set of operations into a first group of work orders and classifying each work order having an operation in said second set of operations into a second group of work orders.

67. The method of claim 66 wherein said receiving a shop model indication comprises receiving an indication of a job shop model for said first set of operations and wherein said scheduling further comprises:

(a) classifying each work order of said first group of work orders as a candidate for scheduling at a work center associated with said bottleneck operation, said classifying resulting in one or more candidate work orders;

(b) assigning a priority to each of said candidate work orders based on a set of job prioritization rules;

(c) selecting a highest priority candidate work order having a priority that is at least as high as any priority assigned to any other candidate work order; and

(d) attempting to schedule an operation of said highest priority candidate work order at a machine of a work center at which said highest priority work order is a candidate based on a set of machine selection rules.

68. The method of claim 67 further comprising, if said attempting succeeds in scheduling said operation for execution at said machine:

if the first set of operations of said highest priority candidate work order has a successor operation;

reclassifying said highest priority candidate work order as a candidate for scheduling at the work center associated with said successor operation, said reclassifying resulting in a reclassified candidate work order; and

assigning a priority to said reclassified candidate work order based on said set of job prioritization rules.

69. The method of claim 68 further comprising repeating (c) and (d) until no candidate work orders remain.

70. The method of claim 69 wherein said attempting to schedule an operation of said highest priority candidate work order comprises:

categorizing the machines of the work center for performing said operation into suitability categories based on a determined suitability of each machine for completing said operation of said highest priority candidate work order;

for each suitability category, identifying a candidate machine of the machines in said suitability category based on said set of machine selection rules, said identifying resulting in one or more candidate machines;

identifying a best candidate machine from said one or more candidate machines based on said set of machine selection rules; and

scheduling said operation of the work order at said best candidate machine.

71. The method of claim 70 wherein each work order specifies a number of units to be completed and wherein said scheduling further comprises, for each work order of said first group of work orders that is also in said second group of work orders and for which said attempting to schedule has successfully scheduled every operation in said first set of operations:

setting a due date for a last operation in said second group of operations of said work order to an assigned start time of said bottleneck operation plus a transit time for transporting the units of the work order from said latest operation to said bottleneck operation.

72. The method of claim 66 wherein said receiving a shop model indication comprises receiving an indication of a job shop model for said second set of operations and wherein said scheduling further comprises:

(a) classifying each work order of said second group of work orders as a candidate for scheduling at a work center associated with a last operation of the second set of operations of the work order, said classifying resulting in one or more candidate work orders;

(b) assigning a priority to each of said candidate work orders based a set of job prioritization rules;

(c) selecting a highest priority candidate work order having a priority that is at least as high as any priority assigned to any other candidate work order; and

(d) attempting to schedule an operation of said highest priority candidate work order at a machine of a work center at which said highest priority work order is a candidate based on a set of machine selection rules.

73. The method of claim 72 further comprising, if said attempting succeeds in scheduling said operation for execution at said machine:

if the second set of operations of said highest priority candidate work order has a predecessor operation;

reclassifying said highest priority candidate work order as a candidate for scheduling at the work center associated with said predecessor operation, said reclassifying resulting in a reclassified candidate work order; and

assigning a priority to said reclassified candidate work order based on said set of job prioritization rules.

74. The method of claim 73 further comprising repeating (c) and (d) until no candidate work orders remain.

75. The method of claim 66 wherein said receiving a shop model indication comprises receiving a flow shop model indicating that the operations in said first set of operations follow a common sequence and wherein said scheduling further comprises:

(a) selecting a work center associated with said bottleneck operation, said selecting resulting in a selected work center;

(b) assigning a priority to each work order of said first group of work orders having said bottleneck operation based on said set of job prioritization rules;

(c) identifying a highest priority work order having an assigned priority that is at least as high as any priority assigned to any other work order at the selected work center; and

(d) attempting to schedule an operation of said highest priority work order at a machine of said selected work center.

76. The method of claim 75 further comprising, if said attempting fails to schedule said operation for execution at said machine, canceling any previously scheduled operation of said highest priority work order and deeming said highest priority work order ineligible for any further attempting to schedule at said plurality of machines.

77. The method of claim 76 wherein a work order that is not ineligible is eligible and further comprising repeating (c) and (d) until no eligible work orders with an unscheduled operation associated with the selected work center remain in said first group of work orders.

78. The method of claim 77 further comprising, if at least one eligible work order having an unscheduled operation remains in said first group of work orders:

based on said common sequence, selecting the next work center for performing an unscheduled operation of an eligible work order of said first group of work orders, said selecting resulting in a new selected work center; and

assigning a priority to each eligible work order of said first group of work orders having an unscheduled operation associated with said selected work center based on said set of job prioritization rules.

79. The method of claim 78 further comprising repeating (c) and (d) until no eligible work orders remain in said first group of work orders having an unscheduled operation associated with the selected work center.

80. The method of claim 79 wherein said attempting to schedule an operation of said highest priority work order comprises:

categorizing the machines of the selected work center for performing said operation into suitability categories based on a determined suitability of each machine for completing said operation of said highest priority work order;

for each suitability category, identifying a candidate machine of the machines in said suitability category based on a set of machine selection rules, said identifying resulting in one or more candidate machines;

identifying a best candidate machine from said one or more candidate machines based on said set of machine selection rules; and

scheduling said operation of the work order at said best candidate machine.

81. The method of claim 80 wherein each work order specifies a number of units to be completed and wherein said scheduling further comprises, for each work order of said first group of work orders which is also in said second group of work orders and for which said attempting to schedule has successfully scheduled every operation in its first set of operations:

setting a due date for a last operation in said second group of operations of said work order to an assigned start time of said bottleneck operation plus a transit time for transporting the units of the work order from said latest operation to said bottleneck operation.

82. The method of claim 66 wherein said receiving a shop model indication comprises receiving a flow shop model indicating that the operations in said second set of operations follow a common sequence and wherein said scheduling further comprises:

(a) selecting a work center associated with a last operation of a work order from said second group of work orders, said selecting resulting in a selected work center;

(b) assigning a priority to each work order of said second group of work orders having an operation associated with the selected work center based on said set of job prioritization rules;

(c) identifying a highest priority work order having an assigned priority that is at least as high as any priority assigned to any other work order at the selected work center; and

(d) attempting to schedule an operation of said highest priority work order at a machine of said selected work center.

83. The method of claim 82 further comprising, if said attempting fails to schedule said operation for execution at said machine, canceling any previously scheduled operation of said highest priority work order and deeming said highest priority work order ineligible for any further attempting to schedule at said plurality of machines.

84. The method of claim 83 wherein a work order that is not ineligible is eligible and further comprising repeating (c) and (d) until no eligible work orders remain in said second group of work orders having an unscheduled operation associated with the selected work center.

85. The method of claim 84 further comprising, if at least one eligible work order remains in said second group of work orders having an unscheduled operation:

based on said common sequence, selecting the previous work center for performing an unscheduled operation of an eligible work order of said second group of work orders, said selecting resulting in a new selected work center; and

assigning a priority to each eligible work order of said second group of work orders having an unscheduled operation associated with said selected work center based on said set of job prioritization rules.

86. The method of claim 85 further comprising repeating (c) and (d) until no eligible work orders remain in said second group of work orders having an unscheduled operation associated with the selected work center.

87. The method of claim 66, wherein said scheduling further comprises, for each work order that is in both said first group and said second group of work orders:

determining a preceding operations cycle time for processing said first set of operations for said work order; and

for each operation in said second set of operations of said work order, determining an earliest start time at which said operation can be commenced, said earliest start time being offset from a beginning of a scheduling time window by at least said preceding operations cycle time.

88. The method of claim 87 wherein said scheduling further comprises, for each work order of said first group of work orders, scheduling the operations of said first set of operations at machines of said work centers.

89. The method of claim 88 wherein said scheduling further comprises, for the first operation of each work order of said first group of work orders:

determining an earliest start time at which said first operation can be commenced; and

determining a changeover time period for preparing a machine for processing said first operation.

90. The method of claim 89 wherein said scheduling further comprises, for each work order in said first group of work orders, if the machine at which said first operation of said work order is scheduled is available for processing said first operation during a time interval bounded by the beginning of the scheduling time window and the earliest start time of said first operation and if the changeover time period for preparing said machine for processing said first operation is greater than or equal to said time interval:

scheduling the preparing of said machine for processing said first operation to commence at the start of said scheduling time window; and

rescheduling said first operation to commence immediately after said preparing.

91. The method of claim 90 further comprising, for each work order, rescheduling the operations of said first set of operations which follow said first operation and the operations of said second set of operations on the basis of said rescheduling of said first operation.

92. The method of claim 89 wherein said scheduling further comprises, for each work order in said first group of work orders, if the machine at which said first operation of said work order is scheduled is available for processing said first operation during a time interval bounded by the beginning of the scheduling time window and the earliest start time of said first operation and if the changeover time period for preparing said machine for processing said first operation is less than said time interval:

scheduling the preparing of said machine for processing said first operation to complete at the earliest start time of said first operation; and

rescheduling said first operation to commence at the earliest start time of said first operation.

93. The method of claim 92 further comprising, for each work order, rescheduling the operations of said first set of operations which follow said first operation and the operations of said second set of operations on the basis of said rescheduling of said first operation.

94. The method of claim 1 wherein said indication of a methodology is an indication of bottleneck scheduling methodology and further comprising:

for each of said work orders having successor operations succeeding a bottleneck operation, scheduling said successor operations in sequential order; and

for each of said work orders having predecessor operations preceding said bottleneck operation, scheduling said predecessor operations in reverse sequential order.

95. A method of scheduling work orders defined by one or more operations at a plurality of work centers, each work center having a group of machines, each work center for performing an operation, the method comprising:

(a) classifying each of said work orders as a candidate for scheduling at one of said work centers, said classifying resulting in one or more candidate work orders;

(b) assigning a priority to each of said candidate work orders based on a set of job prioritization rules;

(c) selecting a highest priority candidate work order having a priority that is at least as high as any priority assigned to any other candidate work order; and

(d) attempting to schedule an operation of said highest priority candidate work order at a machine of a work center for which said highest priority work order is a candidate based on a set of machine selection rules.

96. A method of scheduling work orders at a plurality of work centers, each work order defined by operations following a common sequence, each work center having a group of machines, each work center for performing an operation, the method comprising:

(a) selecting one of said work centers based on said common sequence, said selecting resulting in a selected work center;

(b) assigning a priority to each of said work orders having an operation associated with the selected work center based on a set of job prioritization rules;

(c) identifying a highest priority work order having an assigned priority that is at least as high as any priority assigned to any other work order at the selected work center; and

(d) attempting to schedule an operation of said highest priority work order at a machine of said selected work center.

97. A computer readable medium containing computer-executable instructions which, when performed by a processor in a computing device, cause said computing device to:

receive a shop model indication comprising one of a job shop model and a flow shop model;

receive an indication of a methodology comprising one of a forward scheduling methodology, a backward scheduling methodology, and a bottleneck scheduling methodology; and

schedule operations of said work orders based on said receiving a shop model indication and said receiving an indication of a methodology.

98. A computer readable medium containing computer-executable instructions which, when performed by a processor in a computing device, cause said computing device to:

classify each of a set of work orders as a candidate for scheduling at one of a plurality of work centers to create a set of candidate work orders;

assign a priority to each of said candidate work orders based on a set of job prioritization rules;

select a highest priority candidate work order having a priority that is at least as high as any priority assigned to any other candidate work order; and

attempt to schedule an operation of said highest priority candidate work order at a machine of a work center for which said highest priority work order is a candidate based on a set of machine selection rules.

99. A computer readable medium containing computer-executable instructions which, when performed by a processor in a computing device, cause said computing device to:

select one of a plurality of work centers based on a sequence of operations common to a set of work orders to be scheduled, said selecting resulting in a selected work center;

assign a priority to each of said work orders of said set having an operation associated with the selected work center based on a set of job prioritization rules;

identify a highest priority work order having an assigned priority that is at least as high as any priority assigned to any other work order of said set at the selected work center; and

attempt to schedule an operation of said highest priority work order at a machine of said selected work center.

100. A computing device comprising a processor and persistent storage memory in communication with said processor storing processor readable instructions for directing said device to:

classify each of a set of work orders as a candidate for scheduling at one of a plurality of work centers to create a set of candidate work orders;

assign a priority to each of said candidate work orders based on a set of job prioritization rules;

select a highest priority candidate work order having a priority that is at least as high as any priority assigned to any other candidate work order; and

attempt to schedule an operation of said highest priority candidate work order at a machine of a work center for which said highest priority work order is a candidate based on a set of machine selection rules.

101. A computing device comprising a processor and persistent storage memory in communication with said processor storing processor readable instructions for directing said device to:

select one of a plurality of work centers based on a sequence of operations common to a set of work orders to be scheduled, said selecting resulting in a selected work center;

assign a priority to each of said work orders of said set having an operation associated with the selected work center based on a set of job prioritization rules;

identify a highest priority work order having an assigned priority that is at least as high as any priority assigned to any other work order of said set at the selected work center; and

attempt to schedule an operation of said highest priority work order at a machine of said selected work center.

102. A method of determining a job prioritization rule and a machine selection rule to be applied during scheduling of work orders, comprising:

receiving a scheduling criterion; and

mapping said scheduling criterion to said job prioritization rule and said machine selection rule.

103. A memory storing a three-dimensional linked list data structure for use in scheduling work orders for execution at machines assigned to work centers, comprising:

a first linked list having one or more work center nodes, each of said work center nodes being associated with a work center and having a second linked list of one or more machine nodes, each of said machine nodes being associated with a machine of said work center and having a third linked list of one or more time line nodes, each of said time line nodes representing a status of said machine during a time period.

104. The memory of claim 103 wherein said first, second and third linked lists are doubly linked.

105. The memory of claim 103 wherein said status is selected from the group consisting of meal break, preventive maintenance, machine downtime, manual adjustment, shutdown, machine trial run, pilot run and manual assignment, available, work order assignment, changeover time, running lot assignment, and unavailable.

106. The memory of claim 104 wherein said time line nodes are ordered based on said time period.