A note on optimal assignment of slack due-dates in single-machine scheduling
The author solves a single machine problem with job ready times, special due dates and job preemption allowed. Additionally, job precedence constraints are given. The objective is to minimize a linear combination of the maximum tardiness and due date assignment costs. As due dates the slack due dates are used which allow constant slack for all jobs, i.e. \(d_ j= r_ j+ k\) for all jobs \(j\), \(d_ j\) and \(r_ j\) denote the job due date and ready time, respectively, and the parameter \(k\) is the constant slack for all jobs. The solution consists of two phases, computing the optimal job sequence first, then optimizing the due date parameter \(k\). For arbitrary precedence constraints, the algorithm works in \(O(n^ 2)\), whereas for tree-like precedence constraints the complexity decreases to \(O(n\log n)\). For special cases (if the job due dates and modified job release times are similarly ordered) the proposed algorithm can even be used if job preemption is not allowed.
- Optimal assignment of due-dates for preemptive single-machine scheduling
- Single machine scheduling with deadlines, release and due dates
- Optimal assignment of slack due-dates and sequencing in a single-machine shop
- Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment
- Slack due date assignment and scheduling stochastic jobs on a single machine
- Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem
- Due Date Assignment for Production Systems
- scientific article; zbMATH DE number 3825547 (Why is no real title available?)
- scientific article; zbMATH DE number 3691044 (Why is no real title available?)
- On the Assignment of Optimal Due Dates
- Optimal assignment of slack due-date and sequencing in a single machine shop
- Optimal assignment of slack due-dates and sequencing in a single-machine shop
- Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine
- Optimal due-date assignment and sequencing in a single machine shop
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Sequencing with Earliness and Tardiness Penalties: A Review
- Survey of scheduling research involving due date determination decisions
- Scheduling a single machine to minimize earliness penalties subject to the SLK due-date determination method
- Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment
- Optimal assignment of due-dates for preemptive single-machine scheduling
- Single machine scheduling with precedence constraints and positionally dependent processing times
- Scheduling with due date assignment under special conditions on job processing
- Slack due date assignment and scheduling stochastic jobs on a single machine
- A note: minmax due-date assignment problem with lead-time cost
- Scheduling problems with partially ordered jobs
- Optimal assignment of slack due-date and sequencing in a single machine shop
- Optimal assignment of slack due-dates and sequencing in a single-machine shop
This page was built for publication: A note on optimal assignment of slack due-dates in single-machine scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1310016)
