Exact algorithms for single-machine scheduling with time windows and precedence constraints

DOI10.1007/S10951-015-0428-YMaRDI QIDQ310349zbMATH OpenOpenAlexFDO

Authors Morteza Davari, Roel Leus, Fabrice Talla Nobibon, Erik Demeulemeester

Publication date 8 September 2016

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

Full work available at URL https://lirias.kuleuven.be/handle/123456789/494595

zbMATH Keywords

branch and boundmixed integer programmingsingle-machine scheduling

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Mixed integer programming (90C11)

Recommendations

• An exact algorithm for the precedence-constrained single-machine scheduling problem
• Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints
• An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time.
• A branch and bound algorithm to minimize total weighted tardiness on a single processor
• An exact method to minimize the number of tardy jobs in single machine scheduling

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem
• A Dynamic Programming Approach to Sequencing Problems
• A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time
• A dynamic programming method for single machine scheduling
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
• A new dominance rule to minimize total weighted tardiness with unequal release dates.
• A survey of algorithms for the single machine total weighted tardiness scheduling problem
• An algorithm for single machine sequencing with deadlines to minimize total weighted completion time
• An algorithm for single machine sequencing with release dates to minimize total weighted completion time
• An exact algorithm for single-machine scheduling without machine idle time
• An exact algorithm for the precedence-constrained single-machine scheduling problem
• An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time.
• Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates
• Dual decomposition of a single-machine scheduling problem
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling
• Maximum series-parallel subgraph
• Minimizing Weighted Completion Times with Deadlines
• Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs
• Optimal Reduction of Two-Terminal Directed Acyclic Graphs
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Production planning and industrial scheduling. Examples, case studies and applications.
• Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer
• Rangen: A random network generator for activity-on-the-node networks
• Scheduling
• Scheduling problems in parallel systems for telecommunications
• Scheduling with release dates on a single machine to minimize total weighted completion time
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Single machine scheduling with deadlines, release and due dates
• Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The Recognition of Series Parallel Digraphs
• The concrete delivery problem
• The two-machine flow shop problem with arbitrary precedence relations

Cited in

(7)

• Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
• Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints
• Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers
• Minimizing makespan on a single machine with release dates and inventory constraints
• An exact algorithm for the precedence-constrained single-machine scheduling problem

Describes a project that uses

Uses Software

• RanGen

This page was built for publication: Exact algorithms for single-machine scheduling with time windows and precedence constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q310349)