带学习效应和资源依赖的单机排序模型

Single Machine Scheduling Problems with Learning Effect and Resource-dependence

在工业生产中,随着员工操作技能的熟练程度的增加,对于相同的任务越往后加工,所花的时间将会减少。同时,为了尽早完工,管理者也会考虑给加工工件分配一定量的额外资源来缩短工件加工时间。本文基于以上实例,讨论了工件的实际加工时间既具有学习效应又依赖所分配资源的单机排序问题。在问题中,假设工件的学习效应是之前已加工工件正常加工时间和的指数函数。同时随着分配给工件资源量的增加,工件的实际加工时间呈线性减少,所需费用呈线性增加。对这一排序模型,主要探讨以下五个目标函数:最小化最大完工时间与资源消耗量总费用的和;最小化总完工时间与资源消耗量总费用的和;最小化加权总完工时间与资源消耗量总费用的和;最小化总提前、总延误、总共同交货期与资源消耗量总费用的和以及最小化总提前、总延误、总松弛交货期与资源消耗量总费用的和。本文对前三个目标函数相应的排序问题给出了多项式时间可求解的算法。对后两个目标函数所涉及的排序问题借助于指派问题分别给出了时间复杂性为O(n3)的算法。

In industrial manufactures, the time spent on the same task will be reduced as the skill level of the staff increases. At the same time, the manager will consider allocating a certain amount of additional resources to shorten the job processing time. In this paper, we consider single machine scheduling problems in which the actual processing time of a job is of learning effect and of resource-dependence based on the above case. In the problem, it is assumed that the actual processing time of a job is an exponential function of the total normal processing time of jobs already processed before it. At the same time,the actual processing time of a job linear decreases and the total resource consumption costs linear increases as the resource distributed to the job increases. For such a scheduling problem, we introduce five objective functions： the sum of makespan and total resource consumption costs; the sum of the total completion time and total resource consumption costs; the sum of the total weighted completion time and total resource consumption costs ; the sum of the total earliness,tardi- ness,common due date and total resource consumption costs and the sum of the total earliness,tardiness,slack due date and total resource consumption costs. For the scheduling problems corresponding to the first three func- tions , we present polynomial time solvable algorithms respectively. We give time solvable algorithms for the scheduling problems corresponding to the last two functions respectively by using assignment problem.