Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

High-Speed Scheduling Method

IP.com Disclosure Number: IPCOM000120098D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 125K

Publishing Venue

IBM

Related People

Hirose, S: AUTHOR [+2]

Abstract

Disclosed is a method for efficiently generating active operation schedules to static job-shop problems. In this method, schedule generation is performed by allocating operations to machines one by one. Fast execution is achieved by effectively omitting unnecessary calculation for unrelated operations.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

High-Speed Scheduling Method

      Disclosed is a method for efficiently generating active
operation schedules to static job-shop problems.  In this method,
schedule generation is performed by allocating operations to machines
one by one.  Fast execution is achieved by effectively omitting
unnecessary calculation for unrelated operations.

      Basically, the input to static job-shop scheduling problems is
a set of jobs and a set of machines.  A job consists of some
operations.  An operation in a job may have precedence over another
operation in the same job.  In such a case, the latter must start
after the former completes. An operation can be performed by more
than one machine. Therefore, scheduling is to determine the start
time and the machine to be used for each operation.  It is assumed
that the processing time of each operation can be predetermined when
a machine for the operation is fixed.

      For the purpose of scheduling, two attributes are maintained.
They are the "earliest possible start time (EST)" of operations and
the "completion time (CT)" of machines.  The EST of an operation
constrains the operation to start at a later time than the specified
EST.  The initial value of EST is usually the start time of the
schedule period, but any other value can be specified if a product
has special production condition.  The CT of a machine is the end
time of the last operation allocated to the machine by now. As
operations are allocated to a machine, its CT changes.  The initial
value of this attribute is usually the start time of the schedule
period, but any other value can be used if a machine requires some
special consideration.

      An operation is "schedulable" if all of its preceding
operations have been scheduled.  In this method, a list of
schedulable operations sorted by their EST in ascending order is
maintained.  (The list structure is used here for easy explanation,
but other data structures, such as balanced tree, can be used for
efficiency as long as sequential access to the contents is
implemented.)  The initial contents of this list are the operations
without a preceding operation.

      In this method, operations are scheduled one by one. At each
step of the execution, an operation is selected from the list of
schedulable operations with the information on the start time and the
machine to be used.  (The selection algorithm is explained in detail
below.)  Then, the processing time and the end time of the operation
is calculated, the CT of the machine is updated, and the operation is
removed from the list.  If there are operations which have become
schedulable by this allocation, they are added to the list.  When an
operation is added to the list, its EST is updated according to the
end times of its preceding operations (the maximum of the end times
and the original EST is used).  The operation is then inserted to an
appropriate position so that the list can remain sorted....