Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem

DOI10.1007/S40314-016-0370-4MaRDI QIDQ725705zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 2 August 2018

Published in Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s40314-016-0370-4

zbMATH Keywords

branch-and-bound algorithmdynamic programminginteger programmingschedulingheuristic algorithmtardy/lost penalty

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Mixed integer programming (90C11)

Recommendations

• The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm
• An exact method to minimize the number of tardy jobs in single machine scheduling
• An algorithm to program a single machine with penalties for earliness and tardiness.
• AN EXACT APPROACH FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLY AND QUADRATIC TARDY PENALTIES
• A single machine scheduling problem with earliness/tardiness and starting time penalties under a common due date

Cites work

• scientific article; zbMATH DE number 5345853 (Why is no real title available?)
• scientific article; zbMATH DE number 167292 (Why is no real title available?)
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 1302193 (Why is no real title available?)
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• A note on ``Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
• A survey on offline scheduling with rejection
• An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
• An algorithm for insertion of idle time in the single-machine scheduling problem with convex cost functions
• An exact approach for scheduling jobs with regular step cost functions on a single machine
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• Approximation algorithms for scheduling a single machine to minimize total late work
• Due date assignments and scheduling a single machine with a general earliness/tardiness cost function
• General stochastic single-machine scheduling with regular cost functions
• Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs
• 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
• Scheduling with monotonous earliness and tardiness penalties
• Single Machine Scheduling to Minimize Total Late Work
• Single machine scheduling to minimize total weighted tardiness
• Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
• Techniques for scheduling with rejection
• The single-machine total tardiness scheduling problem: review and extensions

Cited in

(2)

• Research on construction and application for the model of multistage job shop scheduling problem
• Heuristics for multimachine minmax scheduling problems with general earliness and tardiness costs

This page was built for publication: Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q725705)