Off‐line scheduling with forbidden zones

Off‐line scheduling with forbidden zones

0.00 Avg rating0 Votes
Article ID: iaor2013761
Volume: 40
Issue: 4
Start Page Number: 1034
End Page Number: 1037
Publication Date: Apr 2013
Journal: Computers and Operations Research
Authors: ,
Keywords: scheduling, combinatorial optimization
Abstract:

In various manufacturing and computing environments there may be certain time intervals, during which processing may continue but may not be initiated. We examine the problem of off‐line scheduling in the presence of such forbidden zones. The problem is closely related to a one‐dimensional open‐end bin packing problem. We prove that the decision version of the problem is strongly NP‐complete and then establish bounds on the asymptotic performance ratio of an O ( n log n ) equ1 approximation algorithm for a special case, and test it numerically. We present a further heuristic for a non‐regular case and test it empirically.

Reviews

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