A bicriteria approach to minimize number of tardy jobs and resource consumption in scheduling a single machine

Liron Yedidsion, Dvir Shabtay, Ephraim Korach and Moshe Kaspi

International Journal of Production Economics, 2009, vol. 119, issue 2, 298-307

Abstract: We extend the classical scheduling problem of minimizing the number of tardy jobs in a single-machine to the case where the job processing times are controllable by allocating a continuous and non-renewable resource to the processing operations. Our aim is to construct an efficient trade-off curve between the number of tardy jobs and total resource consumption using a bicriteria approach. Most of the research on scheduling with controllable resource-dependent processing times is done either to a linear resource consumption function or to a specific type of convex resource consumption function. We, in contrast, analyze the problem for a more general type of convex decreasing resource consumption function, which guarantees a very robust analysis that can be applied to a wide range of problems. We present four different variations of the problem and prove them to be -hard. We then present a polynomial time algorithm to solve an important special case of the problem and also suggest and compare the performances of three different heuristic algorithms.

Keywords: Deterministic; scheduling; Controllable; processing; times; Resource; allocation; Complexity (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925-5273(09)00078-4
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:proeco:v:119:y:2009:i:2:p:298-307

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().