Computer Scheduling With Multiple Release Time/Deadline Intervals
Original Publication Date: 1984-Aug-01
Included in the Prior Art Database: 2005-Feb-04
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).