An exact algorithm for single-machine scheduling without machine idle time

DOI10.1007/s10951-008-0093-5zbMath1182.90051OpenAlexW1982727680MaRDI QIDQ2268522

Shuji Fujikuma, Shunji Tanaka, Mituhiko Araki

Publication date: 8 March 2010

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-008-0093-5

zbMATH Keywords

Lagrangian relaxationsingle-machine schedulingexact algorithmtime-indexed formulationsuccessive sublimation dynamic programming method

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Production models (90B30) Dynamic programming (90C39)

Related Items (30)

Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ The two-machine flowshop total completion time problem: branch-and-bound algorithms based on network-flow formulation ⋮ Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times ⋮ An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times ⋮ Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date ⋮ Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems ⋮ Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ On the exact solution of a large class of parallel machine scheduling problems ⋮ Scheduling with time-dependent discrepancy times ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ Minimizing value-at-risk in single-machine scheduling ⋮ Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems ⋮ Precedence theorems and dynamic programming for the single-machine weighted tardiness problem ⋮ Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times ⋮ An exact approach for scheduling jobs with regular step cost functions on a single machine ⋮ Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem ⋮ Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment ⋮ \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees ⋮ 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 ⋮ Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime ⋮ Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem

Cites Work

• Formulating the single machine sequencing problem with release dates as a mixed integer program
• On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
• A time indexed formulation of non-preemptive single machine scheduling problems
• A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem
• 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.
• Using short-term memory to minimize the weighted number of late jobs on a single machine.
• 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
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem

This page was built for publication: An exact algorithm for single-machine scheduling without machine idle time