A heuristic for preemptive scheduling with set-up times

DOI10.1007/BF02238747MaRDI QIDQ1202243zbMATH OpenFDO

Authors Zhongliang Yu, Gerhard J. Woeginger

Publication date 25 February 1993

Published in Computing (Search for Journal in Brave)

zbMATH Keywords

heuristicsNP-completeidentical parallel machinespreemptive schedulingpolynomial time approximation algorithm\(m\) parallel machinesconstant (job- and machine-independent) set-up timesworst- case analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times
• Lot-sizing scheduling with batch setup times
• Non-preemptive scheduling with setup times: a PTAS
• A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times
• A heuristic algorithm for minimizing mean flow time with unit setups

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• On the Complexity of Scheduling with Batch Setup Times
• Performance Guarantees for Scheduling Algorithms
• Scheduling with deadlines and loss functions
• Time bounds for selection

Cited in

(14)

• Scheduling in switching networks with set-up delays
• Strategic scheduling games: equilibria and efficiency
• Non-preemptive scheduling with setup times: a PTAS
• Improved heuristics for the early/tardy scheduling problem with no idle time
• scientific article; zbMATH DE number 1416517 (Why is no real title available?)
• Survey of scheduling research involving setup times
• A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times
• Non-preemptive scheduling on machines with setup times
• Approximation algorithms for problems in scheduling with set-ups
• Bounds for parallel machine scheduling with predefined parts of jobs and setup time
• Heuristics to Schedule Service Engineers within Time Windows
• A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times
• Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times
• A heuristic algorithm for minimizing mean flow time with unit setups

This page was built for publication: A heuristic for preemptive scheduling with set-up times

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