US6038539A — Job scheduling system for designating procedure s…

Claim 1

Independent Claim 302 words

A computer-implemented job shop scheduling system for designating start times of a plurality of procedures processed by a plurality of resource devices, having restriction conditions with respect to available start times, end times, a sequence of said procedures, and a prohibition of simultaneous executions of multiple said procedures, said system comprising: initial restriction violating condition set means for initially setting restriction violating conditions which satisfy a sufficient condition for a violation of said restriction conditions; start time change means for changing a first start time of one of said plurality of procedures when said restriction violating condition is set by said initial restriction violating condition set means, to not satisfy said restriction violating conditions, thereby optimizing a total process time; start time designation means for designating a second start time of one of said plurality of procedures when said restriction violating condition is set by said initial restriction violating condition set means, to not satisfy said restriction violating conditions, thereby optimizing a total process time; restriction violating condition generation means for assigning a start time of a procedure which satisfies at least one of said restriction violating conditions to a corresponding variable of one of the restriction violating conditions which is satisfied and for ANDing said restriction violating conditions with said one restriction violating condition having said assigned start time to generate a new restriction violating condition and for narrowing a search space by substituting a real numeric number of a start time into a variable corresponding to a start time of a restriction violating condition and prohibiting a sub-schedule based on a partially undefined schedule which satisfies said restriction violating condition; and restriction violating condition storage means for storing said restriction violating conditions set by said initial restriction violating condition set means and generated by said restriction violating condition generation means.

Claim 2

Dependent Claim 302 words

A computer-implemented job shop scheduling system for designating start times of a plurality of procedures processed by a plurality of resource devices, having restriction conditions with respect to available start times, end times, a sequence of said procedures, and a prohibition of simultaneous executions of multiple said procedures, said system comprising: initial restriction violating condition set means for initially setting restriction violating conditions which satisfy a sufficient condition for a violation of said restriction conditions; start time change means for changing a first start time of one of said plurality of procedures when said restriction violating condition is set by said initial restriction violating condition set means, to not satisfy said restriction violating conditions, thereby optimizing a total process time; start time designation means for designating a second start time of one of said plurality of procedures when said restriction violating condition is set by said initial restriction violating condition set means, to not satisfy said restriction violating conditions, thereby optimizing a total process time; restriction violating condition generation means for assigning a start time of a procedure which satisfies at least one of said restriction violating conditions to a corresponding variable of one of the restriction violating conditions which is satisfied and for ANDing said restriction violating conditions with said one restriction violating condition having said assigned start time to generate a new restriction violating condition and for narrowing a search space by substituting a real numeric number of a start time into a variable corresponding to a start time of a restriction violating condition and prohibiting a sub-schedule based on a partially undefined schedule which satisfies said restriction violating condition; and restriction violating condition storage means for storing said restriction violating conditions set by said initial restriction violating condition set means and generated by said restriction violating condition generation means.

Claim 3

Dependent Claim 55 words

The computer-implemented job shop scheduling system as set forth in claim 1, wherein an available start time and end time of each of said plurality of procedures included in said restriction violating conditions are variables making a restriction violating condition still valid even after the corresponding available start time or available end time is changed.

Claim 4

Dependent Claim 74 words

The computer-implemented job shop scheduling system as set forth in claim 2, further including a device to update the value of said variables representing the available start time or the end time to a stricter value whenever one schedule is obtained and to generate a restriction validating condition which includes a variable corresponding to the available start time or the available end time as the only variable when a schedule cannot be successfully obtained.

Claim 5

Dependent Claim 194 words

