Lower bounds for parallel machine scheduling problems
From MaRDI portal
Summary: We study the parallel machine scheduling problem with release dates and consider several `min-sum' objective functions including total weighted tardiness, total tardiness, total weighted completion time and total completion time. We describe several lower bounds for these problems, most of them being original ones. We provide experimental results to compare these lower bounds according to their quality and of their computational time requirement.
Recommendations
- Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates
- Tight bounds for the identical parallel machine scheduling problem
- Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions
- Lower bounds for scheduling on identical parallel machines with heads and tails
- A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates
Cited in
(27)- Note on Shim and Kim's lower bounds for scheduling on identical parallel machines to minimize total tardiness
- On lower bounds on the minimum maximum lateness on one machine subject to release date
- Improved bounds on relaxations of a parallel machine scheduling problem
- A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals
- Lower bounds on precedence-constrained scheduling for parallel processors.
- On lower and upper bounds for single machine parallel batch scheduling
- Multi-machine scheduling lower bounds using decision diagrams
- Lower bounds for uniform machine scheduling using decision diagrams
- A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems
- Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods
- Scheduling jobs on parallel machines to minimize a regular step total cost function
- Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates
- Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time
- Lower bounds for the head-body-tail problem on parallel machines: a computational study of the multiprocessor flow shop
- Branch-and-bound algorithm for total weighted tardiness minimization on parallel machines under release dates assumptions
- scientific article; zbMATH DE number 4191384 (Why is no real title available?)
- Bounds for naive multiple machine scheduling with release times and deadlines
- Tight bounds for the identical parallel machine scheduling problem
- An almost tight lower bound for the scheduling problem to meet two min-sum objectives
- Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
- Lower bounds for scheduling on identical parallel machines with heads and tails
- Dynamic scheduling of patients in emergency departments
- Range of lower bounds
- Measuring the slack between lower bounds for scheduling on parallel machines
- An improved discrete optimisation procedure with comparison to constraint programming
- Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem
- On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
This page was built for publication: Lower bounds for parallel machine scheduling problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q947338)
