On the complexity of generalized due date scheduling problems

DOI10.1016/0377-2217(91)90149-PzbMath0742.90043OpenAlexW2090454346MaRDI QIDQ1175769

Nicholas G. Hall, Suresh P. Sethi, Chelliah Skriskandarajah

Publication date: 25 June 1992

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(91)90149-p

zbMATH Keywords

generalized due date scheduling

Mathematics Subject Classification ID

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

Related Items

Single machine scheduling with assignable due dates, A single machine scheduling with generalized and periodic due dates to minimize total deviation, A scatter search approach with dispatching rules for a joint decision of cell formation and parts scheduling in batches, Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs, A greedy heuristic for solving scheduling problems with bounded rejection cost, Single machine scheduling with rejection and generalized parameters, A note: minmax due-date assignment problem with lead-time cost, Just-In-Time Scheduling with Generalized Due Dates and Identical Due Date Intervals, Minimizing late jobs in the general one machine scheduling problem, Optimal control strategies for single-machine family scheduling with sequence-dependent batch setup and controllable processing times, Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty, Minimizing tardiness scheduling measures with generalized due-dates and a maintenance activity, Order acceptance and scheduling with delivery under generalized parameters, Scheduling with due date assignment under special conditions on job processing, Single machine scheduling with delivery dates and cumulative payoffs, A note on the SPT heuristic for solving scheduling problems with generalized due dates, Performance guarantees for a scheduling problem with common stepwise job payoffs, Batch scheduling of deteriorating reworkables, Unary NP-hardness of minimizing total weighted tardiness with generalized due dates, Minimizing total late work on a single machine with generalized due-dates, Strong NP-hardness of minimizing total deviation with generalized and periodic due dates, Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty, Two-Machine Ordered Flow Shop Scheduling with Generalized Due Dates, Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates, Unnamed Item, On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates, A survey of the state-of-the-art of common due date assignment and scheduling research, Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates, Scheduling with generalized and periodic due dates under single- and two-machine environments

Cites Work

• Complexity results for scheduling chains on a single machine
• Minimizing Total Tardiness on One Machine is NP-Hard
• A Note on Open Shop Preemptive Schedules
• Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
• Minimizing Maximum Lateness in a Two-Machine Open Shop
• Minimizing Total Tardiness on a Single Machine with Precedence Constraints
• Open Shop Scheduling to Minimize Finish Time
• Complexity of Scheduling under Precedence Constraints
• Flowshop and Jobshop Schedules: Complexity and Approximation
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Some simple scheduling algorithms
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item