US 4,896,269 AGranted

Job shop scheduling and production method and apparatus

AssigneeGeneral Electric Company

InventorDavid W. Tong

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for the efficient scheduling of a first plurality of jobs and the performance of the jobs on a second plurality of processing machines uses various heuristic rules in order to meet scheduling objectives. Initially, each job is scheduled on the machines without regard to the scheduling of any other job. Job scheduling conflicts are then identified and a priority index for each conflict is computed. For each job step involved in the highest priority conflict, a flexibility index is computed. Based on the flexibility index, the highest priority conflict is resolved by relaxing one or more steps of one or more jobs. If the conflicts have not been resolved at this stage, control returns to the step of identification of all remaining job scheduling conflicts. Upon resolution of all conflicts, an overall schedule of all jobs on all machines may be displayed. Additionally, the jobs are then performed on the machines based upon the final, conflict free schedule.

Claims16

Dependent claims

A method for performing a first plurality of production jobs on a second plurality of machines, each said job comprising a sequence of job steps to be respectively performed in a predetermined sequence on said machines, each said job step having a predetermined performance duration, each said job having a total processing time that is the sum of the performance durations of its respective steps and a due time measured relative to an arbitrary schedule start time, said method comprising the steps of:

(a) initially scheduling each said job for performance on said machines without regard to the scheduling of any other ones of said jobs, the initial scheduling for each said job being the tightest possible schedule for that job;
(b) identifying all job scheduling conflicts, each said conflict being the scheduling of more than one said job step on the same machine at the same time;
(c) computing a priority index for each said conflict in accordance with the equation:
PI=PRP.times.MDF.times.PSL
where:
PI=conflict priority index;
PRP=product of the job process time/job due time ratios of the jobs in said conflict;
MDF=demand factor of the machine on which said conflict occurs;
PSL=sum of the performance durations of the job steps constituting said conflict;
(d) selecting a highest priority conflict having the largest computed priority index;
(e) computing, for each job step constituting said highest priority conflict, a flexibility index in accordance with the equation:
FI=ST-SF
where:
FI=job step flexibility index;
ST=job slack time;
SF=job shift factor;
(f) holding fixed in time in said schedule within said highest priority conflict the job step having the lowest computed flexibility index while relaxing in time each remaining job step in said highest priority conflict until that conflict is resolved;
(g) relaxing, for each said job a step of which was relaxed to resolve said highest priority conflict, the steps succeeding the relaxed step only to the extent necessary to assure the steps of said job remain in said predetermined sequence;
(h) returning to step (b) if there remain any scheduling conflicts;
(i) providing a final, conflict free schedule for the performance of said first plurality of jobs on said second plurality of machines;
and
(j) performing said first plurality of production jobs on said second plurality of machines based on said final, conflict free schedule.

19 more elements

A method of production using digital computing apparatus to prepare a job schedule for each of a first plurality of production jobs on a second plurality of machines, each said job comprising a sequence of job steps to be respectively performed in a predetermined sequence on said machines, each said job step having a predetermined performance duration, each said job having a total processing time that is the sum of the performance durations of its respective steps and a due time measured relative to an arbitrary schedule start time, said method comprising the steps of:

(a) inputting to said computing apparatus as data for each said job:
(i) the sequence of steps associated therewith;
(ii) the identity of the machine on which each said job step is to be performed;
(iii) the performance duration of each said job step;
and
(iv) the due time
(b) operating said digital computing apparatus to perform the steps of:
initially scheduling each said job for performance on said machines without regard to the scheduling of any other ones of said jobs, the initial scheduling for each said job being the tightest possible schedule for that job;
identifying all job scheduling conflicts, each said conflict being the scheduling of more than one said job step on the same machine at the same time;
computing a priority index for each said conflict in accordance with the equation:
PI=PRP.times.MDF.times.PSL
where:
PI=conflict priority index;
PRP=product of the job process time/job due time ratios of the jobs in said conflict;
MDF=demand factor of the machine on which said conflict occurs;
PSL=sum of the performance durations of the job steps constituting said conflict;
selecting a highest priority conflict having the largest computed priority index;
computing, for each job step constituting said highest priority conflict, a flexibility index in accordance with the equation:
FI=ST-SF
where:
FI=job step flexibility index;
ST=job slack time;
SF=job shift factor;
holding fixed in time in said schedule within said highest priority conflict the job step having the lowest computed flexibility index while relaxing in time each remaining job step in said highest priority conflict until that conflict is resolved;
relaxing, for each said job a step of which was relaxed to resolve said highest priority conflict, the steps succeeding the relaxed step only to the extent necessary to assure the steps of said job remain in said predetermined sequence;
returning to the scheduling conflicts identifying step if there remain any scheduling conflicts;
and
providing a representation of a final, conflict free schedule for the performance of said first plurality of jobs on said second plurality of machines;
and
(c) performing said first plurality of production jobs on said second plurality of machines based on said final, conflict free schedule.

