| 作业车间调度问题解的不可行性检测算法和快速修复算法 |
| |
| 引用本文： | 孙璐,黄志,张惠民,顾文钧.作业车间调度问题解的不可行性检测算法和快速修复算法[J].东南大学学报,2011,27(1):88-91. |
| |
| 作者姓名： | 孙璐 黄志 张惠民 顾文钧 |
| |
| 作者单位： | 孙璐,Sun Lu(东南大学交通学院,南京,210096;Department of Civil Engineering,Catholic University of America,Washington DC 20064,USA);黄志,Huang Zhi(Department of Civil Engineering,Catholic University of America,Washington DC 20064,USA;华中科技大学计算机学院,武汉,430074);张惠民,Zhang Huiming(山西省公路局晋中分局,晋中,030600);顾文钧,Gu Wenjun(Department of Civil Engineering,Catholic University of America,Washington DC 20064,USA) |
| |
| 基金项目： | The US National Science Foundation，the Research Fellowship for International Young Scientists，the Fok Ying-Tong Education Foundation，the Natural Science Foundation of Jiangsu Province，the Postdoctoral Science Foundation of Jiangsu Province |
| |
| 摘 要： | 为了判别作业车间调度问题的解的可行性,提出了一种基于图论的启发式判别算法,并通过实例验证了方法的正确性.提出了普适于作业车间调度问题的快速修补新算法,可以对于作业车间调度问题的不可行解进行修正使之变成可行解.判别算法和修补算法在最不利情形下的计算复杂性均为O(n),判别算法在最有利情形下的计算复杂性为O(2 |J|+|...
|
| 关 键 词： | 不可行解 作业车间调度 修复算法 |
Infeasibility test algorithm and fast repair algorithm of job shop scheduling problem |
| |
| Sun Lu, Huang Zhi, Zhang Huiming Gu Wenjun.Infeasibility test algorithm and fast repair algorithm of job shop scheduling problem[J].Journal of Southeast University(English Edition),2011,27(1):88-91. |
| |
| Authors: | Sun Lu Huang Zhi Zhang Huiming Gu Wenjun |
| |
| Institution: | Sun Lu1,2 Huang Zhi2,3 Zhang Huiming4 Gu Wenjun1(1School of Transportation,Southeast University,Nanjing 210096,China)(2Department of Civil Engineering,Catholic University of America,Washington DC 20064,USA)(3School of Computer Science,Huazhong University of Science and Technology,Wuhan 430074,China)(4Jinzhong Bureau of Highway Administration,Jinzhong 030600,China) |
| |
| Abstract: | 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 scena... |
| |
| Keywords: | infeasibility job shop scheduling repairing algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
