CAJ | 학술논문

针对柔性作业车间调度问题(Flexible job shop scheduling problem，FJSP)，以优化最大完工时间为目标，提出一种融合两级邻域搜索和遗传算法的混合算法。基于通过利用机器空闲时间来减小最大完工时间的想法，构造邻域结构，对关键路径上的关键工序进行移动，实现邻域搜索，以改进当前解；设计针对FJSP问题特点的两级邻域搜索方式，第一级邻域搜索为跨机器移动工序，将工序移动到除当前加工机器之外的其他可选机器上，第二级邻域搜索为同机器移动工序，将工序在当前加工机器上进行移动；给出两级邻域搜索相应的保证可行解工序移动条件；兼顾FJSP问题求解算法的全局搜索能力和局部搜索能力，利用遗传算法实现全局搜索，两级邻域搜索实现局部搜索；采用国际通用的FJSP问题基准算例进行测试，验证了所提方法的有效性。
침대유성작업차간조도문제(Flexible job shop scheduling problem，FJSP)，이우화최대완공시간위목표，제출일충융합량급린역수색화유전산법적혼합산법。기우통과이용궤기공한시간래감소최대완공시간적상법，구조린역결구，대관건로경상적관건공서진행이동，실현린역수색，이개진당전해；설계침대FJSP문제특점적량급린역수색방식，제일급린역수색위과궤기이동공서，장공서이동도제당전가공궤기지외적기타가선궤기상，제이급린역수색위동궤기이동공서，장공서재당전가공궤기상진행이동；급출량급린역수색상응적보증가행해공서이동조건；겸고FJSP문제구해산법적전국수색능력화국부수색능력，이용유전산법실현전국수색，량급린역수색실현국부수색；채용국제통용적FJSP문제기준산례진행측시，험증료소제방법적유효성。
For the flexible job shop scheduling problem (FJSP), in order to optimize the maximum completion time, a hybrid algorithm mixed with bilevel neighborhood search and genetic algorithm is proposed. The neighborhood structure is constructed by using machine idle time to reduce the maximum completion time. In order to improve the current solution, critical operations of the critical path are moved to achieve neighborhood search. The method of bilevel neighborhood search is designed according to the characteristics of FJSP. The first level neighborhood search is the cross-machine moving operation, and the operation is moved to other optional machines in addition to current processing machine. The second level neighborhood search is the same-machine moving operation, and the operation is moved on current processing machine. Operation moving conditions corresponding to the bilevel neighborhood search are given to ensure feasible solutions. Both of global search ability and local search ability of FJSP solving algorithm are considered, and to use genetic algorithm to achieve global search, bilevel neighborhood search to achieve local search. The internationally accepted FJSP benchmark examples are adopted to test the validity of the proposed method.