# A Combination of Flow Shop Scheduling and the Shortest Path Problem

Preprint · Kameng Nip, Zhenbo Wang, Fabrice Talla Nobibon, Roel Leus

- Archive id: arxiv:1309.0081
- Published: 2013-08-31
- arXiv: https://arxiv.org/abs/1309.0081
- Source URL: https://arxiv.org/abs/1309.0081
- PDF: https://arxiv.org/pdf/1309.0081
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.