A Dynamic Programming Approach for Sequencing Groups of Identical Jobs

Harilaos N. Psaraftis
Additional contact information
Harilaos N. Psaraftis: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1980, vol. 28, issue 6, 1347-1359

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 . This makes our approach practical for real-world problems in which this latter number is small. More importantly, the algorithm offers savings in computational effort as compared to the classical Dynamic Programming approach to sequencing problems, savings which are solely due to taking advantage of group classifications. Specific cost functions, as well as a real-world problem for which the algorithm is particularly well-suited, are examined. The problem application is the optimal sequencing of aircraft landings at an airport. A numerical example as well as suggestions on possible extensions to the model are also presented.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.6.1347 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:28:y:1980:i:6:p:1347-1359

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().