27 more elements

Apparatus for performing a first plurality of production jobs on a second plurality of machines, each said job comprising a sequence of job steps to be respectively performed in a predetermined sequence on said machines, each said job step having a predetermined performance duration, each said job having a total processing time that is the sum of the performance durations of its respective steps and a due time measured relative to an arbitrary schedule start time, said apparatus comprising:

means for initially scheduling each said job for performance on said machines without regard to the scheduling of any other ones of said jobs, the initial scheduling for each said job being the tightest possible schedule for that job;
means for identifying all job scheduling conflicts, each said conflict being the scheduling of more than one said job step on the same machine at the same time;
means for computing a priority index for each said conflict in accordance with the equation:
PI=PRP.times.MDF.times.PSL
where:
PI=conflict priority index;
PRP=product of the job process time/job due time ratios of the jobs in said conflict;
MDF=demand factor of the machine on which said conflict occurs;
PSL=sum of the performance durations of the job steps constituting said conflict;
means for selecting a highest priority conflict having the largest computed priority index;
means for computing, for each job step constituting said highest priority conflict, a flexibility index in accordance with the equation:
FI=ST-SF
where:
FI=job step flexibility index;
ST=job slack time;
SF=job shift factor;
means for holding fixed in time in said schedule within said highest priority conflict the job step having the lowest computed flexibility index while relaxing in time each remaining job step in said highest priority conflict until that conflict is resolved;
means for relaxing, for each said job a step of which was relaxed to resolve said highest priority conflict, the steps succeeding the relaxed step only to the extent necessary to assure the steps of said job remain in said predetermined sequence;
means for continuing to resolve scheduling conflicts until all conflicts are resolved;
means for providing a representation of a final, conflict free schedule for the performance of said first plurality of jobs on said second plurality of machines;
and
means for performing said first plurality of production jobs on said second plurality of machines based on said final, conflict free schedule.

19 more elements

programmed digital computing apparatus for performing the steps of:
(a) initially scheduling each said job for performance on said machines without regard to the scheduling of any other ones of said jobs, the initial scheduling for each said job being the tightest possible schedule for that job;
(b) identifying all job scheduling conflicts, each said conflict being the scheduling of more than one said job step on the same machine at the same time;
(c) computing a priority index for each said conflict in accordance with the equation:
PI=PRP.times.MDF.times.PSL
where:
PI=conflict priority index;
PRP=product of the job process time/job due time ratios of the jobs in said conflict;
MDF=demand factor of the machine on which said conflict occurs;
PSL=sum of the performance durations of the job steps constituting said conflict;
(d) selecting a highest priority conflict having the largest computed priority index;
(e) computing, for each job step constituting said highest priority conflict, a flexibility index in accordance with the equation:
FI=ST-SF
where:
FI=job step flexibility index;
ST=job slack time;
SF=job shift factor;
(f) holding fixed in time in said schedule within said highest priority conflict the job step having the lowest computed flexibility index while relaxing in time each remaining job step in said highest priority conflict until that conflict is resolved;
(g) relaxing, for each said job a step of which was relaxed to resolve said highest priority conflict, the steps succeeding the relaxed step only to the extent necessary to assure the steps of said job remain in said predetermined sequence;
(h) returning to step (b) if there remain any scheduling conflicts;
(i) providing a representation of a final, conflict free schedule for the performance of said first plurality of jobs on said second plurality of machine;
and
means for performing said first plurality of production jobs on said second plurality of machines based on said final, conflict free schedule.

20 more elements

Dependencies are inferred from the claim text.

Facts

Application: 07/161,513Filed 29 Feb 1988
Granted: 23 Jan 1990
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06Q 10/06
Administration; Management: resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation…
G05B 19/41865
Total factory control, i.e. centrally controlling a plurality of machines, e.g. direct or distributed numerical control [DNC], flexible…:…
G05B 2219/34418
Director, elements to supervisory: scheduler for sequential control, task planning, control sequence
G06Q
Information and communication technology [ict] specially adapted for administrative, commercial, financial, managerial