A combination of flow shop scheduling and the shortest path problem

DOI10.1007/S10878-013-9670-4zbMATH Open1328.90129arXiv1309.0081OpenAlexW2160962818MaRDI QIDQ2354293FDOQ2354293

Authors: Kameng Nip, Fabrice Talla Nobibon, Roel Leus, Zhenbo Wang 

Publication date: 10 July 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1309.0081

Recommendations

• Combination of two-machine flow shop scheduling and shortest path problems
• Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms
• A study on several combination problems of classic shop scheduling and shortest path
• The hybrid flow shop scheduling problem
• scientific article; zbMATH DE number 1911010
• A branch and bound algorithm for the flow-shop scheduling problem
• A flexible flowshop problem with total flow time minimization
• A HYBRID TWO-STAGE FLOWSHOP SCHEDULING PROBLEM
• Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time
• A FLOWSHOP SCHEDULING ALGORITHM TO MINIMIZE TOTAL FLOWTIME

zbMATH Keywords

approximation algorithmshortest pathflow shop schedulingcombination of optimization problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Cites Work

• Network flows. Theory, algorithms, and applications.
• A note on two problems in connexion with graphs
• Title not available (Why is that?)
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Title not available (Why is that?)
• Robust discrete optimization and its applications
• Optimal two- and three-stage production schedules with set-up time included
• The Complexity of Flowshop and Jobshop Scheduling
• Combination of parallel machine scheduling and vertex cover
• Approximability of flow shop scheduling
• Flowshop and Jobshop Schedules: Complexity and Approximation
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• A concise survey of efficiently solvable special cases of the permutation flow-shop problem
• A New Heuristic for Three-Machine Flow Shop Scheduling
• Scheduling with incompatible jobs
• Title not available (Why is that?)

Cited In (8)

• On the approximability of the two-phase knapsack problem
• Optimal path selection approach for fuzzy reliable shortest path problem
• Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families
• Vertex cover meets scheduling
• Combination of two-machine flow shop scheduling and shortest path problems
• Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms
• A study on several combination problems of classic shop scheduling and shortest path
• Improved approximation algorithms for the combination problem of parallel machine scheduling and path

This page was built for publication: A combination of flow shop scheduling and the shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354293)