Job scheduling system for designating procedure start times

• US 6,038,539 A
• Filed: 03/04/1993
• Issued: 03/14/2000
• Est. Priority Date: 03/04/1992
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Maruyama, Fumihiro, Minoda, Yoriko, Takizawa, Yuka, Sawada, Shuho
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/026,014
• Time in Patent Office: 2,567 Days
• Field of Search: 364/401, 364/402, 364/403, 364/468, 364/468.05, 364/468.06, 364/468.07, 395/207, 395/208, 395/209, 705/7, 705/8, 705/9
• US Class Current: 705/7.24
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A computer-implemented scheduling system and method designates start times of a plurality of procedures processed by a plurality of resource devices. The computer-implemented scheduling system includes an initial restriction violating condition set device for initially setting restriction violating conditions which satisfy a sufficient condition for a violation of the restriction conditions, a start time change device for changing a first start time of one of the procedures, when the restriction violating condition is set by the initial restriction violating condition set device, not to satisfy the restriction violating conditions, a start time designation device for designating a second start time of one of the procedures, when the restriction violating condition is set by the initial restriction violating condition set device, not to satisfy the restriction violating conditions, a restriction violating condition generation device for substituting the first or second start time of one of the procedures, when the start time change device changes the first start time or the start time designation device designates the second start time, respectively, to satisfy the restriction violating conditions, into a variable of the one restriction violating condition and for ANDing the restriction violating conditions with the one restriction violating condition having the substituted first or second start time, to generate a new restriction violating condition, and a restriction violating condition storage device for storing the restriction violating conditions set by the initial restriction violating condition set device and generated by the restriction violating condition generation device.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

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

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.