Job shop scheduling and production method and apparatus

Claim 1

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×MDF×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.

Claim 2

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×MDF×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.

Claim 6

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×MDF×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.

Claim 7

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×MDF×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.