点击次数：

论文类型：期刊论文

发表时间：2014-04-01

发表刊物：OPTIMIZATION LETTERS

收录刊物：SCIE、EI

卷号：8

期号：4

页面范围：1273-1285

ISSN号：1862-4472

关键字：Scheduling; Single machine; Learning effect

摘要：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.