Infeasibility test algorithm and fast repair algorithm of job shop scheduling problem  

作业车间调度问题解的不可行性检测算法和快速修复算法(英文)

作　　者：孙璐[1,2] 黄志[2,3] 张惠民 顾文钧 

机构地区：[1]东南大学交通学院,南京210096 [2]Department of Civil Engineering,Catholic University of America [3]华中科技大学计算机学院,武汉430074 [4]山西省公路局晋中分局,晋中030600

出　　处：《Journal of Southeast University(English Edition)》2011年第1期88-91,共4页东南大学学报（英文版）

基　　金：The US National Science Foundation (No. CMMI-0408390, CMMI-0644552);the Research Fellowship for International Young Scientists (No. 51050110143);the Fok Ying-Tong Education Foundation(No. 114024);the Natural Science Foundation of Jiangsu Province (No.BK2009015);the Postdoctoral Science Foundation of Jiangsu Province (No.0901005C)

摘　　要：To diagnose the feasibility of the solution of a job-shop scheduling problem（JSSP）,a test algorithm based on diagraph and heuristic search is developed and verified through a case study.Meanwhile,a new repair algorithm for modifying an infeasible solution of the JSSP to become a feasible solution is proposed for the general JSSP.The computational complexity of the test algorithm and the repair algorithm is both O（n） under the worst-case scenario,and O（2J＋M） for the repair algorithm under the best-case scenario.The repair algorithm is not limited to specific optimization methods,such as local tabu search,genetic algorithms and shifting bottleneck procedures for job shop scheduling,but applicable to generic infeasible solutions for the JSSP to achieve feasibility.为了判别作业车间调度问题的解的可行性,提出了一种基于图论的启发式判别算法,并通过实例验证了方法的正确性.提出了普适于作业车间调度问题的快速修补新算法,可以对于作业车间调度问题的不可行解进行修正使之变成可行解.判别算法和修补算法在最不利情形下的计算复杂性均为O(n) ,判别算法在最有利情形下的计算复杂性为O(2|J|+|M|) .所提出的算法具有很大的灵活性,对于局部蚂蚁算法、遗传算法以及一般的作业车间调度问题均适用.

关 键 词：INFEASIBILITY job shop scheduling repairing algorithm 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]