关键词: 排序, 学习效应, 单机, 凸资源分配

Abstract: In traditional scheduling model, the processing time of a job (task) is generally assumed to be a constant in advance. However, as the scheduling model evolves, this concept has been revised by introducing the concept of learning effect and resource allocation simultaneously. The importance of the learning effect is its implications in manufacturing industry and production planning, i.e., learning-by-doing increases the production efficiency. For example, a worker (i.e., machine) needs to produce a product (i.e., job), with the accumulation of experience (i.e., the learning effect), so the processing time of the product will be getting shorter. In addition, in the chemical production, the processing time of a product (for instance, a compound) can be controlled by the amount of catalyst, which is the concept of resource allocation (controllable processing time). The scheduling problems with the learning effect and resource allocation simultaneously have received widespread attention, for the research can improve production efficiency and economic benefits.
   This paper investigates a single machine resource allocation scheduling problem with the time-dependent learning effect, where the actual processing time of a job depends not only on the amount of a non-renewable resource but also on the total normal processing time of the jobs that have been processed. The goal of this problem is to determine an optimal sequence and optimal resource allocation such that the linear weighted sum of maximum completion time (i.e., makespan of all jobs) and total resource consumption is to be minimized. Under a given sequence, the optimal resource allocation can be obtained, and then the objective function (cost) of this paper can only depend on the normal processing times (i.e., this problem can be translated into a purely combinatorial optimization problem). The examples are given to show that the smallest processing time (SPT) first rule and largest processing time (LPT) first rule are not the optimal sequences. This problem is conjectured NP-hard, to solve the problem, the optimal properties, the lower bound and upper bound are given, and then the branch and bound algorithm can be proposed. An example is given to show how to solve the problem by the branch and bound algorithm. Finally, the algorithms (including the heuristic upper algorithm and the branch and bound algorithm) are tested numerically as well.
   A challenging question for future research-whether this problem is NP-hard, how to prove it, and whether there are more efficient solution algorithms for this problem. Other interesting future research might be dedicated to the extensions: either to multi-machine (for instance, flow shop or identical parallel machines) settings, or to regular (non-regular) objective functions (for instance, total weighted completion time or earliness-tardiness cost under the just-in-time (J-I-T) production environment).

Key words: scheduling, learning effect, single machine, convex resource allocation