Scheduling Equal-Length Jobs with Delivery times on Identical Processors

The problem of scheduling n jobs of equal duration p with release and delivery times on m identical processors with the objective to minimize the maximal job completion time is considered. An algorithm is proposed that has the time complexity O ( mn log n ) if the maximal job delivery time q max is bounded by some constant. This is better than the earlier known best bound of O ( mn 2 log( np / m )) for the version of the problem with non-restricted q max . The algorithm has the time complexity O(q_{\max }^2 n\log n\max \{ m,\;q_{\max } \} ) without the restriction on q max . As the presented computational experiments show, practical behavior of the algorithm remains good without restriction on q max , i.e., for arbitrarily long delivery times, the running time of the algorithm, in practice, does not depend on q max .

Keywords:

• Scheduling Identical Processors
• Release Time
• Delivery Time
• Computational Complexity