Some single-machine scheduling problems with a truncation learning effect

✍ Scribed by Chin-Chia Wu; Yunqiang Yin; Shuenn-Ren Cheng

• Publisher: Elsevier Science
• Year: 2011
• Tongue: English
• Weight: 219 KB
• Volume: 60
• Category: Article
• ISSN: 0360-8352
• DOI: 10.1016/j.cie.2011.01.016

✦ Synopsis

Scheduling with learning effects has received growing attention nowadays. A well-known learning model is called ''sum-of processing-times-based learning'' in which the actual processing time of a job is a nonincreasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Motivated by this observation, we propose a truncation learning model where the actual job processing time is a function which depends not only on the processing times of the jobs already processed but also on a control parameter. The use of the truncated function is to model the phenomenon that the learning of a human activity is limited. Under the proposed learning model, we show that some single-machine scheduling problems can be solved in polynomial time. In addition, we further provide the worst-case error bounds for the problems to minimize the maximum lateness and total weighted completion time.