On the general solution for a class of early/tardy problems
type: Item
instance of: scholarly article
title: On the general solution for a class of early/tardy problems
zbMATH Open document ID: 0794.90021
DOI: 10.1016/0305-0548(93)90070-Y
author: Prabuddha De
author: Jay B. Ghosh
author: Charles Wells
published in: Computers \& Operations Research
publication date: 1993-04-01T00:00:00Z
review text: The non-preemptive scheduling of \(n\) jobs with a common due date \(d\) on a single machine is considered. The objective is to find a schedule that minimizes \(\sum^ n_{j=1} | C_ j- d|^ r\), where \(C_ j\) is the completion time of job \(j\) and \(r\) is a positive integer. By generalizing known results for \(r=1\) and \(r=2\), various structural properties of an optimal solution are derived. These structural properties are used to derive a pseudopolynomial dynamic programming algorithm. Prior to applying this algorithm, it is assumed that the processing times and the due date are suitably scaled using an integer scaling factor so that optimal completion times of jobs are integers.
reviewed by: C.N.Potts
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 149370
zbMATH Keywords: non-preemptive scheduling
zbMATH Keywords: common due date
zbMATH Keywords: single machine
zbMATH Keywords: pseudopolynomial dynamic programming
MaRDI profile type: Publication
cites work: Sequencing with Earliness and Tardiness Penalties: A Review
cites work: Minimizing the average deviation of job completion times about a common due date
cites work: Single- and multiple-processor models for minimizing completion time variance
cites work: Determination of an optimal common due date and optimal sequence in a single machine job shop
cites work: Minimizing the sum of absolute lateness in single-machine and multimachine scheduling
cites work: A V-shape property of optimal schedule of jobs about a common due date
cites work: Minimizing mean absolute deviation of completion times about a common due date
cites work: Single-machine scheduling to minimize absolute deviation of completion times from a common due date
cites work: Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
cites work: Scheduling to minimize weighted earliness and tardiness about a common due-date
cites work: Scheduling around a small common due date
cites work: Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
cites work: Note—A Note on the Minimization of Mean Squared Deviation of Completion Times About a Common Due Date
cites work: Scheduling about a common due date with earliness and tardiness penalties
cites work: Minimizing the Time-in-System Variance for a Finite Jobset
cites work: Minimising Waiting Time Variance in the Single Machine Problem
cites work: Deterministic and Random Single Machine Sequencing with Variance Minimization
cites work: Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem
cites work: An alternative proof of optimality for the common due-date assignment problem
cites work: Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date
cites work: V-shape property for optimal schedules with monotone penalty functions
cites work: A Functional Equation and its Application to Resource Allocation and Sequencing Problems
full work available at URL: 0305-0548(93)90070-y
OpenAlex ID: W2080122513
description: scientific article; zbMATH DE number 149370