An exact algorithm for single-machine scheduling without machine idle time
From MaRDI portal
Publication:2268522
DOI10.1007/S10951-008-0093-5zbMATH Open1182.90051OpenAlexW1982727680MaRDI QIDQ2268522FDOQ2268522
Authors: Shunji Tanaka, Shuji Fujikuma, 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
Recommendations
- A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
- An exact algorithm for the precedence-constrained single-machine scheduling problem
- An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem
- An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
- A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
exact algorithmLagrangian relaxationtime-indexed formulationsingle-machine schedulingsuccessive sublimation dynamic programming method
Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Production models (90B30)
Cites Work
- 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
- Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
- Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I
- A dynamic programming method for single machine scheduling
- A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
- Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
- Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem
- Formulating the single machine sequencing problem with release dates as a mixed integer program
- 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
- State-space relaxation procedures for the computation of bounds to routing problems
- An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
- New exact algorithms for one-machine earliness-tardiness scheduling
- On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
Cited In (32)
- An exact block algorithm for no-idle RPQ problem
- A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
- Minimizing value-at-risk in single-machine scheduling
- A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties
- Scheduling with time-dependent discrepancy times
- Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem
- On the exact solution of a large class of parallel machine scheduling problems
- Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem
- An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem
- Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
- Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty
- \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
- Exact algorithms for single-machine scheduling with time windows and precedence constraints
- An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
- Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times
- Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times
- The two-machine flowshop total completion time problem: branch-and-bound algorithms based on network-flow formulation
- Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment
- A bucket indexed formulation for nonpreemptive single machine scheduling problems
- Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
- An algorithm for insertion of idle time in the single-machine scheduling problem with convex cost functions
- An iterative dynamic programming approach for the temporal knapsack problem
- Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date
- A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime
- 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
- A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems
- An exact approach for scheduling jobs with regular step cost functions on a single machine
- Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers
- An exact algorithm for the precedence-constrained single-machine scheduling problem
- Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models
- Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems
This page was built for publication: An exact algorithm for single-machine scheduling without machine idle time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268522)
