Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2014-04-01

Journal: OPTIMIZATION LETTERS

Included Journals: EI、SCIE

Volume: 8

Issue: 4

Page Number: 1273-1285

ISSN: 1862-4472

Key Words: Scheduling; Single machine; Learning effect

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.