一种基于最小二乘支持向量机JSP调度算法  

An Algorithm Based on Least Squares Support Vector Machine for Job-shop Problem

作　　者：李文超[1] 杨宏兵[2] 

机构地区：[1]江苏大学汽车与交通工程学院,江苏镇江212013 [2]苏州大学机电工程学院,苏州215021

出　　处：《组合机床与自动化加工技术》2011年第12期14-17,共4页Modular Machine Tool & Automatic Manufacturing Technique

基　　金：国家自然科学基金(51005160);江苏省高校自然科学研究项目(10KJB410001)

摘　　要：作为生产调度里面一类典型问题,Job-shop问题的求解是属于NP完全的,对于大规模Job-shop问题的有效算法至今仍未找到。在有向图模型基础上,提出通过约束引导方式获取可行调度。提出使用最小二乘支持向量机对样本学习实现可互换工序对准确选取,以此提高调度方案质量。将求解过程中特殊算例补充到样本库进行后续训练以提高算法性能。数值仿真结果表明所提算法对于大规模Job-shop问题求解存在较好效果。As a kind of typical problem in production scheduling,the solving of Job-shop problem belongs to 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 least squares support vector machine is constructed to choose accurately the interchangeable operations by learning small samples to obtain the better scheduling.The performance of the algorithm presented can be improved by replenishing special problems during running as supplementary samples for the follow ing training.The results of simulation show that the algorithm performed w ell for Job-shop problem.

关 键 词：最小二乘支持向量机 JOB-SHOP调度 约束引导 

分 类 号：TH16[机械工程—机械制造及自动化] TG65[金属学及工艺—金属切削加工及机床]