High-multiplicity scheduling on one machine with forbidden start and completion times

High-multiplicity scheduling on one machine with forbidden start and completion times

0.00 Avg rating0 Votes
Article ID: iaor20163652
Volume: 19
Issue: 5
Start Page Number: 609
End Page Number: 616
Publication Date: Oct 2016
Journal: Journal of Scheduling
Authors: , ,
Keywords: scheduling, production, combinatorial optimization, simulation
Abstract:

We are interested in a single machine scheduling problem where jobs can neither start nor end on some specified instants, and the aim is to minimize the makespan. This problem models the situation where an additional resource, subject to unavailability constraints, is required to start and to finish a job. We consider in this paper the high‐multiplicity version of the problem, when the input is given using a compact encoding. We present a polynomial time algorithm for large diversity instances (when the number of different processing times is greater than the number of forbidden instants). We also show that this problem is fixed‐parameter tractable when the number of forbidden instants is fixed, regardless of jobs characteristics.

Reviews

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