The coupled unit-time operations problem on identical parallel machines with respect to the makespan

DOI10.1016/J.ORL.2013.11.006MaRDI QIDQ1667166zbMATH OpenOpenAlexFDO

Authors Djamal Rebaine, Alix Munier-Kordon

Publication date 27 August 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2013.11.006

zbMATH Keywords

time delaysmakespanworst-case analysisspecial casecoupled operations

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)

Recommendations

• The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan
• Two-machine flowshop scheduling problem with coupled-operations
• An improved approximation algorithm for the coupled-task scheduling problem with equal exact delays
• Approximation algorithms for coupled task scheduling minimizing the sum of completion times
• Minimizing makespan subject to minimum total flow-time on identical parallel machines

Cites work

• A note on scheduling identical coupled tasks in logarithmic time
• An exact algorithm for scheduling identical coupled tasks
• Complexity results for single-machine problems with positive finish-start time-lags
• Heuristics for a coupled-operation scheduling problem
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Polynomial-time algorithms for scheduling problem for coupled-tasks in presence of treatment tasks
• Scheduling for a multifunction phased array radar system
• Scheduling of coupled tasks and one-machine no-wait robotic cells
• Scheduling of coupled tasks with unit processing times

Cited in

(5)

• Two-machine flowshop scheduling problem with coupled-operations
• FPTAS for the two identical parallel machine problem with a single operator under the free changing mode
• Parallel machine scheduling with a simultaneity constraint and unit-length jobs to minimize the makespan
• Minimizing total completion time on parallel machines with unit length jobs that need one additional resource
• The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan

This page was built for publication: The coupled unit-time operations problem on identical parallel machines with respect to the makespan

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