A dynamic programming approach for sequencing groups of identical jobs

Research output: Contribution to journalJournal articleResearchpeer-review

155 Downloads (Pure)

Abstract

A dynamic programming approach for sequencing a given set of jobs in a single machine is developed, so that the total processing cost is minimized. Assume that there are N distinct groups of jobs, where the jobs within each group are identical. A very general, yet additive cost function is assumed. This function includes the overall completion time minimization problem as well as the total weighted completion time minimization problem as special cases. Priority considerations are included; no job may be shifted by more than a prespecified number of positions from its initial, first come-first served position in a prescribed sequence. The running time and the storage requirement of the dynamic programming algorithm are both polynomial functions of the maximum number of jobs per group, and exponential functions of the number of groups N.
Original languageEnglish
Journal4 O R
Volume28
Issue number6
Pages (from-to)1347-1359
Number of pages13
ISSN1619-4500
DOIs
Publication statusPublished - 1980
Externally publishedYes

Fingerprint Dive into the research topics of 'A dynamic programming approach for sequencing groups of identical jobs'. Together they form a unique fingerprint.

Cite this