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 条
  • [21] The two-machine open shop problem: To fit or not to fit, that is the question
    van den Akker, M
    Hoogeveen, H
    Woeginger, GJ
    OPERATIONS RESEARCH LETTERS, 2003, 31 (03) : 219 - 224
  • [22] Two-machine flow shop no-wait scheduling with a nonavailability interval
    Kubzin, MA
    Strusevich, VA
    NAVAL RESEARCH LOGISTICS, 2004, 51 (04) : 613 - 631
  • [23] A heuristic algorithm for two-machine re-entrant shop scheduling
    Drobouchevitch, IG
    Strusevich, VA
    ANNALS OF OPERATIONS RESEARCH, 1999, 86 (0) : 417 - 439
  • [24] Two-stage open shop scheduling with a bottleneck machine
    Drobouchevitch, IG
    Strusevich, VA
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2001, 128 (01) : 159 - 174
  • [25] Minimising the makespan in the two-machine job shop problem under availability constraints
    Benttaleb, Mourad
    Hnaien, Faicel
    Yalaoui, Farouk
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2019, 57 (05) : 1427 - 1457
  • [26] Minimizing the makespan for the two-machine flow shop scheduling problem with random breakdown
    Hnaien, Faicel
    Arbaoui, Taha
    ANNALS OF OPERATIONS RESEARCH, 2023, 328 (02) : 1437 - 1460
  • [27] Non-Preemptive Open Shop Scheduling Considering Machine Availability
    Barjouei, A. Shojaei
    Barabadi, Abbas
    Tavakkoli-Moghaddam, R.
    2019 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2019, : 1280 - 1284
  • [28] A 3/2 algorithm for two-machine open shop with route-dependent processing times
    Strusevich, VA
    Van De Waart, AJA
    Dekker, R
    JOURNAL OF HEURISTICS, 1999, 5 (01) : 5 - 28
  • [29] A 3/2 Algorithm for Two-Machine Open Shop with Route-Dependent Processing Times
    V. A. Strusevich
    A. J. A. van de Waart
    R. Dekker
    Journal of Heuristics, 1999, 5 : 5 - 28
  • [30] A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints
    Kameng Nip
    Zhenbo Wang
    Journal of Scheduling, 2023, 26 : 543 - 558
12345