[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

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.

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