A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times |
| |
Authors: | Alberto Bosio Giovanni Righini |
| |
Affiliation: | (1) Dipartimento di Tecnologie dell’Informazione, Università degli Studi di Milano, via Bramante 65, 26013 Crema, Italy |
| |
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. |
| |
Keywords: | Combinatorial optimization Dynamic programming Scheduling |
本文献已被 SpringerLink 等数据库收录! |