Article ID: | iaor20115553 |
Volume: | 126 |
Issue: | 2 |
Start Page Number: | 264 |
End Page Number: | 266 |
Publication Date: | Aug 2010 |
Journal: | International Journal of Production Economics |
Authors: | Koulamas Christos, Kyparisis George J |
Keywords: | job shop, makespan, sequencing, setup time |
We consider single‐machine scheduling problems with past‐sequence‐dependent (p‐s‐d) job delivery times. The p‐s‐d delivery time is needed to remove any waiting time‐induced adverse effects on the job's condition (prior to delivering the job to the customer) and it is therefore proportional to the job's waiting time. We show that single‐machine scheduling problems with p‐s‐d delivery times and with either completion time‐related criteria (such as the makespan or the total job completion time) or due date related criteria (such as the maximum lateness or the number of tardy jobs) can be solved by simple polynomial‐time algorithms.