Job scheduling system

• US 6,131,093 A
• Filed: 02/25/1998
• Issued: 10/10/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): Amsbury, Wayne
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US09/030,016
• Time in Patent Office: 958 Days
• Field of Search: 364/468.06, 364/401, 705/8, 395/650, 707/8
• US Class Current: 1/1
• 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 scheduling system designates start times of a plurality of procedures processed by a plurality machines. The scheduling system comprises an initial restriction violating condition set portion for initially setting a restriction violating condition which is a sufficient condition for the violation of the restriction conditions, a start time change portion for changing the start time of a procedure, a start time designation portion for designating the start time of a procedure, a restriction violating condition generation portion for substituting start times of a procedure which satisfy at least one of the restriction violating conditions into a variable of one of the restriction violating conditions and ANDing the conditions so as to generate a new restriction violating condition, a restriction violating condition storage portion for storing restriction violating conditions generated by the initial restriction violating condition set portion and the restriction violating condition generation portion.

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:

a restriction violating condition generation unit to assign a real number of a start time for a procedure which satisfies a restriction violation condition to a variable corresponding to the start time in the satisfied restriction violation condition, taking an AND of the real number assigned to the restriction violating conditions for each value of the variable to generate a new restriction violation condition without the variable, and narrowing a search space by prohibiting a sub-schedule based on a partially undefined schedule which satisfies said restriction violation condition; and

a restriction violating condition storage unit to store said restriction violation condition set by said restriction violating condition generation unit.

2. The computer-implemented job shop scheduling system as set forth in claim 1, further comprising:

an initial restriction violating condition set unit to set initial restriction violating conditions which satisfy a sufficient condition for a violation of said restriction condition;

a start time change unit to change 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 unit, not to satisfy said restriction violating condition; and

a start time designation unit to designate 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 unit, not to satisfy said restriction violating condition.

3. The computer-implemented job shop scheduling system as set forth in claim 1, wherein said restriction violation condition generated before changing can be validated when an available start time and an end time are changed by using the restriction violation condition in which a value for available start time and end time are set by a variable number to narrow a result search space and shorten a proceeding time.

4. The computer-implemented job shop scheduling system as set forth in claim 1, wherein said restriction violation condition generated before changing can be validated when an available start time and an end time are changed by using the restriction satisfying condition in which a value for available start time and end time are set by a variable number to narrow a result search space and shorten a proceeding time.

5. The computer-implemented job shop scheduling system as set forth in claim 1, wherein a best suitable schedule based on a smallest amount of necessary time is generated by identifying that events satisfying the stored restriction violation condition including a sub-schedule, which has not been carried out, cannot satisfy the given restriction however acceptable the definition for the undefined portions of the sub-schedule is to delete wasteful proceedings and shorten proceeding time as a result of narrowing search space.

6. The computer-implemented job shop scheduling system as set forth in claim 1, wherein a best suitable schedule based on a smallest amount of necessary time is generated by identifying that events not satisfying the stored restriction satisfying condition including a sub-schedule, which has not been carried out, cannot satisfy the given restriction however acceptable the definition for the undefined portions of the sub-schedule is to delete wasteful proceedings and shorten proceeding time as a result of narrowing search space.