CAJ | 학술논문

在满足任务的交货期相同和工序无等待等假设条件后,提出了一种排列流水车间提前/延期惩罚调度问题的启发式算法. 该算法首先按照7种任务排序的规则分别得到任务的较优次序,然后分别使用NEH算法构造优化解,再对每个不同解进行邻域搜索,最后比较得出最优解. 在中小规模问题的数据实验中,该算法求解与最优解的相近程度达到99%左右,并且通过大量数据样本的标准差验证,求解的稳定性也非常好. 在大规模问题的数据实验中,该启发式算法体现出非常好的优化性能,同constraint programming(ILOG-CP)优化引擎算法比较,计算结果也明显占优.
재만족임무적교화기상동화공서무등대등가설조건후,제출료일충배렬류수차간제전/연기징벌조도문제적계발식산법. 해산법수선안조7충임무배서적규칙분별득도임무적교우차서,연후분별사용NEH산법구조우화해,재대매개불동해진행린역수색,최후비교득출최우해. 재중소규모문제적수거실험중,해산법구해여최우해적상근정도체도99%좌우,병차통과대량수거양본적표준차험증,구해적은정성야비상호. 재대규모문제적수거실험중,해계발식산법체현출비상호적우화성능,동constraint programming(ILOG-CP)우화인경산법비교,계산결과야명현점우.
Given the same due date and no idle time in processes, a heuristic algorithm for the earliness and tardiness penalties scheduling problem in permutation flow shop is proposed. Firstly, the algorithm gets the relatively good sequence of the jobs according to the sorted sequence regulation of 7 jobs. And then, the NEH algorithm is used to get the optimized solutions. At last, the optimal solutions are achieved by comparing the neighborhood searching results for every solutions. In the middle scale and small scale problems, the extent of similarity between the solutions got by the heuristic algorithm and the optimal solutions is 99%. Meanwhile through testing the standard deviation of the large scale samples, it is shown that the stability of the solutions is very good. In large scale problems, the heuristic algorithm appears good optimized performances and its calculated results are better than those got by ILOG-constraint programming(CP) optimized engine.