[1] Sun Lu, Huang Zhi, Zhang Huiming, et al. Infeasibility test algorithm and fast repair algorithmof job shop scheduling problem [J]. Journal of Southeast University (English Edition), 2011, 27 (1): 88-91. [doi:10.3969/j.issn.1003-7985.2011.01.018]

Copy

Infeasibility test algorithm and fast repair algorithmof job shop scheduling problem()

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

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

27

Issue:

2011 1

Page:

88-91

Research Field:

Computer Science and Engineering

Publishing date:

2011-03-30

Info

Title:

Infeasibility test algorithm and fast repair algorithmof job shop scheduling problem

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

Author(s):

Sun Lu¹;  2;  Huang Zhi²;  3;  Zhang Huiming⁴;  Gu Wenjun¹

¹School of Transportation, Southeast University, Nanjing 210096, China
²Department of Civil Engineering, Catholic University of America, Washington DC 20064, USA
³School of Computer Science, Huazhong University of Science and Technology, Wuhan 430074, China
⁴Jinzhong Bureau of Highway Administration, Jinzhong 030600, China

孙璐¹;  2;  黄志²;  3;  张惠民⁴;  顾文钧²

¹东南大学交通学院, 南京 210096; ²Department of Civil Engineering, Catholic University of America, Washington DC 20064, USA; ³华中科技大学计算机学院, 武汉 430074; ⁴山西省公路局晋中分局, 晋中 030600

Keywords:

infeasibility;  job shop scheduling;  repairing algorithm

不可行解;  作业车间调度;  修复算法

PACS:

TP391

DOI:

10.3969/j.issn.1003-7985.2011.01.018

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(2|J|+|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|).所提出的算法具有很大的灵活性, 对于局部蚂蚁算法、遗传算法以及一般的作业车间调度问题均适用.

References:

[1] Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness [M]. San Francisco: Freeman, 1979.
[2] Jain A S, Meeran S. Deterministic job-shop scheduling: past, present, and future [J]. European Journal of Operational Research, 1999, 113(2):390-434.
[3] Jain A S, Meeran S. A state-of-the-art review of job-shop scheduling techniques [R]. Nethergate, Dundee, UK: Department of Applied Physics, Electronics and Mechanical Engineering of University of Dundee, Scotland, 1998.
[4] Balas E, Vazacopoulos A. Guided local search with shifting bottleneck for job shop scheduling [J]. Management Science, 1998, 44(2):262-275.
[5] Luh P B, Zhao X, Wang Y, et al. Lagrangian relaxation neural networks for job shop scheduling [J]. IEEE Transactions on Robotics and Automation, 2000, 16(1):78-88.
[6] Geyik F, Cedimoglu I H. The strategies and parameters of tabu search for job-shop scheduling [J]. Journal of Intelligent Manufacturing, 2004, 15(4):439-448.
[7] Murovec B, Suhel P. A repairing technique for the local search of the job-shop problem[J].European Journal of Operational Research, 2002, 153(1): 220-238.
[8] Mattfeld D C. Evolutionary search and the job shop: investigations on genetic algorithms for production scheduling [M]. Heidelberg, Germany: Physica-Verlag, 1996.
[9] Adams J, Balas E, Zawack D. The shifting bottleneck procedure for job shop scheduling [J]. Management Science, 1988, 34(3):391-401.
[10] Balas E. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm [J]. Operations Research, 1969, 17(6): 941-957.

Memo

Memo:

Biography: Sun Lu(1972—), male, doctor, professor, sunl@cua.edu.
Foundation items: 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).
Citation: Sun Lu, Huang Zhi, Zhang Huimin, et al. Infeasibility test algorithm and fast repair algorithm of job shop scheduling problem[J].Journal of Southeast University(English Edition), 2011, 27(1):88-91.[doi:10.3969/j.issn.1003-7985.2011.01.018]

Common functions