Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (9): 240-242.

Previous Articles     Next Articles

Method for solving Job-shop problem applying Support Vector Machine

LI Wenchao1, YANG Hongbing2, MA Taofeng3   

  1. 1.School of Automobile and Traffic Engineering, Jiangsu University, Zhenjiang, Jiangsu 212013, China
    2.School of Mechanical and Electric Engineering, Soochow University, Suzhou, Jiangsu 215021, China
    3.Chassis Department, Pan Asia Technical Automotive Center Co., Ltd, Shanghai 201201, China
  • Online:2013-05-01 Published:2016-03-28

一种用支持向量机求解Job-shop问题方法

李文超1,杨宏兵2,马涛锋3   

  1. 1.江苏大学 汽车与交通工程学院,江苏 镇江 212013
    2.苏州大学 机电工程学院,江苏 苏州 215021
    3.上海泛亚汽车技术中心有限公司 底盘部,上海 201201

Abstract: 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 following training. The results of simulation show that the algorithm performs well for Job-shop problem.

Key words: Support Vector Machine(SVM), Job-shop, constraint guided

摘要: 作为生产调度里面一类典型问题,机器数大于2的Job-shop调度(m>2)是一类NP完全问题,大规模Job-shop问题的有效算法至今仍未找到。在有向图模型基础上,提出通过约束引导方式获取可行调度。提出利用支持向量机通过对小样本学习来实现可互换工序对较为准确选取,以此提高调度方案质量。将求解过程中特殊算例补充到样本库进行后续训练以提高算法性能。数值仿真结果表明所提算法对于大规模Job-shop问题求解存在较好效果。

关键词: 支持向量机, Job-shop, 约束引导