Approximating the 2-machine flow shop problem with exact delays taking two values

DOI10.1007/S10898-019-00775-0zbMATH Open1442.90065arXiv1711.00081OpenAlexW2963657568WikidataQ128026758 ScholiaQ128026758MaRDI QIDQ2174271FDOQ2174271

Yanyan Li

Publication date: 21 April 2020

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

Abstract: In the $2$-Machine Flow Shop problem with exact delays the operations of each job are separated by a given time lag (delay). Leung et al. (2007) established that the problem is strongly NP-hard when the delays may have at most two different values. We present further results for this case: we prove that the existence of $(1.25-varepsilon)$-approximation implies P$=$NP and develop a $2$-approximation algorithm.

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

zbMATH Keywords

approximation algorithmflow shopscheduling problemapproximation factorexact delaysinapproximability lower bound

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cites Work

• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• Title not available (Why is that?)
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Interleaving two-phased jobs on a single machine
• Approximation algorithms for UET scheduling problems with exact delays
• Radar pulse interleaving for multi‐target tracking
• Approximation Algorithms for Scheduling Problems with Exact Delays
• SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS

This page was built for publication: Approximating the 2-machine flow shop problem with exact delays taking two values

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