We consider a scheduling problem in which the processing time of each job deteriorates, i.e. it increases as time passes after the release date of the job. We present a dynamic programming algorithm coupled with upper bounding and lower bounding techniques to compute exact solutions. We report on problem instances of different size and we analyze the dependence between the ranges to which the data belong and the computing time.
A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times / A. Bosio, G. Righini. - In: MATHEMATICAL METHODS OF OPERATIONS RESEARCH. - ISSN 1432-2994. - 69:2(2009), pp. 271-280. [10.1007/s00186-008-0258-1]
A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times
G. RighiniUltimo
2009
Abstract
We consider a scheduling problem in which the processing time of each job deteriorates, i.e. it increases as time passes after the release date of the job. We present a dynamic programming algorithm coupled with upper bounding and lower bounding techniques to compute exact solutions. We report on problem instances of different size and we analyze the dependence between the ranges to which the data belong and the computing time.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
