Finite capacity scheduling using job prioritization and machine selection

• US 7,904,192 B2
• Filed: 01/14/2004
• Issued: 03/08/2011
• Est. Priority Date: 01/14/2004
• Status: Expired due to Fees

• Current Assignee: Agency For Science Technology and Research (Government of Singapore)
• Original Assignee: Agency For Science Technology and Research (Government of Singapore)
• Inventors: Cai, Tianxiang, Zhu, Juping, Chua, Tay Jin, Yin, Xiaofeng
• Primary Examiner(s): Decady; Albert
• Assistant Examiner(s): Chang; Sunray R
• Application Number:
  US10/758,468
• Publication Number:
  US 20050154625A1
• Time in Patent Office: 2,610 Days
• Field of Search: 700/90, 700/99, 700/100, 700/101
• US Class Current: 700/100
• 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 computing device comprising:

a processor; and

persistent storage memory in communication with said processor storing processor readable instructions for directing said device to schedule a plurality of work orders, each work order of said plurality being defined by a plurality of operations to be scheduled at a plurality of work centers, each work center having a group of machines, each work center for performing an operation, the scheduling comprising, upon receiving a shop model indication comprising a job shop model and receiving an indication of a scheduling methodology comprising one of a forward scheduling methodology and a backward scheduling methodology;

(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, said attempting occurring after a successful previous scheduling of another operation of said highest priority candidate work order followed by a successful scheduling of an operation of different one of said work orders; and

(e) upon a failure of said attempting to schedule said operation, canceling the 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.

2. The computing device of claim 1 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.

3. The computing device of claim 2 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.

4. The computing device of claim 1 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.

5. The computing device of claim 4 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.

6. The computing device of claim 1 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.

7. The computing device of claim 1 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.

8. The computing device of claim 1 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.

9. The computing device of claim 8 wherein said suitability category is chosen from the set consisting of Must, Dedicated Preferred, Shared Preferred, No Preference, and Must Not.

10. The computing device of claim 9 wherein, if said categorizing has categorized any machine into the Must suitability category, said identifying identifies said machine as said best candidate machine.

11. The computing device of claim 9 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.

12. The computing device of claim 8 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.

13. The computing device of claim 1 wherein said set of job prioritization rules is work centre specific.

14. A computer readable medium containing computer-executable instructions which, when performed by a processor in a computing device, cause said computing device to schedule a plurality of work orders, each work order of said plurality defined by a plurality of operations to be scheduled at a plurality of work centers, each work center having a group of machines, each work center for performing an operation, the scheduling comprising, upon receiving a shop model indication comprising a job shop model and receiving an indication of a scheduling methodology comprising one of a forward scheduling methodology and a backward scheduling methodology:

(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;

(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, said attempting occurring after a successful previous scheduling of another operation of said highest priority candidate work order followed by a successful scheduling of an operation of different one of said work orders; and

(e) upon a failure of said attempting 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.