Single‐machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm

Suresh Chand, Rodney Traub and Reha Uzsoy

Naval Research Logistics (NRL), 1996, vol. 43, issue 5, 709-719

Abstract: This article considers the single‐machine dynamic scheduling problem where the jobs have different arrival times and the objective is to minimize the sum of completion times. This problem is known to be strongly NP‐hard. We develop decomposition results for this problem such that a large problem can be solved by combining optimal solutions for several smaller problems. The decomposition results can be used with any implicit enumeration method to develop an optimal algorithm. Our computational experiment indicates that the computational efficiency of the currently best available branch‐and‐bound algorithm can be improved with the use of our decomposition results. © 1996 John Wiley & Sons, Inc.

Date: 1996
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199608)43:53.0.CO;2-9

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:wly:navres:v:43:y:1996:i:5:p:709-719

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().