Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines

Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines

0.00 Avg rating0 Votes
Article ID: iaor20106373
Volume: 13
Issue: 5
Start Page Number: 479
End Page Number: 492
Publication Date: Oct 2010
Journal: Journal of Scheduling
Authors: ,
Abstract:

The paper addresses the problem of multi-slot just-in-time scheduling. Unlike the existing literature on this subject, it studies a more general criterion–the minimization of the schedule makespan rather than the minimization of the number of slots used by schedule. It gives an O(nlog2 n)-time optimization algorithm for the single machine problem. For arbitrary number of m>1 identical parallel machines it presents an O(nlogn)-time optimization algorithm for the case when the processing time of each job does not exceed its due date. For the general case on m>1 machines, it proposes a polynomial time constant factor approximation algorithm.

Reviews

Required fields are marked *. Your email address will not be published.