The computer-implemented job shop scheduling system as set forth in claim 1, further comprising: a device to update the value of a variable representing an available start time or end time to a stricter value whenever one schedule is obtained and to generate a restriction validating condition which includes a variable corresponding to the available start time or the available end time as the only variable when a schedule cannot be successfully obtained; resource allocation means for allocating said resource devices; processing time allocation means for allocating processing time; procedure sequence allocation means for allocating a sequence of a procedure by considering said available start times, said end times, a restriction for a procedure sequence to be selected from a lowest order to higher orders, said simultaneous execution prohibition of said multiple procedures; and job allocation means for allocating a job, whereby said initial restriction violating condition set means, said start time change means, said start time designation means, said restriction violating condition generation means, and said restriction violating condition storage means are controlled by said resource allocation means, said processing time allocation means, said procedure sequence allocation means and said job allocation means.

Claim 6

Dependent Claim 46 words

The computer-implemented job shop scheduling system as set forth in claim 1 wherein said available start time is defined as a restriction violation condition defined by applying a negative condition to a condition for a first procedure available start time and a next available start time.

Claim 7

Dependent Claim 47 words

The computer-implemented job shop scheduling system as set forth in claim 1 wherein said end time is defined as a restriction violation condition defined by applying a negative condition to an end time condition defined with an end time variable number resulted from all necessary procedure times.

Claim 8

Dependent Claim 42 words

The computer-implemented job shop scheduling system as set forth in claim 1 wherein said procedure sequence is defined as a restriction violation condition defined by applying a negative condition to a condition defined by adding corresponding process time and corresponding start time.

Claim 9

Dependent Claim 51 words

The computer-implemented job shop scheduling system as set forth in claim 1 wherein said simultaneous execution prohibition for multiple procedures is defined by a restriction condition showing an impossibility for processing multiple procedures with a same machine by applying a negative condition to conditions for procedures executed by said same machine.

Claim 10

Dependent Claim 258 words

A computer-implemented job shop scheduling system for designating start times of a plurality of procedures processed by a plurality of resource devices, having restriction conditions with respect to available start times, end times, a sequence of said procedures, and a prohibition of simultaneous executions of multiple said procedures, said system comprising: initial restriction satisfying condition set means for initially setting restriction satisfying conditions which satisfy a necessary condition for a satisfaction of said restriction conditions; start time change means for changing a first start time of one of said plurality of procedures when said restriction satisfying condition is set by said initial restriction satisfying condition set means, to satisfy said restriction satisfying conditions, thereby optimizing a total process time; start time designation means for designating a second start time of one of said plurality of procedures when said restriction satisfying condition is set by said initial restriction satisfying condition set means, to satisfy said restriction satisfying conditions, thereby optimizing a total process time; restriction satisfying condition generation means for assigning a start time of a procedure which does not satisfy at least one of said restriction satisfying conditions to a corresponding variable of one of the restriction satisfying conditions which is not satisfied and for ANDing said restriction satisfying conditions with said one restriction satisfying condition having said assigned start time to generate a new restriction satisfying condition; and restriction satisfying condition storage means for storing said restriction satisfying conditions set by said initial restriction satisfying condition set means and generated by said restriction satisfying condition generation means.

Claim 11

Dependent Claim 258 words

A computer-implemented job shop scheduling system for designating start times of a plurality of procedures processed by a plurality of resource devices, having restriction conditions with respect to available start times, end times, a sequence of said procedures, and a prohibition of simultaneous executions of multiple said procedures, said system comprising: initial restriction satisfying condition set means for initially setting restriction satisfying conditions which satisfy a necessary condition for a satisfaction of said restriction conditions; start time change means for changing a first start time of one of said plurality of procedures when said restriction satisfying condition is set by said initial restriction satisfying condition set means, to satisfy said restriction satisfying conditions, thereby optimizing a total process time; start time designation means for designating a second start time of one of said plurality of procedures when said restriction satisfying condition is set by said initial restriction satisfying condition set means, to satisfy said restriction satisfying conditions, thereby optimizing a total process time; restriction satisfying condition generation means for assigning a start time of a procedure which does not satisfy at least one of said restriction satisfying conditions to a corresponding variable of one of the restriction satisfying conditions which is not satisfied and for ANDing said restriction satisfying conditions with said one restriction satisfying condition having said assigned start time to generate a new restriction satisfying condition; and restriction satisfying condition storage means for storing said restriction satisfying conditions set by said initial restriction satisfying condition set means and generated by said restriction satisfying condition generation means.

