A branch and bound to minimize the number of late jobs on a single machine with release time constraints
From MaRDI portal
Publication:1869685
DOI10.1016/S0377-2217(01)00353-8zbMath1037.90022MaRDI QIDQ1869685
Éric Pinson, Philippe Baptiste, Laurent Peridy
Publication date: 28 April 2003
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0377-2217(01)00353-8
branch and bound; dominance properties; elimination rules; number of late jobs; Single machine scheduling
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B35: Deterministic scheduling theory in operations research
Related Items
On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation, A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty, A survey of single machine scheduling to minimize weighted number of tardy jobs, New dominance rules and exploration strategies for the \(1|r _{i}|\sum U _{i }\) scheduling problem, A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem, Minimizing the weighted number of tardy jobs on a single machine with release dates, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms, A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem, Changeover formulations for discrete-time mixed-integer programming scheduling models, Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance, Mathematical models for preemptive shop scheduling problems, Scheduling a single machine to minimize a regular objective function under setup constraints, Using short-term memory to minimize the weighted number of late jobs on a single machine., A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints, Tower-of-sets analysis for the Kise-Ibaraki-Mine algorithm, A global constraint for total weighted completion time for unary resources, Scheduling jobs on parallel machines to minimize a regular step total cost function, Optimality proof of the Kise-Ibaraki-Mine algorithm, Fuzzy reasoning based on a new fuzzy rough set and its application to scheduling problems, A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates, Algorithms for Necklace Maps, Empirically discovering dominance relations for scheduling problems using an evolutionary algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A practical use of Jackson's preemptive schedule for solving the job shop problem
- A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
- Minimizing late jobs in the general one machine scheduling problem
- Characterizing the set of feasible sequences for n jobs to be carried out on a single machine
- The one-machine sequencing problem
- An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
- A branch and bound algorithm for the job-shop scheduling problem
- The job-shop problem and immediate selection
- Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the `Tower of Sets' property
- Adjustment of heads and tails for the job-shop problem
- Constraint-based scheduling: Applying constraint programming to scheduling problems.
- Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
- Solving various weighted matching problems with constraints
- An Algorithm for Solving the Job-Shop Problem
- A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
- A new approach to computing optimal schedules for the job-shop scheduling problem
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
