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

Single-machine learning effect scheduling jobs with release time

具有学习效应的任务的加工时间和带有准备时间的任务问题是排序论中的重要研究内容,它们对任务的完工时间有重要影响.研究了具有学习效应且带有准备时间的任务单机排序问题,其中学习效应指的是任务的实际加工时间是该已经排好的任务对数加工时间的递减函数,目标函数为最小化总完工时间.这个问题是NP-难问题.用分支定界法给出了此问题的最优解,为了提高分支定界法的运行效率,同时给出了一个启发式算法、几个优势性质和两个下界.计算结果表明分支定界法和启发式算法求解此问题非常有效.

The processing time of jobs with a learning important research content in scheduling, which have effect and the jobs with release time are the important effects on the completion time of jobs. A single-machine learning effect scheduling problem with job release time is considered, where the learning effect means that the actual processing time of a job is a decreasing function of total logarithm normal processing time of jobs in front of it in the sequence, the objective function is to minimize the total completion time. This problem is well-known NP-hard, and a branch-and-bound algorithm is proposed to solve the problem. A heuristic algorithm, several dominance properties and two lower bounds are derived to speed up the elimination process of the branch-and-bound algorithm. Computational results show that the proposed heuristic algorithm and the branch-and-bound algorithm can perform effectively and efficiently.