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 条
  • [41] A heuristic for scheduling two-machine no-wait flow shops with anticipatory setups
    Sidney, JB
    Potts, CN
    Sriskandarajah, C
    OPERATIONS RESEARCH LETTERS, 2000, 26 (04) : 165 - 173
  • [42] Two-machine flowshop scheduling with intermediate transportation under job physical space consideration
    Gong, Hua
    Tang, Lixin
    COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (09) : 1267 - 1274
  • [43] Competitive two-agent scheduling problems to minimize the weighted combination of makespans in a two-machine openshop
    Jiang, Fuhong
    Zhang, Xingong
    Bai, Danyu
    Wu, Chin-Chia
    ENGINEERING OPTIMIZATION, 2018, 50 (04) : 684 - 697
  • [44] Minimizing the rnakespan in the non-preemptive job-shop scheduling with limited machine availability
    Mati, Yazid
    COMPUTERS & INDUSTRIAL ENGINEERING, 2010, 59 (04) : 537 - 543
  • [45] An improved algorithm for the two machine flow shop problem with several availability constraints
    Hadda, Hatem
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2010, 8 (03): : 271 - 280
  • [46] A survey of scheduling with deterministic machine availability constraints
    Ma, Ying
    Chu, Chengbin
    Zuo, Chunrong
    COMPUTERS & INDUSTRIAL ENGINEERING, 2010, 58 (02) : 199 - 211
  • [47] Scheduling rules for two-stage flexible flow shop scheduling problem subject to tail group constraint
    Li, Zhan-tao
    Chen, Qing-xin
    Mao, Ning
    Wang, Xiaoming
    Liu, Jianjun
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2013, 146 (02) : 667 - 678
  • [48] An improved algorithm for the two machine flow shop problem with several availability constraints
    Hatem Hadda
    4OR, 2010, 8 : 271 - 280
  • [49] An Improved Solution Algorithm for Two-Job Shop Scheduling Problems with Availability Constraints
    Aggoune, Riad
    INTERNATIONAL MULTICONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS (IMECS 2010), VOLS I-III, 2010, : 2180 - 2185
  • [50] Scheduling with limited machine availability
    Schmidt, G
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 121 (01) : 1 - 15
12345