Single-machine scheduling with time window-dependent processing times |
| |
Authors: | C Lahlou S Dauzère-Pérès |
| |
Affiliation: | 1.IRCCyN—Ecole des Mines de Nantes,Nantes Cedex,France;2.Ecole des Mines de Saint-Etienne,Gardanne,France |
| |
Abstract: | In the one-machine scheduling problems analysed in this paper, the processing time of a job depends on the time at which the job is started. More precisely, the horizon is divided into time windows and with each one a coefficient is associated that is used to determine the actual processing time of a job starting in it. Two models are introduced, and one of them has direct connections with models considered in previous papers on scheduling problems with time-dependent processing times. Various computational complexity results are presented for the makespan criterion, which show that the problem is NP-hard, even with two time windows. Solving procedures are also proposed for some special cases. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|