CAJ | 학술논문

针对带一台搬运机器人的job—shop调度问题，提出了一种并行禁忌搜索算法，目标是最小化最大完工时间。首先，充分利用问题的特点，构造2个启发式的初始排序。然后，利用这2个初始排序，使用禁忌搜索算法并行的搜索。在禁忌搜索算法的领域部分，先建立析取图模型，然后查找关键路径，再查找关键路径上的机床块和机器人块，在块上采取移动或交换的策略来建立领域。实验结果表明算法是有效的。
침대대일태반운궤기인적job—shop조도문제，제출료일충병행금기수색산법，목표시최소화최대완공시간。수선，충분이용문제적특점，구조2개계발식적초시배서。연후，이용저2개초시배서，사용금기수색산법병행적수색。재금기수색산법적영역부분，선건립석취도모형，연후사조관건로경，재사조관건로경상적궤상괴화궤기인괴，재괴상채취이동혹교환적책략래건립영역。실험결과표명산법시유효적。
In this paper, scheduling problem of job-shop with a single transport robot is addressed. A parallel tabu search algorithm is presented to minimize the makespan. First, with the characteristic of the problem, two schedules are created as the initial solutions by using a heuristic. Then, the tabu search algorithm is used for parallel search. By this algorithm, a disjunctive graph model is established such that the critical path and the block are found. Then, a strategy of moving or changing on block is used for the neighborhood in the algorithm. Experimental results show that the algorithm is effective.