点击次数：

论文类型：期刊论文

发表时间：2009-10-01

发表刊物：INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL

收录刊物：EI、SSCI、SCIE、Scopus

卷号：5

期号：10A

页面范围：3189-3199

ISSN号：1349-4198

关键字：Scheduling; Time-dependent; Learning effect; Sigle-machine; Heuristic algorithm; Performance ratio

摘要：This paper deals with Single-machine scheduling problems with an actual time-dependent learning consideration. First, we provide a mathematical description of learning effects in scheduling environment. Then we introduce an actual time-dependent learning model, in which the learning effect is defined a function of the ratio of sum of actual processing times of the jobs previously scheduled to total normal processing time of all jobs. We incorporate it into single-machine scheduling problems and show by examples that the optimal schedule for the classical version of the problem is not optimal in the presence of this new actual time-dependent learning effect for the following objective functions: the makespan, the sum. of kth power of the completion times, the total weighted completion times, the maximum lateness and the number of tardy jobs. But for some special cases, we show that the shortest processing time first (SPT) rule, the weighted shortest processing time first (WSPT) rule, the earliest due date (EDD) rule and Moore's Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively. We also use these rules as heuristics for the general cases and analyze their worst-case error bounds.