On the complexity of coupled-task scheduling

DOI10.1016/S0166-218X(96)00041-8zbMath0873.90053OpenAlexW1966465131MaRDI QIDQ5961610

A. J. Orman, Chris N. Potts

Publication date: 25 February 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

single machinemakespansequencingpolynomial algorithmsNP-hardnesscoupled-task

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items (27)

Polynomial-time algorithms for scheduling problem for coupled-tasks in presence of treatment tasks ⋮ Coupled task scheduling with convex resource consumption functions ⋮ Scheduling of coupled tasks with unit processing times ⋮ Modelling for the control of a complex radar system ⋮ A binary search algorithm for the general coupled task scheduling problem ⋮ Some complexity and approximation results for coupled-tasks scheduling problem according to topology ⋮ A branch-and-bound algorithm for the coupled task problem ⋮ Approximation algorithms for coupled task scheduling minimizing the sum of completion times ⋮ The coupled task scheduling problem: an improved mathematical program and a new solution algorithm ⋮ Identical coupled task scheduling: polynomial complexity of the cyclic case ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ Approximation algorithms for UET scheduling problems with exact delays ⋮ Scheduling of coupled tasks and one-machine no-wait robotic cells ⋮ Minimizing flowtime for paired tasks ⋮ A note on scheduling identical coupled tasks in logarithmic time ⋮ Scheduling coupled-operation jobs with exact time-lags ⋮ Coupled task scheduling with exact delays: literature review and models ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Two machines flow shop with reentrance and exact time lag ⋮ Improved analysis of an algorithm for the coupled task problem with UET jobs ⋮ Scheduling for a multifunction phased array radar system ⋮ A first fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays ⋮ Scheduling coupled tasks with exact delays for minimum total job completion time ⋮ Coupled task scheduling with time-dependent processing times ⋮ Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints ⋮ Two-machine flowshop scheduling problem with coupled-operations ⋮ SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS

Cites Work

• Finding the median
• Optimal two- and three-stage production schedules with setup times included
• Scheduling coupled tasks
• `` Strong NP-Completeness Results
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Shop Problems With Two Machines and Time Lags

This page was built for publication: On the complexity of coupled-task scheduling