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 条
  • [31] A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints
    Nip, Kameng
    Wang, Zhenbo
    JOURNAL OF SCHEDULING, 2023, 26 (06) : 543 - 558
  • [32] The Two-machine Flow-shop Scheduling Problem with a Single Server and Unit Server Times
    Ling, Shi
    Guang, Cheng Xue
    JOURNAL OF INFORMATICS AND MATHEMATICAL SCIENCES, 2012, 4 (01): : 123 - 127
  • [33] Heuristic algorithms for the two-machine flowshop with limited machine availability
    Blazewicz, J
    Breit, J
    Formanowicz, P
    Kubiak, W
    Schmidt, G
    OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2001, 29 (06): : 599 - 608
  • [34] The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan
    Munier-Kordon, Alix
    Rebaine, Djamal
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 203 (01) : 42 - 49
  • [35] Makespan Minimization in Two-Machine Flow-Shop Scheduling under No-wait and Deterministic Unavailable Interval Constraints
    Chen, Kejia
    Li, Debiao
    Wang, Xiao
    JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING, 2020, 29 (04) : 400 - 411
  • [36] Metaheuristics for the job-shop scheduling problem with machine availability constraints
    Tamssaouet, Karim
    Dauzere-Peres, Stephane
    Yugma, Claude
    COMPUTERS & INDUSTRIAL ENGINEERING, 2018, 125 : 1 - 8
  • [37] Flow shop scheduling problem with limited machine availability: A heuristic approach
    Aggoune, R
    Portmann, MC
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2006, 99 (1-2) : 4 - 15
  • [38] An open shop scheduling problem with a non-bottleneck machine
    Strusevich, VA
    Hall, LA
    OPERATIONS RESEARCH LETTERS, 1997, 21 (01) : 11 - 18
  • [39] A Two-Machine Learning Date Flow-Shop Scheduling Problem with Heuristics and Population-Based GA to Minimize the Makespan
    Xu, Jian-You
    Lin, Win-Chin
    Chang, Yu-Wei
    Chung, Yu-Hsiang
    Chen, Juin-Han
    Wu, Chin-Chia
    MATHEMATICS, 2023, 11 (19)
  • [40] A Comparison of Two-machine Flowshop with Availability Constraints for Limited Waiting Time
    Yu, Yanhui
    2015 27TH CHINESE CONTROL AND DECISION CONFERENCE (CCDC), 2015, : 6529 - 6532
12345