A branch and bound approach for single machine scheduling with earliness and tardiness penalties

DOI10.1016/S0898-1221(99)00130-3zbMath0931.90013OpenAlexW2013137873MaRDI QIDQ1963033

Pei-Chann Chang

Publication date: 20 January 2000

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0898-1221(99)00130-3

zbMATH Keywords

complexitybranch and boundsingle machine scheduling

Mathematics Subject Classification ID

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

Related Items

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem ⋮ A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties ⋮ Minimizing total earliness and tardiness on a single machine using a hybrid heuristic ⋮ Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems ⋮ EA/G-GA for single machine scheduling problems with earliness/tardiness costs ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ Bi-objective single machine scheduling problem with stochastic processing times

Cites Work

• Single machine scheduling to minimize mean absolute lateness: A heuristic solution
• A decomposition algorithm for the single machine total tardiness problem
• Algorithms for a class of single-machine weighted tardiness and earliness problems
• Minimizing the sum of absolute lateness in single-machine and multimachine scheduling
• Minimizing the average deviation of job completion times about a common due date
• Sequencing with Earliness and Tardiness Penalties: A Review
• Minimizing mean absolute deviation of completion times about a common due date
• Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• The Single Machine Early/Tardy Problem
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates
• Single-machine scheduling with early and tardy completion costs