Off-line scheduling with forbidden zones

被引：2

作者：

Abdekhodaee, Amir ^{[1
]}

Wirth, Andrew ^{[2
]}

机构：

[1] Swinburne Univ Technol, Fac Engn & Ind Sci, Hawthorn, Vic 3122, Australia

[2] Univ Melbourne, Dept Mech Engn, Melbourne, Vic 3010, Australia

来源：

COMPUTERS & OPERATIONS RESEARCH | 2013年 / 40卷 / 04期

关键词：

Scheduling; Bin packing; Tidal constraints;

D O I：

10.1016/j.cor.2012.10.020

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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) approximation algorithm for a special case, and test it numerically. We present a further heuristic for a non-regular case and test it empirically. (C) 2012 Elsevier Ltd. All rights reserved.

引用

页码：1034 / 1037

页数：4