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: | Wirth Andrew, Abdekhodaee Amir |
Keywords: | scheduling, combinatorial optimization |
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