Claim 12

Dependent Claim 55 words

The computer-implemented job shop scheduling system as set forth in claim 9, wherein an available start time and end time of each of said plurality of procedures included in said restriction satisfying conditions are variables making a restriction satisfying condition still valid even after the corresponding available start time or available end time is changed.

Claim 13

Dependent Claim 86 words

The computer-implemented job shop scheduling system as set forth in claim 10, further including a device to update the value of said variables representing the available start time or the end time to a stricter value whenever one schedule is obtained and to generate a restriction satisfying condition which includes a variable corresponding to the available start time or the available end time as the only variable when a schedule cannot be successfully obtained, thereby obtaining an optimum schedule with a minimum total process time period.

Claim 14

Dependent Claim 206 words

The computer-implemented job shop scheduling system as set forth in claim 9, further comprising: a device to update the value of a variable representing an available start time or end time to a stricter value whenever one schedule is obtained and to generate a restriction satisfying condition which includes a variable corresponding to the available start time or the available end time as the only variable when a schedule cannot be successfully obtained, thereby obtaining an optimum schedule with a minimum total process time period; resource allocation means for allocating said resource devices; processing time allocation means for allocating processing time; procedure sequence allocation means for allocating a sequence of a procedure by considering said available start times, said end times, a restriction for a procedure sequence to be selected from a lowest order to higher orders, said simultaneous execution prohibition of said multiple procedures; and job allocation means for allocating a job, whereby said initial restriction violating condition set means, said start time change means, said start time designation means, said restriction violating condition generation means, and said restriction violating condition storage means are controlled by said resource allocation means, said processing time allocation means, said procedure sequence allocation means and said job allocation means.

Claim 15

Dependent Claim 241 words

A computer-implemented job shop scheduling method for designating start times of a plurality of procedures processed by a plurality of resource devices, having restriction conditions with respect to available start times, end times, a sequence of said procedures, and a prohibition of simultaneous executions of multiple said procedures, said method comprising the steps of: initially setting restriction violating conditions which satisfy a sufficient condition for a violation of said restriction conditions; changing a first start time of one of said plurality of procedures when said restriction violating condition is set, to not satisfy said restriction violating conditions, thereby optimizing a total process time; designating a second start time of one of said plurality of procedures when said restriction violating condition is set, to not satisfy said restriction violating conditions, thereby optimizing a total process time; assigning a start time of a procedure which satisfies at least one of said restriction violating conditions to a corresponding variable of one of the restriction violating conditions which is satisfied and ANDing said restriction violating conditions with said one restriction violating condition having said assigned start time to generate a new restriction violating condition and for narrowing a search space by substituting a real numeric number of a start time into a variable corresponding to a start time of a restriction violating condition and prohibiting a sub-schedule based on a partially undefined schedule which satisfies said restriction violating condition; and storing said restriction violating conditions.

Claim 16

Dependent Claim 241 words

A computer-implemented job shop scheduling method for designating start times of a plurality of procedures processed by a plurality of resource devices, having restriction conditions with respect to available start times, end times, a sequence of said procedures, and a prohibition of simultaneous executions of multiple said procedures, said method comprising the steps of: initially setting restriction violating conditions which satisfy a sufficient condition for a violation of said restriction conditions; changing a first start time of one of said plurality of procedures when said restriction violating condition is set, to not satisfy said restriction violating conditions, thereby optimizing a total process time; designating a second start time of one of said plurality of procedures when said restriction violating condition is set, to not satisfy said restriction violating conditions, thereby optimizing a total process time; assigning a start time of a procedure which satisfies at least one of said restriction violating conditions to a corresponding variable of one of the restriction violating conditions which is satisfied and ANDing said restriction violating conditions with said one restriction violating condition having said assigned start time to generate a new restriction violating condition and for narrowing a search space by substituting a real numeric number of a start time into a variable corresponding to a start time of a restriction violating condition and prohibiting a sub-schedule based on a partially undefined schedule which satisfies said restriction violating condition; and storing said restriction violating conditions.

