Complexity results for scheduling chains on a single machine

DOI10.1016/0377-2217(80)90111-3MaRDI QIDQ1142687zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

computational complexitysingle machineNP-hard problemstotal weighted tardinesschain-like precedence constraintsdeterministic sequencing problemsminimization of late jobsscheduling chainstotal weighted completion time criterionunit-time jobs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cites work

• scientific article; zbMATH DE number 3471786 (Why is no real title available?)
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Complexity of Scheduling under Precedence Constraints
• Complexity results for scheduling chains on a single machine
• Computational Complexity of Discrete Optimization Problems
• On the Computational Complexity of Combinatorial Problems
• Optimal scheduling for two-processor systems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• `` Strong NP-Completeness Results

Cited in

(26)

• Minimizing the number of tardy jobs with precedence constraints and agreeable due dates
• New heuristics for packing unequal circles into a circular container
• Two schemes of the branch-and-bound method for a flow shop total weighted tardiness minimization problem
• Single machine preemptive scheduling to minimize the weighted number of late jobs with deadlines and nested release/due date intervals
• A note on competing-agent Pareto-scheduling
• Open shop scheduling problems with late work criteria.
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Single-machine scheduling with supporting tasks
• Packing cylinders and rectangular parallelepipeds with distances between them into a given region
• A metric approach for scheduling problems with minimizing the maximum penalty
• Approximate Deadline-Scheduling with Precedence Constraints
• A note on the maximum number of on-time jobs on parallel identical machines.
• Network construction problems with due dates
• How useful are preemptive schedules?
• On the complexity of generalized due date scheduling problems
• Complexity results for scheduling chains on a single machine
• A survey of single machine scheduling to minimize weighted number of tardy jobs
• Packing different-sized circles into a rectangular container
• The simple plant location problem: Survey and synthesis
• An improved algorithm for the packing of unequal circles within a larger containing circle
• On single-machine scheduling without intermediate delays
• Polyhedral results for position-based scheduling of chains 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
• Equitable scheduling on a single machine
• On scheduling cycle shops: Classification, complexity and approximation

This page was built for publication: Complexity results for scheduling chains on a single machine

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