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 条
[41]   A Decomposition and Coordination Scheduling Method for Flow-shop Problem Based on TOC [J].
ZHANG HongYuan XI YuGeng GU HanYu Institute of Automation Shanghai Jiaotong University Shanghai .
自动化学报, 2005, (02) :182-187
[42]   Moth optimisation algorithm with local search for the permutation flow shop scheduling problem [J].
Abuhamdah, Anmar ;
Alzaqebah, Malek ;
Jawarneh, Sana ;
Althunibat, Ahmad ;
Banikhalaf, Mustafa .
INTERNATIONAL JOURNAL OF COMPUTER APPLICATIONS IN TECHNOLOGY, 2021, 65 (03) :189-208
[43]   A modified branch and bound algorithm for a vague flow-shop scheduling problem [J].
Gholizadeh, H. ;
Fazlollahtabar, H. ;
Gholizadeh, R. .
IRANIAN JOURNAL OF FUZZY SYSTEMS, 2019, 16 (04) :55-64
[44]   Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization [J].
Kaizhou Gao ;
Quanke Pan ;
P. N. Suganthan ;
Junqing Li .
The International Journal of Advanced Manufacturing Technology, 2013, 66 :1563-1572
[45]   Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization [J].
Gao, Kaizhou ;
Pan, Quanke ;
Suganthan, P. N. ;
Li, Junqing .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2013, 66 (9-12) :1563-1572
[46]   The k-Centrum Shortest Path Problem [J].
Garfinkel, Robert ;
Fernandez, Elena ;
Lowe, Timothy J. .
TOP, 2006, 14 (02) :279-292
[47]   A strong flow-based formulation for the shortest path problem in digraphs with negative cycles [J].
Ibrahim, M. S. ;
Maculan, N. ;
Minoux, M. .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2009, 16 (03) :361-369
[48]   Applying Reinforcement Learning for Shortest Path Problem [J].
Sun, Zhixuan .
2022 INTERNATIONAL CONFERENCE ON BIG DATA, INFORMATION AND COMPUTER NETWORK (BDICN 2022), 2022, :820-824
[49]   Discussion on a Simplified Algorithm for the Shortest Path Problem [J].
Cuiyan ;
Litong ;
Renshupo .
2008 INTERNATIONAL WORKSHOP ON INFORMATION TECHNOLOGY AND SECURITY, 2008, :66-69
[50]   Parameterized Algorithms for Eccentricity Shortest Path Problem [J].
Bhyravarapu, Sriram ;
Jana, Satyabrata ;
Kanesh, Lawqueen ;
Saurabh, Saket ;
Verma, Shaily .
COMBINATORIAL ALGORITHMS, IWOCA 2023, 2023, 13889 :74-86
12345