An improved algorithm for the two machine flow shop problem with several availability constraints

被引：3
作者：
Hadda, Hatem [1 ]
机构：
[1] Ctr Urbain Nord, INSAT Tunis, Unite Rech URAII, Tunis 1080, Tunisia
来源：
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH | 2010年 / 8卷 / 03期
关键词：
Flow shop scheduling; Availability constraint; Heuristics; Worst case analysis; Polynomially solvable case; 2-MACHINE FLOWSHOP;
D O I：
10.1007/s10288-010-0119-7
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper we deal with the two-machine flow shop scheduling problem with several availability constraints on the first machine, under the resumable scenario. We first develop an improved algorithm with a relative worst-case error bound of 4/3. We then present a polynomially solvable case.
引用
收藏
页码：271 / 280
页数：10
相关论文
共 50 条
  • [41] A general flow shop scheduling problem with consideration of position-based learning effect and multiple availability constraints
    Behdin Vahedi-Nouri
    Parviz Fattahi
    Reza Tavakkoli-Moghaddam
    Reza Ramezanian
    The International Journal of Advanced Manufacturing Technology, 2014, 73 : 601 - 611
  • [42] TWO-MACHINE FLOW SHOP WITH SYNCHRONIZED PERIODIC MAINTENANCE
    Krimi, Issam
    Benmansour, Rachid
    Hanafi, Said
    Elhachemi, Nizar
    RAIRO-OPERATIONS RESEARCH, 2019, 53 (01) : 351 - 365
  • [43] Two-machine open shop scheduling with an availability constraint
    Breit, J
    Schmidt, G
    Strusevich, VA
    OPERATIONS RESEARCH LETTERS, 2001, 29 (02) : 65 - 77
  • [44] A two-stage hybrid flow shop problem with dedicated machine and release date
    Nabli, Zouhour
    Khalfallah, Soulef
    Korbaa, Ouajdi
    KNOWLEDGE-BASED AND INTELLIGENT INFORMATION & ENGINEERING SYSTEMS (KES-2018), 2018, 126 : 214 - 223
  • [45] An exact solution with an improved running time for the routing flow shop problem with two machines
    Chernykh, Ilya
    Kononov, Alexander
    Sevastyanov, Sergey
    JOURNAL OF SCHEDULING, 2024, 27 (04) : 329 - 340
  • [46] No-wait scheduling of a two-machine flow-shop to minimise the makespan under non-availability constraints and different release dates
    Ben Chihaoui, Faten
    Kacem, Imed
    Hadj-Alouane, Atidel B.
    Dridi, Najoua
    Rezg, Nidhal
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2011, 49 (21) : 6273 - 6286
  • [47] A fast tabu search algorithm for the permutation flow-shop problem
    Nowicki, E
    Smutnicki, C
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 91 (01) : 160 - 175
  • [48] Two-Layer Harmony Search Algorithm for a Robust Flow Shop Scheduling Problem
    Wu, Bo
    Wang, Bing
    Han, Xingbao
    INTELLIGENT COMPUTING, NETWORKED CONTROL, AND THEIR ENGINEERING APPLICATIONS, PT II, 2017, 762 : 252 - 261
  • [49] An Improved Discrete Migrating Birds Optimization Algorithm for the No-Wait Flow Shop Scheduling Problem
    Zhang, Sujun
    Gu, Xingsheng
    Zhou, Funa
    IEEE ACCESS, 2020, 8 (08): : 99380 - 99392
  • [50] A \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(\frac 4 3) -}$$\end{document} approximation algorithm for a special case of the two machine flow shop problem with several availability constraints
    Hatem Hadda
    Optimization Letters, 2009, 3 (4) : 583 - 592
12345