Approximation algorithms for scheduling a single machine to minimize total late work
From MaRDI portal
Publication:1196210
DOI10.1016/0167-6377(92)90001-JzbMath0767.90039OpenAlexW2009816147MaRDI QIDQ1196210
Luk N. Van Wassenhove, Chris N. Potts
Publication date: 17 December 1992
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(92)90001-j
single machineworst-case analysisapproximation algorithmstotal late workinteger due dateinteger processing timetruncated enumeration
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items (28)
Semi-online scheduling on two identical machines with a common due date to maximize total early work ⋮ Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays ⋮ Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date ⋮ Minimizing total weighted late work on a single-machine with non-availability intervals ⋮ Scheduling imprecise computation tasks with \(0/1\)-constraint ⋮ Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work ⋮ A common approximation framework for early work, late work, and resource leveling problems ⋮ Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work ⋮ Bicriterion Pareto‐scheduling of equal‐length jobs on a single machine related to the total weighted late work ⋮ A no-delay single machine scheduling problem to minimize total weighted early and late work ⋮ Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work ⋮ A survey of due-date related single-machine with two-agent scheduling problem ⋮ A new perspective on single-machine scheduling problems with late work related criteria ⋮ Single-machine scheduling with multi-agents to minimize total weighted late work ⋮ A two-agent single-machine scheduling problem with late work criteria ⋮ Open shop scheduling problems with late work criteria. ⋮ Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals ⋮ A DUAL CRITERIA PREEMPTIVE SCHEDULING PROBLEM FOR MINIMAX ERROR OF IMPRECISE COMPUTATION TASKS ⋮ Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date ⋮ The two-machine flow-shop problem with weighted late work criterion and common due date ⋮ Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work ⋮ Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem ⋮ A Branch-and-Bound Algorithm for Two-Agent Scheduling with Learning Effect and Late Work Criterion ⋮ Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date ⋮ THE NP-HARDNESS OF MINIMIZING THE TOTAL LATE WORK ON AN UNBOUNDED BATCH MACHINE ⋮ Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ Two-machine flow shop scheduling with a common due date to maximize total early work
Cites Work
- Fast approximation algorithm for job sequencing with deadlines
- A fully polynomial approximation scheme for the total tardiness problem
- Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
- Single Machine Scheduling to Minimize Total Late Work
- Algorithms for Scheduling Independent Tasks
- Unnamed Item
This page was built for publication: Approximation algorithms for scheduling a single machine to minimize total late work
