Scheduling jobs with values dependent on their completion times

Adam Janiak and Tomasz Krysiak

International Journal of Production Economics, 2012, vol. 135, issue 1, 231-241

Abstract: The paper concerns two scheduling problems with job values and losses of job values (costs) dependent on job completion times. In the first problem, we consider scheduling jobs with stepwise values in parallel processor environment. In the stepwise value, there is given a number of moments at which the job value decreases and between them the job value is constant (thus, the value deteriorates over time). The maximized criterion is the total job value. We prove strong NP-hardness of a single processor case of the problem and construct a pseudo-polynomial time algorithm for a special case with fixed number of unrelated parallel processors and fixed number of common moments of job value changes. Additionally, for uniform and unrelated parallel processors we construct and experimentally test several heuristic algorithms based on the list strategy. The second problem is a single processor one with piecewise linear losses of job values (the loss increases over time). The minimized criterion is the total loss of job value. We prove strong NP-hardness of the problem and existence of a pseudo-polynomial time exact algorithm for its special case. We also construct some heuristic algorithms for this problem and verify experimentally their efficiency.

Keywords: Scheduling; Job value; Computational complexity; Heuristic (search for similar items in EconPapers)
Date: 2012
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/S092552731100315X
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:135:y:2012:i:1:p:231-241

DOI: 10.1016/j.ijpe.2011.07.014

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 ().