Claim 17

Dependent Claim 197 words

A computer-implemented job shop scheduling method for designating start times of a plurality of procedures processed by a plurality of resource devices, having restriction conditions with respect to available start times, end times, a sequence of said procedures, and a prohibition of simultaneous executions of multiple said procedures, said method comprising the steps of: initially setting restriction satisfying conditions which satisfy a necessary condition for a satisfaction of said restriction conditions; changing a first start time of one of said plurality of procedures when said restriction satisfying condition is set, to satisfy said restriction satisfying conditions, thereby optimizing a total process time; designating a second start time of one of said plurality of procedures when said restriction satisfying condition is set, to satisfy said restriction satisfying conditions, thereby optimizing a total process time; assigning a start time of a procedure which does not satisfy at least one of said restriction satisfying conditions to a corresponding variable of one of the restriction violating conditions which is not satisfied and ANDing said restriction satisfying conditions with said one restriction violating condition having said assigned start time to generate a new restriction satisfying condition; and storing said restriction satisfying conditions.

Claim 18

Dependent Claim 197 words

A computer-implemented job shop scheduling method for designating start times of a plurality of procedures processed by a plurality of resource devices, having restriction conditions with respect to available start times, end times, a sequence of said procedures, and a prohibition of simultaneous executions of multiple said procedures, said method comprising the steps of: initially setting restriction satisfying conditions which satisfy a necessary condition for a satisfaction of said restriction conditions; changing a first start time of one of said plurality of procedures when said restriction satisfying condition is set, to satisfy said restriction satisfying conditions, thereby optimizing a total process time; designating a second start time of one of said plurality of procedures when said restriction satisfying condition is set, to satisfy said restriction satisfying conditions, thereby optimizing a total process time; assigning a start time of a procedure which does not satisfy at least one of said restriction satisfying conditions to a corresponding variable of one of the restriction violating conditions which is not satisfied and ANDing said restriction satisfying conditions with said one restriction violating condition having said assigned start time to generate a new restriction satisfying condition; and storing said restriction satisfying conditions.

Claim 19

Dependent Claim 66 words

A computer implemented scheduling method for designating a procedure start time, comprising: assigning a start time for a procedure which satisfies a first restriction violating condition; and ANDing the first and another restriction violating condition generating a new restriction violating condition, thereby narrowing a search space by substituting a real number start time for a variable and prohibiting a subschedule based on a partially undefined schedule.

Claim 20

Dependent Claim 66 words

A computer implemented scheduling method for designating a procedure start time, comprising: assigning a start time for a procedure which satisfies a first restriction violating condition; and ANDing the first and another restriction violating condition generating a new restriction violating condition, thereby narrowing a search space by substituting a real number start time for a variable and prohibiting a subschedule based on a partially undefined schedule.

Claim 21

Dependent Claim 43 words

A computer implemented scheduling method for designating a procedure start time, comprising: assigning a start time for a procedure which does not satisfy a first restriction satisfying condition; and ANDing the first and another restriction satisfying condition generating a new restriction satisfying condition.

Claim 22

Dependent Claim 43 words

A computer implemented scheduling method for designating a procedure start time, comprising: assigning a start time for a procedure which does not satisfy a first restriction satisfying condition; and ANDing the first and another restriction satisfying condition generating a new restriction satisfying condition.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-03-14	2003-09-13	2004-03-14	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-03-14	2007-09-13	2008-03-14	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-03-14	2011-09-13	2012-03-14	$7700.00	Window Closed / Lapsed

Job scheduling system for designating procedure start times

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag