Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs

DOI10.1137/0207031zbMath0386.68050OpenAlexW2075889702MaRDI QIDQ4167580

Publication date: 1978

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0207031

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Algorithms in computer science (68W99)

Related Items

Unnamed Item ⋮ Linear time approximation schemes for vehicle scheduling problems ⋮ Scheduling with batching: Minimizing the weighted number of tardy jobs ⋮ Scheduling with few changes ⋮ Approximating the minmax rooted-tree cover in a tree ⋮ Scheduling two job families on a single machine with two competitive agents ⋮ Integer knapsack problems with set-up weights ⋮ The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard ⋮ Batch scheduling to minimize maximum lateness ⋮ Lot-size scheduling of two types of jobs on identical machines ⋮ Single machine batch scheduling problem with family setup times and release dates to minimize makespan ⋮ A survey of single machine scheduling to minimize weighted number of tardy jobs ⋮ Minimizing maximum tardiness on a single machine with family setup times and machine disruption ⋮ A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness ⋮ Scheduling with batching: A review ⋮ Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times ⋮ Branch and bound algorithms for single machine scheduling with batching to minimize the number of late jobs ⋮ Approximation algorithms for problems in scheduling with set-ups ⋮ An online algorithm for a problem in scheduling with set-ups and release times ⋮ Impact of sequence-dependent setup time on job shop scheduling performance ⋮ Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness ⋮ Minimizing L _max for the single machine scheduling problem with family set-ups ⋮ A heuristic approach for single-machine scheduling with due dates and class setups. ⋮ A note on the complexity of family scheduling to minimize the number of late jobs ⋮ Solving the medium newspaper production/distribution problem ⋮ Minmax Tree Cover in the Euclidean Space ⋮ Batch sizing and job sequencing on a single machine ⋮ Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs ⋮ A forward branch-and-search algorithm and forecast horizon results for the changeover scheduling problem ⋮ Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines ⋮ Scheduling with families of jobs and delivery coordination under job availability ⋮ A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree ⋮ Batch scheduling and common due-date assignment on a single machine ⋮ Using profit maximizing scheduling models to structure operational trade-offs and manufacturing strategy issues ⋮ On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times ⋮ Minimizing maximum lateness with job families ⋮ A polynomial algorithm for lot-size scheduling of two type tasks. ⋮ Local search procedures for improving feasible solutions to the sequential ordering problem ⋮ The coordination of scheduling and batch deliveries