Single machine scheduling with discretely controllable processing times

DOI10.1016/S0167-6377(97)00010-2zbMath0888.90088OpenAlexW2021910328MaRDI QIDQ1373460

Qing Lu, Guochun Tang, Zhi-Long Chen

Publication date: 19 November 1997

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(97)00010-2

zbMATH Keywords

single machinemakespantotal completion timecontrollable processing timesmaximum tardinesspseudo-polynomial dynamic programming algorithmssum of the total processing cost

Mathematics Subject Classification ID

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

Related Items

Approximation schemes for parallel machine scheduling problems with controllable processing times ⋮ Single-machine scheduling with trade-off between number of tardy jobs and compression cost ⋮ A survey of scheduling with controllable processing times ⋮ Considering manufacturing cost and scheduling performance on a CNC turning machine ⋮ Weighted throughput in a single machine preemptive scheduling with continuous controllable processing times ⋮ Single machine scheduling with a variable common due date and resource-dependent processing times. ⋮ Single machine batch scheduling with jointly compressible setup and processing times. ⋮ A Review for Submodular Optimization on Machine Scheduling Problems ⋮ Single-machine scheduling with machine unavailability periods and resource dependent processing times ⋮ Approximation schemes for job shop scheduling problems with controllable processing times ⋮ Pseudo-polynomial dynamic programming for an integrated due date assignment, resource allocation, production, and distribution scheduling model in supply chain scheduling ⋮ Single machine scheduling with resource dependent release times and processing times ⋮ Single machine group scheduling with resource dependent setup and processing times ⋮ Group scheduling with controllable setup and processing times: minimizing total weighted completion time ⋮ A \(\frac 32\)-approximation algorithm for parallel machine scheduling with controllable processing times ⋮ SCHEDULING WITH DISCRETELY COMPRESSIBLE RELEASE DATES TO MINIMIZE MAKESPAN ⋮ Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling ⋮ Single machine batch scheduling with resource dependent setup and processing times ⋮ Minimizing total tardiness on a single machine with controllable processing times ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems

Cites Work

• Unnamed Item
• A survey of results for sequencing problems with controllable processing times
• A bicriterion approach to time/cost trade-offs in sequencing
• Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: Worst-case analysis
• Single-machine sequencing with controllable processing times
• Two parallel machine sequencing problems involving controllable job processing times
• Single-machine scheduling with trade-off between number of tardy jobs and resource allocation
• Sequencing with Earliness and Tardiness Penalties: A Review
• Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine
• Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem
• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• `` Strong NP-Completeness Results
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Multiple Variable-Speed Machines
• Flow Shop Scheduling with Resource Flexibility
• Scheduling to minimize the total compression and late costs
• Reducibility among Combinatorial Problems
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs