带准备时间的单机指数时间学习效应排序问题

摘要

研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数.学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间.这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解.通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值.通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性.%A single-machine scheduling problem with exponentially time-dependent learning effect and release time is studied in this paper.The exponentially time-dependent learning effect means that the actual processing time of a job is an exponential function of processing times of jobs already processed.We assume that the actual processing time of a job depends on both the job's normal processing time and the cumulative normal processing times of all jobs already processed and consider the minimization of the total completion time as the objective function.This problem is NP-hard,and a mathematical programming model and a branch-and-bound algorithm combining with some dominance properties and lower bounds are presented to derive the optimal solution for the problem.A heuristic algorithm is also proposed to improve the upper bounds of the branch-and-bound algorithm.Computational experiments are presented to verify the performance of the branch-and-bound algorithm in terms of solution quality and time.