Browse Prior Art Database

Computer Scheduling With Multiple Release Time/Deadline Intervals

IP.com Disclosure Number: IPCOM000043288D
Original Publication Date: 1984-Aug-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Simons, BF: AUTHOR

Abstract

This invention relates to a method for scheduling M machines and N processes, each process execution occupies a fixed time magnitude so that it runs uninterruptedly on the same machine within a predetermined interval. The method steps include: formation of a bipartite graph having a first set of N processes, and a second set of time intervals each of which is an integral multiple of its running time; and execution of a matching algorithm among the jobs and intervals. For the general problem there is a set of M machines and a set of N processes using the machines for a fixed amount of time (running time) each week. Each process is available to use a machine at certain times of certain days (r/d intervals).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

Computer Scheduling With Multiple Release Time/Deadline Intervals

This invention relates to a method for scheduling M machines and N processes, each process execution occupies a fixed time magnitude so that it runs uninterruptedly on the same machine within a predetermined interval. The method steps include: formation of a bipartite graph having a first set of N processes, and a second set of time intervals each of which is an integral multiple of its running time; and execution of a matching algorithm among the jobs and intervals. For the general problem there is a set of M machines and a set of N processes using the machines for a fixed amount of time (running time) each week. Each process is available to use a machine at certain times of certain days (r/d intervals). The method is constrained to one in which all processes require the same amount of time on a machine, and each r/d interval has multiples of that amount of time as its endpoints. To simplify the analysis, it shall be assumed that all processes require a unity time interval on a machine and that the r/d intervals have a time dimension as endpoints. It shall also be assumed that once execution of a process has begun, then the execution cannot be interrupted until it has been completed. A set of processes can be executed (a problem instance is feasible) if, and only if, each process can receive a unit time each week (each process can be run in its entirety during one of its r/d intervals). The first step in the method is to transform the problem into a matching problem on a bipartite graph. This transformation is the first part of the algorithm. After the transformation is completed, the algorithm calls either the bipartite matching algorithm (BMA) or the weighted bipartite matching algorithm (WBMA) as a subroutine. It is noted that a process can have one or many very long r/d intervals. It is shown that for each process J(i), it is possible to eliminate all but the first n/m units of r/d time for J(i), where n/m is the smallest integer greater than or equal to n/m. This is essential to bounding the running time of the algorithm, since the algorithm partitions the n/d intervals into unit length intervals when it constructs the bipartite graph. If there were no bound on the length of the r/d intervals, then the bipartite graph might have an exponential number of nodes. It can be assumed that n/m is a bound on the total amount of time for which any process is available. The algorithm partitions all r/d intervals of length greater than one...