An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem

DOI10.1007/978-1-4614-1123-9_2zbMath1355.90031OpenAlexW2206876514MaRDI QIDQ2958666

Shunji Tanaka

Publication date: 3 February 2017

Published in: Just-in-Time Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4614-1123-9_2

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

An iterative dynamic programming approach for the temporal knapsack problem, A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties, A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Preemption in single machine earliness/tardiness scheduling
• A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates
• A time indexed formulation of non-preemptive single machine scheduling problems
• A dynamic programming method for single machine scheduling
• An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
• A polyhedral approach to single-machine scheduling problems.
• Optimal timing of a sequence of tasks with general completion costs
• Using short-term memory to minimize the weighted number of late jobs on a single machine.
• A branch and bound approach for single machine scheduling with earliness and tardiness penalties
• An exact algorithm for single-machine scheduling without machine idle time
• Algorithms for a class of single-machine weighted tardiness and earliness problems
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
• The one-machine problem with earliness and tardiness penalties
• Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints
• A branch and bound procedure to minimize mean absolute lateness on a single processor
• An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
• New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• State-space relaxation procedures for the computation of bounds to routing problems
• Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates
• A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• Single-machine scheduling with early and tardy completion costs