A combination of flow shop scheduling and the shortest path problem

被引：0
作者：
Kameng Nip
Zhenbo Wang
Fabrice Talla Nobibon
Roel Leus
机构：
[1] Tsinghua University,Department of Mathematical Sciences
[2] KU Leuven,Research Foundation–Flanders, ORSTAT, Faculty of Economics and Business
[3] KU Leuven,ORSTAT, Faculty of Economics and Business
来源：
Journal of Combinatorial Optimization | 2015年 / 29卷
关键词：
Approximation algorithm; Combination of optimization problems; Flow shop scheduling; Shortest path;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper studies a combinatorial optimization problem which is obtained by combining the flow shop scheduling problem and the shortest path problem. The objective of the obtained problem is to select a subset of jobs that constitutes a feasible solution to the shortest path problem, and to execute the selected jobs on the flow shop machines to minimize the makespan. We argue that this problem is NP-hard even if the number of machines is two, and is NP-hard in the strong sense for the general case. We propose an intuitive approximation algorithm for the case where the number of machines is an input, and an improved approximation algorithm for fixed number of machines.
引用
收藏
页码：36 / 52
页数：16
相关论文
共 50 条
  • [21] Hybrid Genetic Algorithm for Distributed Flow Shop Inverse Scheduling Problem
    Mu J.
    Duan P.
    Gao L.
    Peng W.
    Cong J.
    Jixie Gongcheng Xuebao/Journal of Mechanical Engineering, 2022, 58 (06): : 295 - 308
  • [22] Simultaneous optimization of path planning and flow shop scheduling by bacterial memetic algorithm
    Botzheim, Janos
    Toda, Yuichiro
    Kubota, Naoyuki
    PROCEEDINGS OF THE SEVENTEENTH INTERNATIONAL SYMPOSIUM ON ARTIFICIAL LIFE AND ROBOTICS (AROB 17TH '12), 2012, : 512 - 515
  • [23] A Simple and Effective Approach for Tackling the Permutation Flow Shop Scheduling Problem
    Abdel-Basset, Mohamed
    Mohamed, Reda
    Abouhawwash, Mohamed
    Chakrabortty, Ripon K.
    Ryan, Michael J.
    MATHEMATICS, 2021, 9 (03) : 1 - 23
  • [24] A Modified Cuckoo Search Algorithm for Flow Shop Scheduling Problem with Blocking
    Wang, Hui
    Wang, Wenjun
    Sun, Hui
    Li, Changhe
    Rahnamayan, Shahryar
    Liu, Yong
    2015 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2015, : 456 - 463
  • [25] The Shortest Path Problem for a Multiple Graph
    Smirnov, A. V.
    AUTOMATIC CONTROL AND COMPUTER SCIENCES, 2018, 52 (07) : 625 - 633
  • [26] Approximating the shortest path problem with scenarios
    Kasperski, Adam
    Zielinski, Pawel
    THEORETICAL COMPUTER SCIENCE, 2025, 1025
  • [27] An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter
    Soper, Alan J.
    Strusevich, Vitaly A.
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2007, 18 (03) : 565 - 591
  • [28] Approximability of flow shop scheduling
    Hall, LA
    MATHEMATICAL PROGRAMMING, 1998, 82 (1-2) : 175 - 190
  • [29] Approximability of flow shop scheduling
    Leslie A. Hall
    Mathematical Programming, 1998, 82 : 175 - 190
  • [30] Routing open shop and flow shop scheduling problems
    Yu, Wei
    Liu, Zhaohui
    Wang, Leiyang
    Fan, Tijun
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 213 (01) : 24 - 36
12345