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

DOI10.1007/S10898-019-00775-0MaRDI QIDQ2174271zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 21 April 2020

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

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)

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.

Recommendations

• SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS
• Approximation Algorithms for Scheduling Problems with Exact Delays
• A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum Delays
• Algorithms and Computation
• Minimizing Total Completion Time in Two-Machine Flow Shops with Exact Delays

Cites work

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

Cited in

(4)

• SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS
• Algorithms and Computation
• Approximation Algorithms for Scheduling Problems with Exact Delays
• A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum 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)