Complexity results for scheduling chains on a single machine
From MaRDI portal
Publication:1142687
DOI10.1016/0377-2217(80)90111-3zbMath0439.90041OpenAlexW2065816722MaRDI QIDQ1142687
Jan Karel Lenstra, Alexander H. G. Rinnooy Kan
Publication date: 1980
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: http://ageconsearch.umn.edu/record/272176
computational complexitysingle machineNP-hard problemstotal weighted tardinesschain-like precedence constraintsdeterministic sequencing problemsminimization of late jobsscheduling chainstotal weighted completion time criterionunit-time jobs
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)
Related Items
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Approximate Deadline-Scheduling with Precedence Constraints, Network construction problems with due dates, A survey of single machine scheduling to minimize weighted number of tardy jobs, Packing different-sized circles into a rectangular container, Complexity results for scheduling chains on a single machine, Equitable scheduling on a single machine, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Single-machine scheduling of multiple projects with controllable processing times, How useful are preemptive schedules?, Two schemes of the branch-and-bound method for a flow shop total weighted tardiness minimization problem, Open shop scheduling problems with late work criteria., A note on the maximum number of on-time jobs on parallel identical machines., On the complexity of generalized due date scheduling problems, A metric approach for scheduling problems with minimizing the maximum penalty, Single-machine scheduling with supporting tasks, On single-machine scheduling without intermediate delays, A note on competing-agent Pareto-scheduling, Single Machine Preemptive Scheduling to Minimize the Weighted Number of Late Jobs with Deadlines and Nested Release/Due Date Intervals, New heuristics for packing unequal circles into a circular container, Minimizing the number of tardy jobs with precedence constraints and agreeable due dates, Polyhedral results for position-based scheduling of chains on a single machine, Packing cylinders and rectangular parallelepipeds with distances between them into a given region, The simple plant location problem: Survey and synthesis, An improved algorithm for the packing of unequal circles within a larger containing circle, On scheduling cycle shops: Classification, complexity and approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity results for scheduling chains on a single machine
- Optimal scheduling for two-processor systems
- On the Computational Complexity of Combinatorial Problems
- Scheduling Tasks with Nonuniform Deadlines on Two Processors
- Complexity of Scheduling under Precedence Constraints
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- `` Strong NP-Completeness Results
- Computational Complexity of Discrete Optimization Problems
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
