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

摘要： 研究工件加工时间具有依赖时间学习效应的单机资源分配排序问题,其中工件的实际加工时间不仅依赖于分配给它的不可再生资源数量,还依赖于该工件所排位置之前工件的基本加工时间之和。该问题研究的目标是确定工件的最优排序和最优的资源分配,使最大完工时间(即所有工件的时间表长)和消耗资源的线性加权和最小。对给定的排序,最优的资源分配能够得到,从而目标函数转化为只和工件的基本加工时间有关。通过实例说明经典的最小加工时间优先(SPT)规则和最大加工时间优先(LPT)规则都不是最优解。猜测此问题是NP-难的,为了求解此问题,分析了问题满足的性质,给出了上界和下界,从而给出分支定界算法,并用实例说明该算法是如何求解的。

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