A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines

Nguyen Huynh Tuong, Ameur Soukhal and Jean-Charles Billaut

European Journal of Operational Research, 2010, vol. 202, issue 3, 646-653

Abstract: This paper deals with a scheduling problem of independent tasks with common due date where the objective is to minimize the total weighted tardiness. The problem is known to be ordinary NP-hard in the case of a single machine and a dynamic programming algorithm was presented in the seminal work of Lawler and Moore [E.L. Lawler, J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16 (1969) 77-84]. In this paper, this algorithm is described and discussed. Then, a new dynamic programming algorithm is proposed for solving the single machine case. These methods are extended for solving the identical and uniform parallel-machine scheduling problems.

Keywords: Scheduling; Single; machine; Parallel; machines; Dynamic; programming (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00486-X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:202:y:2010:i:3:p:646-653

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().