Single-machine scheduling problems with past-sequence-dependent setup times |
| |
Authors: | Christos Koulamas George J. Kyparisis |
| |
Affiliation: | Department of Decision Sciences and Information Systems, Florida International University, University Park, Miami, FL 33199, United States |
| |
Abstract: | This paper studies single-machine scheduling problems with setup times which are proportionate to the length of the already scheduled jobs, that is, with past-sequence-dependent or p-s-d setup times. The following objective functions are considered: the maximum completion time (makespan), the total completion time, the total absolute differences in completion times and a bicriteria combination of the last two objective functions. It is shown that the standard single-machine scheduling problem with p-s-d setup times and any of the above objective functions can be solved in O(nlog n) time (where n is the number of jobs) by a sorting procedure. It is also shown that all of our results extend to a “learning” environment in which the p-s-d setup times are no longer linear functions of the already elapsed processing time due to learning effects. |
| |
Keywords: | Scheduling Single-machine Setup times |
本文献已被 ScienceDirect 等数据库收录! |
|