Two-machine open shop scheduling with an availability constraint

被引：27
|
作者：
Breit, J [1 ]
Schmidt, G
Strusevich, VA
机构：
[1] Univ Saarland, Dept Informat & Technol Management, D-66041 Saarbrucken, Germany
[2] Tech Univ Clausthal, Inst Informat, D-38678 Clausthal Zellerfeld, Germany
[3] Univ Greenwich, Sch Comp & Math Sci, London SE10 9LS, England
来源：
OPERATIONS RESEARCH LETTERS | 2001年 / 29卷 / 02期
关键词：
open shop scheduling; availability constraints; worst-case analysis;
D O I：
10.1016/S0167-6377(01)00079-7
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We study a two-machine open shop scheduling problem, in which one machine is not available for processing during a given time interval. The objective is to minimize the makespan. We show that the problem is NP-hard and present an approximation algorithm with a worst-case ratio of 4/3. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：65 / 77
页数：13
相关论文
共 50 条
12345