CAJ | 학술논문

作为生产调度里面一类典型问题,机器数大于2的 Job-shop 调度(m>2)是一类 NP 完全问题,大规模 Job-shop 问题的有效算法至今仍未找到.在有向图模型基础上,提出通过约束引导方式获取可行调度.提出利用支持向量机通过对小样本学习来实现可互换工序对较为准确选取,以此提高调度方案质量.将求解过程中特殊算例补充到样本库进行后续训练以提高算法性能.数值仿真结果表明所提算法对于大规模 Job-shop 问题求解存在较好效果.
작위생산조도리면일류전형문제,궤기수대우2적 Job-shop 조도(m>2)시일류 NP 완전문제,대규모 Job-shop 문제적유효산법지금잉미조도.재유향도모형기출상,제출통과약속인도방식획취가행조도.제출이용지지향량궤통과대소양본학습래실현가호환공서대교위준학선취,이차제고조도방안질량.장구해과정중특수산례보충도양본고진행후속훈련이제고산법성능.수치방진결과표명소제산법대우대규모 Job-shop 문제구해존재교호효과.
As a kind of typical problem in production scheduling, the scheduling of Job-shop for machines above 2(m>2)is NP complete and the valid algorithm hasn’t been found until now for large scale Job-shop problems. The feasible scheduling can be obtained by adding guided constraint on the basis of directed graph. A method based on Support Vector Machine is constructed to choose accurately the interchangeable operations by learning small samples to obtain better scheduling. The performance of the algorithm presented can be improved by replenishing special problems during running as supplementary samples for the fol-lowing training. The results of simulation show that the algorithm performs well for Job-shop problem.