具有共同松弛时间的恶化型工件排序问题研究

研究工件加工时间具有恶化效应的单机松弛工期排序问题.其中恶化效应指的是工件的实际加工时间是其开工时间的递增函数且所有工件的恶化率相同,工件的松弛工期等于其实际加工时间加上共同的松弛时间.目标是确定工件的一个排序和工件工期的共同松弛时间使得工件的提前时间、延迟时间和工期的共同松弛时间的线性加权和达到最小.用运筹学方法证明了该问题可以转化为两个向量的乘积问题,从而多项式时间可解,并给出了求解的最优算法.

Research on common slack time scheduling problem with deteriorating jobs

The single-machine slack due date scheduling problem with deteriorating jobs is researched, where the deterioration effect means that the actual processing time of jobs is defined as increasing function of their starting time and the deteriorating rates of all jobs are identical, and due date of the job is equal to its actual processing time plus the common slack time. The objective is to determine the optimal scheduling and the common slack time simultaneously to minimize the sum of earliness, tardiness and common slack time. It is proved that the problem can be transformed into the product of two vectors by the operations research method, thus can be solved in polynomial time, and the optimal algorithm to solve the problem is given.