Optimality proof of the Kise-Ibaraki-Mine algorithm

DOI10.1007/s10951-010-0210-0zbMath1280.90060OpenAlexW2008693877MaRDI QIDQ2434284

Shanlin Li, Guochun Tang, Zhi-Long Chen

Publication date: 5 February 2014

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-010-0210-0

zbMATH Keywords

algorithmproduction schedulingsingle machine deterministic sequencingproof of optimality

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Unnamed Item
• Unnamed Item
• A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the `Tower of Sets' property
• 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
• A Note on the Optimality Proof of the Kise-Ibaraki-Mine Algorithm
• A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs

This page was built for publication: Optimality proof of the Kise-Ibaraki-Mine algorithm