Using short-term memory to minimize the weighted number of late jobs on a single machine.

DOI10.1016/S0377-2217(02)00438-1zbMath1037.90033OpenAlexW2067913114MaRDI QIDQ1812007

Éric Pinson, David Rivreau, Laurent Peridy

Publication date: 18 June 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(02)00438-1

zbMATH Keywords

Lagrangean relaxationDynamic programmingSchedulingBranch-and-boundRelease timesTime-indexed formulationWeighted number of late jobs

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem ⋮ The two-machine flowshop total completion time problem: branch-and-bound algorithms based on network-flow formulation ⋮ Minimizing the weighted number of tardy jobs on a single machine with release dates ⋮ Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties ⋮ A survey of single machine scheduling to minimize weighted number of tardy jobs ⋮ A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ New dominance rules and exploration strategies for the \(1|r _{i}|\sum U _{i }\) scheduling problem ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints ⋮ A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates ⋮ Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates ⋮ An exact approach for scheduling jobs with regular step cost functions on a single machine ⋮ An exact algorithm for single-machine scheduling without machine idle time ⋮ Earliness-tardiness scheduling with setup considerations ⋮ P2P B&B and GA for the Flow-Shop Scheduling Problem ⋮ Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates

Cites Work

• 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
• The one-machine sequencing problem
• Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the `Tower of Sets' property
• Adjustment of heads and tails for the job-shop problem
• Genetic algorithms to minimize the weighted number of late jobs on a single machine.
• A branch and bound to minimize the number of late jobs on a single machine with release time constraints
• An exact method to minimize the number of tardy jobs in single machine scheduling
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs
• Algorithms for Scheduling Independent Tasks
• A dual algorithm for the one-machine scheduling problem
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• Validation of subgradient optimization
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs