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 条
  • [31] Solving the Flow-Shop Scheduling problem using Grover's Algorithm
    Saiem, Malak
    Arbaoui, Taha
    Hnaien, Faicel
    [J]. PROCEEDINGS OF THE 2023 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION, GECCO 2023 COMPANION, 2023, : 2250 - 2253
  • [32] Hybrid flow shop scheduling problem in ubiquitous manufacturing environmentInspec keywordsOther keywords
    Wu, Xiuli
    Li, Jing
    Sun, Lin
    [J]. IET COLLABORATIVE INTELLIGENT MANUFACTURING, 2019, 1 (02) : 56 - 66
  • [33] Routing open shop and flow shop scheduling problems
    Yu, Wei
    Liu, Zhaohui
    Wang, Leiyang
    Fan, Tijun
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 213 (01) : 24 - 36
  • [34] A hybrid nested partitions algorithm for scheduling flexible resource in flow shop problem
    Wu, Wei
    Wei, Junhu
    Guan, Xiaohong
    Shi, Leyuan
    [J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2012, 50 (10) : 2555 - 2569
  • [35] Flow-Shop Scheduling Problem applied to programming repair medical equipment
    Mellado, R.
    Cubillos, C.
    Cabrera, D.
    [J]. 2016 IEEE INTERNATIONAL CONFERENCE ON AUTOMATICA (ICA-ACCA), 2016,
  • [36] A Discrete Artificial Bee Colony Algorithm for the Blocking Flow Shop Scheduling Problem
    Deng, Guanlong
    Cui, Zhe
    Gu, Xingsheng
    [J]. PROCEEDINGS OF THE 10TH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION (WCICA 2012), 2012, : 518 - 522
  • [37] The circular discrete particle swarm optimization algorithm for flow shop scheduling problem
    Zhang, Jindong
    Zhang, Changsheng
    Liang, Shubin
    [J]. EXPERT SYSTEMS WITH APPLICATIONS, 2010, 37 (08) : 5827 - 5834
  • [38] A circular discrete particle swarm optimization algorithm for flow shop scheduling problem
    Liang, Shubin
    Ning, Jiaxu
    Wang, Xiaodong
    Xue, Zhanao
    [J]. 2008 PROCEEDINGS OF INFORMATION TECHNOLOGY AND ENVIRONMENTAL SYSTEM SCIENCES: ITESS 2008, VOL 4, 2008, : 1151 - 1156
  • [39] An Improved Biogeography-Based Optimization Algorithm for Flow Shop Scheduling Problem
    Huang, Ming
    Shi, Shasha
    Liang, Xu
    Jiao, Xuan
    Fu, Yijie
    [J]. 2020 IEEE 8TH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND NETWORK TECHNOLOGY (ICCSNT), 2020, : 59 - 63
  • [40] Consideration of transportation lags in a two-machine Flow shop scheduling problem
    Jolai, F.
    Abedinnia, H.
    [J]. SCIENTIA IRANICA, 2013, 20 (06) : 2215 - 2223
12345