Dynamic programming approach to the single-machine sequencing problem with different due-dates
type: Item
instance of: scholarly article
title: Dynamic programming approach to the single-machine sequencing problem with different due-dates
zbMATH Open document ID: 0699.90092
DOI: 10.1016/0898-1221(90)90001-Z
publication date: 1990-01-01T00:00:00Z
review text: A collection of jobs is to be processed in such a way that the sum of absolute deviations of job completion times about their respective due- dates is minimized. The problem is NP-complete and a dynamic programming approach is described which offers considerable computational savings over complete enumeration.
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 4147880
zbMATH Keywords: sum of absolute deviations
zbMATH Keywords: job completion times
zbMATH Keywords: due-dates
zbMATH Keywords: NP-complete
author: T. C. Edwin Cheng
reviewed by: Kevin D. Glazebrook
MaRDI profile type: Publication
cites work: Minimizing mean absolute deviation of completion times about a common due date
cites work: Minimizing the average deviation of job completion times about a common due-date: An extension
cites work: Survey of scheduling research involving due date determination decisions
cites work: The art and theory of dynamic programming
cites work: Q3793928
cites work: One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
cites work: Single- and multiple-processor models for minimizing completion time variance
cites work: Q5667655
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: Minimizing the average deviation of job completion times about a common due date
cites work: A Generalized Model of Optimal Due-Date Assignment by Linear Programming
cites work: Minimizing the sum of absolute lateness in single-machine and multimachine scheduling
full work available at URL: 0898-1221(90)90001-z
OpenAlex ID: W2083506849
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 4147880