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 条
  • [1] A combination of flow shop scheduling and the shortest path problem
    Nip, Kameng
    Wang, Zhenbo
    Nobibon, Fabrice Talla
    Leus, Roel
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (01) : 36 - 52
  • [2] A study on several combination problems of classic shop scheduling and shortest path
    Nip, Kameng
    Wang, Zhenbo
    Xing, Wenxun
    THEORETICAL COMPUTER SCIENCE, 2016, 654 : 175 - 187
  • [3] Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms
    Nip, Kameng
    Wang, Zhenbo
    Xing, Wenxun
    COMPUTING AND COMBINATORICS, 2015, 9198 : 97 - 108
  • [4] Scheduling Problem 1∥gi (Ci) as a Shortest Path Problem
    Paluch, Stanislav
    Janosikova, Alzbeta
    Ruzicka, Vendelin
    Urbanicova, Ivana
    MATHEMATICAL METHODS IN ECONOMICS 2013, PTS I AND II, 2013, : 685 - 691
  • [5] A hybrid algorithm for flow shop scheduling problem
    Zhang, Changsheng
    Sun, Jigui
    Ning, Jiaxu
    Yang, Qingyun
    2008 PROCEEDINGS OF INFORMATION TECHNOLOGY AND ENVIRONMENTAL SYSTEM SCIENCES: ITESS 2008, VOL 1, 2008, : 182 - 188
  • [6] A novel metaheuristic approach for the flow shop scheduling problem
    Nearchou, AC
    ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2004, 17 (03) : 289 - 300
  • [7] A tabu search approach for the flow shop scheduling problem
    Ben-Daya, M
    Al-Fawzan, M
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 109 (01) : 88 - 95
  • [8] Improved approximation algorithms for the combination problem of parallel machine scheduling and path
    Li Guan
    Jianping Li
    Weidong Li
    Junran Lichen
    Journal of Combinatorial Optimization, 2019, 38 : 689 - 697
  • [9] Improved approximation algorithms for the combination problem of parallel machine scheduling and path
    Guan, Li
    Li, Jianping
    Li, Weidong
    Lichen, Junran
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (03) : 689 - 697
  • [10] Determining optimal combination of genetic operators for flow shop scheduling
    Wang, Ling
    Zhang, Liang
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2006, 30 (3-4) : 302 - 308
12345