A scheduling problem with job values given as a power function of their completion times
This paper deals with a problem of scheduling jobs on the identical parallel machines, where job values are given as a power function of the job completion times. Minimization of the total loss of job values is considered as a criterion. We establish the computational complexity of the problem - strong NP-hardness of its general version and NP-hardness of its single machine case. Moreover, we solve some special cases of the problem in polynomial time. Finally, we construct and experimentally test branch and bound algorithm (along with some elimination properties improving its efficiency) and several heuristic algorithms for the general case of the problem.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Voutsinas, Theodore G. & Pappis, Costas P., 2002. "Scheduling jobs with values exponentially deteriorating over time," International Journal of Production Economics, Elsevier, vol. 79(3), pages 163-169, October.
- Bachman, Aleksander & Janiak, Adam, 2000. "Minimizing maximum lateness under linear deterioration," European Journal of Operational Research, Elsevier, vol. 126(3), pages 557-566, November.
- W. Townsend, 1978. "The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution," Management Science, INFORMS, vol. 24(5), pages 530-534, January.
- Wlodzimierz Szwarc & Marc E. Posner & John J. Liu, 1988. "The Single Machine Problem with a Quadratic Cost Function of Completion Times," Management Science, INFORMS, vol. 34(12), pages 1480-1488, December.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:193:y:2009:i:3:p:836-848. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.