Title: A combination of flow shop scheduling and the shortest path problem
Authors: Nip, Kameng ×
Wang, Zhenbo #
Talla Nobibon, Fabrice #
Leus, Roel #
Issue Date: 2015
Publisher: Kluwer Academic Publishers
Series Title: Journal of Combinatorial Optimization vol:29 issue:1 pages:36-52
Abstract: 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
ISSN: 1382-6905
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
10.1007_s10878-013-9670-4.pdfA combination of flow shop scheduling and the shortest path problem Published 917KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science