Single Machine Scheduling Problems with General Breakdowns, Earliness and Tardiness Costs

A. Federgruen and G. Mosheiov
Additional contact information
A. Federgruen: Columbia University, New York
G. Mosheiov: Hebrew University, Jerusalem, Israel

Operations Research, 1997, vol. 45, issue 1, 66-71

Abstract: In this paper we consider single machine scheduling problems with a common due-date for all jobs, arbitrary monotone earliness and tardiness costs and arbitrary breakdown and repair processes. We show that the problem is equivalent to a deterministic one without breakdowns and repairs and with an equivalent cost function of a job's completion time. A V -shaped schedule without idle times is shown to be optimal, if this equivalent cost function is quasi-convex .Conversely, we show that a V -shaped schedule may fail to be optimal if the property does not apply. We derive general conditions for the earliness and tardiness cost structure and repair and breakdown processes under which the equivalent cost function is quasi-convex . When a V -shaped schedule is optimal, an efficient (though pseudo-polynomial) algorithm can be used to compute an optimal schedule.

Keywords: production/scheduling; stochastic (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.1.66 (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:45:y:1997:i:1:p:66-71

Access Statistics for this article

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