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

Abstract: Scheduling problems with learning effects are common in actual production environments. For instance, when a machine (worker) needs to assemble or process a product (job), the time required for processing depends on their knowledge, skill, and experience. As the learning effect takes place gradually, products that are processed towards the end of the schedule usually have shorter processing times. In the chemical industry, the processing time of a compound can be varied by increasing the amount of catalyst used. Similarly, in steel production, the length of the preheating time depends on the amount of fuel used. When there is sufficient fuel, the processing time will be reduced. All of the examples mentioned above are influenced by the learning effect and the available resources during the completion time. The scheduling problems related to the learning effect and resource allocation have received significant attention from scholars in recent years. The efficient use of the learning effect and resource allocation can improve production and processing efficiency, leading to increased economic benefits. This note considers the single machine scheduling problems with learning effect and resource-dependence processing times, in which the actual job processing time is a decreasing function of its position scheduled in a sequence and a linear decreasing function of resource consumption.
The paper YU and CHENG (2008) discussed the problem of single-machine scheduling, where the actual machining time of a job is affected by both learning effect and allocated resources. There are jobs to be processed on a single machine, assuming that all jobs arrive at time 0 and that the machine and all jobs cannot be interrupted. The objective is to determine the optimal sequence of all jobs and resource allocation such that the weighted sum of total (weighted) completion time and total resource consumption cost is minimized. The problem assumes that the learning effect of the job is an exponential function of the sum of the normal processing times of the previously processed jobs. Meanwhile, the actual processing time of the job decreases linearly with the resources allocated to the job. The published result showed that the problem of minimizing the sum of the total completion time and the total resource consumption cost is solvable in polynomial time. For the problem of minimizing the sum of total weighted completion time and resource consumption cost, in a special case (i.e., the normal processing time and weight of jobs satisfy an agreeable condition), the published results showed that this problem is polynomially solvable. Firstly, the paper lists the methods for obtaining the optimal sequence of the jobs and the optimal allocation of resources. Then, three counter-examples are given to show that the published results are incorrect. Finally, the main reasons for the incorrectness are presented, i.e., the portion of objective function corresponds to the assignment problem. Future research may consider the time complexity of scheduling problems with learning effects and resource dependence, i.e., whether polynomial time algorithms exist in these problems.

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