Single machine scheduling with exponential learning functions |
| |
Authors: | Haifeng Ma Cheng Shao Xue-Ru Wang |
| |
Institution: | 1. Institute of Advanced Control Technology, Dalian University of Technology, Dalian, 116024, Liaoning, China 2. School of Science, Shenyang Aerospace University, Shenyang, 110136, China
|
| |
Abstract: | In this paper we consider the single machine scheduling problem with exponential learning functions. By the exponential learning functions, we mean that the actual job processing time is a function of the total normal processing times of the jobs already processed. We prove that the shortest processing time (SPT) rule is optimal for the total lateness minimization problem. For the following three objective functions, the total weighted completion time, the discounted total weighted completion time, the maximum lateness, we present heuristic algorithms according to the corresponding problems without exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms. It also shows that the problems of minimizing the total tardiness and discounted total weighted completion time are polynomially solvable under some agreeable conditions on the problem parameters. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|