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.90022OpenAlexW2055770719MaRDI 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
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)
Related Items (22)
A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem ⋮ Tower-of-sets analysis for the Kise-Ibaraki-Mine algorithm ⋮ Minimizing the weighted number of tardy jobs on a single machine with release dates ⋮ A survey of single machine scheduling to minimize weighted number of tardy jobs ⋮ Algorithms for Necklace Maps ⋮ A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem ⋮ A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty ⋮ A global constraint for total weighted completion time for unary resources ⋮ New dominance rules and exploration strategies for the \(1|r _{i}|\sum U _{i }\) scheduling problem ⋮ Scheduling jobs on parallel machines to minimize a regular step total cost function ⋮ Optimality proof of the Kise-Ibaraki-Mine algorithm ⋮ Changeover formulations for discrete-time mixed-integer programming scheduling models ⋮ Fuzzy reasoning based on a new fuzzy rough set and its application to scheduling problems ⋮ A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints ⋮ Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates ⋮ Mathematical models for preemptive shop scheduling problems ⋮ On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation ⋮ 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. ⋮ 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
This page was built for publication: A branch and bound to minimize the number of late jobs on a single machine with release time constraints