کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1135098 | 956089 | 2012 | 9 صفحه PDF | دانلود رایگان |
We study a single machine scheduling problem, where the machine is unavailable for processing for a pre-specified time period. We assume that job processing times are position-dependent. The objective functions considered are minimum makespan, minimum total completion time and minimum number of tardy jobs. All these problems are known to be NP-hard even without position-dependent processing times. For all three cases we introduce simple heuristics which are based on solving the classical assignment problem. Lower bounds, worst case analysis and asymptotic optimality are discussed. All heuristics are shown numerically to perform extremely well.
► A single machine scheduling problem with unavailability time period is studied.
► Job processing times are assumed to be position-dependent.
► The objective functions considered are makespan, total completion time and number of tardy jobs.
► In all cases, simple and efficient heuristics are introduced, analyzed and numerically tested.
Journal: Computers & Industrial Engineering - Volume 62, Issue 4, May 2012, Pages 908–916