CAJ | 학술논문

具有学习效应的任务的加工时间和带有准备时间的任务问题是排序论中的重要研究内容，它们对任务的完工时间有重要影响。研究了具有学习效应且带有准备时间的任务单机排序问题，其中学习效应指的是任务的实际加工时间是该已经排好的任务对数加工时间的递减函数，目标函数为最小化总完工时间。这个问题是NP-难问题。用分支定界法给出了此问题的最优解，为了提高分支定界法的运行效率，同时给出了一个启发式算法、几个优势性质和两个下界。计算结果表明分支定界法和启发式算法求解此问题非常有效。
구유학습효응적임무적가공시간화대유준비시간적임무문제시배서론중적중요연구내용，타문대임무적완공시간유중요영향。연구료구유학습효응차대유준비시간적임무단궤배서문제，기중학습효응지적시임무적실제가공시간시해이경배호적임무대수가공시간적체감함수，목표함수위최소화총완공시간。저개문제시NP-난문제。용분지정계법급출료차문제적최우해，위료제고분지정계법적운행효솔，동시급출료일개계발식산법、궤개우세성질화량개하계。계산결과표명분지정계법화계발식산법구해차문제비상유효。
The processing time of jobs with a learning effect and the jobs with release time are the important research content in scheduling , w hich have 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 .