Dynamic programming approach to the single-machine sequencing problem with different due-dates

Edwin Tai Chiu Cheng

doi:10.1016/0898-1221(90)90001-Z

Dynamic programming approach to the single-machine sequencing problem with different due-dates

Edwin Tai Chiu Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

3 Citations (Scopus)

Abstract

Given a set of n jobs each of which is assigned a due-date and all jobs are simultaneously available to be processed on a single machine, the problem is to find the optimal job processing order that minimizes the sum of absolute deviation of job completion times about their respective due-dates. Since this problem has been shown to be NP-complete, we present a DP (dynamic programming) formulation of the problem and apply the principle of optimality of DP to find the optimal solution by implicit enumeration.

Original language	English
Pages (from-to)	1-7
Number of pages	7
Journal	Computers and Mathematics with Applications
Volume	19
Issue number	2
DOIs	https://doi.org/10.1016/0898-1221(90)90001-Z
Publication status	Published - 1 Jan 1990
Externally published	Yes

ASJC Scopus subject areas

Modelling and Simulation
Computational Theory and Mathematics
Computational Mathematics

More information

10.1016/0898-1221(90)90001-Z

Cite this

@article{b5343bafc46440bfba2db6f3c0db6926,

title = "Dynamic programming approach to the single-machine sequencing problem with different due-dates",

abstract = "Given a set of n jobs each of which is assigned a due-date and all jobs are simultaneously available to be processed on a single machine, the problem is to find the optimal job processing order that minimizes the sum of absolute deviation of job completion times about their respective due-dates. Since this problem has been shown to be NP-complete, we present a DP (dynamic programming) formulation of the problem and apply the principle of optimality of DP to find the optimal solution by implicit enumeration.",

author = "Cheng, \{Edwin Tai Chiu\}",

year = "1990",

month = jan,

day = "1",

doi = "10.1016/0898-1221(90)90001-Z",

language = "English",

volume = "19",

pages = "1--7",

journal = "Computers and Mathematics with Applications",

issn = "0898-1221",

publisher = "Elsevier Ltd",

number = "2",

}

TY - JOUR

T1 - Dynamic programming approach to the single-machine sequencing problem with different due-dates

AU - Cheng, Edwin Tai Chiu

PY - 1990/1/1

Y1 - 1990/1/1

N2 - Given a set of n jobs each of which is assigned a due-date and all jobs are simultaneously available to be processed on a single machine, the problem is to find the optimal job processing order that minimizes the sum of absolute deviation of job completion times about their respective due-dates. Since this problem has been shown to be NP-complete, we present a DP (dynamic programming) formulation of the problem and apply the principle of optimality of DP to find the optimal solution by implicit enumeration.

AB - Given a set of n jobs each of which is assigned a due-date and all jobs are simultaneously available to be processed on a single machine, the problem is to find the optimal job processing order that minimizes the sum of absolute deviation of job completion times about their respective due-dates. Since this problem has been shown to be NP-complete, we present a DP (dynamic programming) formulation of the problem and apply the principle of optimality of DP to find the optimal solution by implicit enumeration.

UR - https://www.scopus.com/pages/publications/0025205492

U2 - 10.1016/0898-1221(90)90001-Z

DO - 10.1016/0898-1221(90)90001-Z

M3 - Journal article

SN - 0898-1221

VL - 19

SP - 1

EP - 7

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

IS - 2

ER -

Dynamic programming approach to the single-machine sequencing problem with different due-dates

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this