An exact approach for scheduling jobs with regular step cost functions on a single machine

DOI10.1016/J.COR.2011.06.006zbMath1251.90134OpenAlexW2041634809MaRDI QIDQ1762077

Boris Detienne, Stéphane Dauzère-Pérès, Claude Yugma

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.06.006

zbMATH Keywords

Lagrangian relaxationexact methodone machine schedulingmultiple due datesstep cost functiontotal cost minimization

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (4)

The two-machine flowshop total completion time problem: branch-and-bound algorithms based on network-flow formulation ⋮ Performance guarantees for a scheduling problem with common stepwise job payoffs ⋮ Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem ⋮ Integration of scheduling and advanced process control in semiconductor manufacturing: review and outlook

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sequencing a single machine with due dates and deadlines: An ILP-based approach to solve very large instances
• Exact methods for the knapsack problem and its generalizations
• A time indexed formulation of non-preemptive single machine scheduling problems
• A dynamic programming method for single machine scheduling
• Using short-term memory to minimize the weighted number of late jobs on a single machine.
• Minimizing the weighted number of tardy jobs on parallel processors
• An exact algorithm for single-machine scheduling without machine idle time
• New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Validation of subgradient optimization
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems

This page was built for publication: An exact approach for scheduling jobs with regular step cost functions on a single machine