Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs

J. Wesley Barnes and Lawrence K. Vanston
Additional contact information
J. Wesley Barnes: The University of Texas, Austin, Texas
Lawrence K. Vanston: The University of Texas, Austin, Texas

Operations Research, 1981, vol. 29, issue 1, 146-160

Abstract: We discuss the problem of minimizing the sum of the setup costs and linear delay penalties when N jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. The delay penalty for each job is a nondecreasing linear function of the sum of the various processing times for preceding jobs. The setup cost for each job is dependent only upon the job that immediately precedes it. The equivalence of the traveling salesman problem to the setup portion of this problem creates a special challenge. The application of several Branch-and-Bound algorithms using various branching rules is discussed. Since the problem has a highly attractive Dynamic Programming formulation, a hybrid algorithm analogous to Morin and Marsten's Dynamic Programming/Branch-and-Bound approach to the traveling salesman problem is also utilized. This technique, detailed in the paper, applies a fathoming criterion to the states of the Dynamic Program in order to drastically reduce memory and computational requirements. We report computational results for a set of randomly generated problems that endorse the effectiveness of one heuristic approach and show the superiority of the hybrid approach over pure Branch-and-Bound methods in yielding confirmed optimal solutions for that set of problems.

Date: 1981
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.29.1.146 (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:29:y:1981:i:1:p:146-160

Access Statistics for this article

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