A note on optimal assignment of slack due-dates in single-machine scheduling
type: Item
instance of: scholarly article
title: A note on optimal assignment of slack due-dates in single-machine scheduling
zbMATH Open document ID: 0794.90023
DOI: 10.1016/0377-2217(93)90242-F
published in: European Journal of Operational Research
publication date: 1993-12-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 474844
zbMATH Keywords: single machine
zbMATH Keywords: job ready times
zbMATH Keywords: due dates
zbMATH Keywords: job preemption
zbMATH Keywords: precedence constraints
zbMATH Keywords: maximum tardiness
author: V. S. Gordon
reviewed by: Helmut G. Kahlbacher
MaRDI profile type: Publication
cites work: Optimal assignment of slack due-date and sequencing in a single machine shop
cites work: Q3885495
cites work: On the Assignment of Optimal Due Dates
cites work: Sequencing with Earliness and Tardiness Penalties: A Review
cites work: Optimal due-date assignment and sequencing in a single machine shop
cites work: Optimal assignment of slack due-dates and sequencing in a single-machine shop
cites work: Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine
cites work: Survey of scheduling research involving due date determination decisions
cites work: Q3670910
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem
cites work: Due Date Assignment for Production Systems
description: scientific article; zbMATH DE number 474844