Polynomial-time approximation schemes for scheduling problems with time lags

DOI10.1007/s10951-009-0134-8zbMath1201.90094OpenAlexW1966192374MaRDI QIDQ600835

Xiandong Zhang, Steef L. van de Velde

Publication date: 3 November 2010

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-009-0134-8

zbMATH Keywords

machine schedulingpolynomial-time approximation scheme (PTAS)time lagsapproximability

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (3)

Two-machine interval shop scheduling with time lags ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Coupled task scheduling with exact delays: literature review and models

Cites Work

• Unnamed Item
• Complexity results for flow-shop and open-shop scheduling problems with transportation delays
• Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
• A heuristic for the two-machine open-shop scheduling problem with transportation times
• A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
• A polynomial approximation scheme for problem \(F2/r_ j/C_{\text{max}}\)
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags
• Sequencing n Jobs on Two Machines with Arbitrary Time Lags
• Optimal two- and three-stage production schedules with setup times included
• Two-machine open shop scheduling with special transportation times
• Heuristics for a coupled-operation scheduling problem
• Deterministic Scheduling with Pipelined Processors
• Scheduling the Open Shop to Minimize Mean Flow Time
• Open shop scheduling with delays
• Open Shop Scheduling to Minimize Finish Time
• The Complexity of Flowshop and Jobshop Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Polynomial Approximation Scheme for a Constrained Flow-Shop Scheduling Problem
• Shop Problems With Two Machines and Time Lags
• Algorithms and Computation
• Algorithms and Computation
• A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum Delays

This page was built for publication: Polynomial-time approximation schemes for scheduling problems with time lags