Open Access Open Access  Restricted Access Subscription Access

A NEW HYBRID HEURISTIC TECHNIQUE FOR SOLVING JOB-SHOP SCHEDULING PROBLEM

Cheng-Fa Tsai, Feng-Cheng Lin

Abstract


This paper proposes a new and efficient hybrid heuristic scheme for solving job-shop scheduling problems (JSP). A new and efficient population initialization and local search concept, based on genetic algorithms, is introduced to search the solution space and to determine the global minimum solution to the JSP problem. Simulated results imply that the proposed novel JSP method (called the PLGA algorithm) outperforms several currently used approaches. This investigation also considers a real-life job-shop scheduling system design, which optimizes the performance of the job-shop scheduling system subject to a required service level. Simulation results demonstrate that the proposed method is very efficient and potentially useful in solving job-shop scheduling problems.

Keywords


JSP; genetic algorithms; local search

Full Text:

PDF

References


Cheng-Fa Tsai, Chun-Wei Tsai, and Chin-Chang Tseng. New and efficient ant-based heuristic method for solving the traveling salesman problem, Expert Systems (accepted, will appear in vol. 20, no. 4, 2003).

Cheng-Fa Tsai, Chun-Wei Tsai, and Ching-Chang Tseng. ACOMAC: An Efficient Method for Solving Traveling Salesman Problem. 2002 IEEE International Joint Conference on Neural Network (IJCNN 2002), pp. 1540-1545, Honolulu, Hawaii, USA.

Cheng-Fa Tsai, Chun-Wei Tsai, and Chi-Ping Chen. A Multiple-Searching Approach to Genetic Algorithms for Solving Large Traveling Salesman Problem. 6th Intern. Conf. on Computer Science and Informatics, pp. 362-366, Durham, NC, USA.

J. Adams, E. Balas, D. Zawack. The shifting bottleneck procedures for job shop scheduling. Management Science, vol. 34, pp. 391-401, 1988.

A. Colorni, M. Dorigo, V. Maniezzo, M. Trubian. Ant system for Job-shop Scheduling. JORBEL - Belgian Journal of Operations Research, Statistics and Computer Science, 34(1), pp. 39-53, 1994.

Dell’s Amico M, M. Turbian. Applying tabu search to the job shop scheduling problem. Annual Operations Research, 40, pp. 231-252, 1993.

L. Davis. Applying adaptive algorithms to epistatic domains. In Proc. of the Inter. Joint Conf. on Artificial Intelligence, pp. 162-164, 1985.

D. Applegate, W. Cook. A computational study of the job-shop scheduling instance. ORSA Journal on Computing 3, pp. 149-156, 1991.

E. Taillard. Benchmarks for basic scheduling problems. European Journal of operational Research, 64, pp.278-285, 1993.

E. Falkenauer, S. Bouffoix. A genetic algorithm for job shop. Proc. of the 1991 IEEE international Conference on Robotics and Automation, 1991.

F. Croce, R. Tadei, G. Volta. A genetic algorithm for the job shop problem. Computers & Operations Research, pp. 15-24, 1995.

Guoyong SHI, Hitoshi IIMA, and Nobuo SANNOMIYA. A new Encoding Scheme for Solving Job Shop Problems by Genetic Algorithm. Proc. of the 35th Conference on Decision and Control Kobe, Japan, pp. 4395-4400, 1996.

H. Fisher and G. Thompson. Probabilistic Learning Combinations of Local Hob-Shop Scheduling Rules. In Industrial Scheduling, J. Muth and G. Thompson eds.,Prentice-Hall, pp. 1225-1251, 1963.

Hong Zhou, Yuncheng Feng, Limin Han. The hybrid heuristic genetic algorithm for job shop scheduling. Computer & Industrial Engineering, pp. 191-200, 2001.

Kyung-Mi Lee and Takeshi Yamakawa. A genetic Algorithm for General Machine Scheduling Problems. 2nd International Conference on Knowledge-based Intelligent Electronic Systems, pp. 60-66, 1998.

S. Kobayashi, I One, M. Yamamura. An efficient genetic algorithm for job shop scheduling problems. Proc. of the sixth International Conference on Genetic Algorithms. San Francisco, CA: Morgan Kaufmann Publishers, pp. 506-511, 1995.

Koji Morikawa, Takeshi Furuhashi, Yoshiki Uchikawa. Single Populated Genetic Algorithm and its Application to Job-shop Scheduling. Proc. of Industrial Electronics, Control, Instrumentation, and Automation on Power Electronics and Motion Control, pp. 1014-1019, 1992.

L. Wang, D.-Z. Zheng. An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research 28, pp. 585-596, 2001.

L. Wang and D.-Z. Zheng. A Modified Genetic Algorithm for Job Shop Scheduling. The International Journal of Advanced Manfacturing Technology by Springer-Verlag, vol. 20, pp. 72-76, 2002.

M. Kolonko. Some new results on simulated annealing applied to the job shop scheduling problem. European Journal of Operational Research, pp. 123-136, 1999.

M. Gen and R. Cheng. Genetic Algorithms and Engineering Design. John Wiley&Sons, New York, 1997.

M. Pinedo. Scheduling: theory, algorithm, and systemd. Prentice-Hall, Englewood Cliffs, NJ, 1995.

E. Nowicki, C. Smutnicki. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, vol. 42, pp. 797-813, 1996.

K. Oey, S.J. Mason. Scheduling batch processing machines in complex job shops. Conference Proceedings of the winter on Simulation, vol. 2, pp. 1200-1207, 2001.

I One, M. Yamamura, S. Kobayashi. A genetic algorithms for job-based order crossover. Proc. of the Third IEEE Conference on Evolutionary Computation. Japan, pp. 547-52, 1996.

R. Cheng, Mitsuo Gen and Yasuhiro Tsujimura. A tutorial Survey of job-shop scheduling problem using genetic algorithm-I. Reprentation. Computer ind. Engng vol. 30, no. 4, pp. 983-997, 1996.

S. Lawrence. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. Graduate School of Industrial Administration, Pittsburgh, Carnegie-Mellon University, 1984.

Van Laarhoven PJM, Aarts EHL, and Lenstra JK. Job shop scheduling by simulated annealing. Operations Research, 40, pp.113-125, 1992.

Xiu Li, Wenhuang Liu, Shouju Ren, and Xuerui Wang. A solution of job-shop scheduling problems based on genetic algorithms. IEEE International Conference on Systems, Man, and Cybernetics, vol. 3, pp. 1823 -1828, 2001.

Yoon-Pin Simon Foo and Yoshiyasu Takefuji. Stochastic Neural Networks for Solving job-shop scheduling part 1. Problem representation. IEEE International Conference on Neural Networks, vol. 2, pp. 275 -282, 1988.

Y. Tsujimura, M. Gen and Y. Mafune. Relations between Evaluation Functions and Schedule-structures in GA-based Job-Shop Scheduling. Technical Report of IEICE in Japanese, AI99-13, pp. 17-24, 1999.

Y. Tsujimura, M. Gen and R. Cheng .Improved Genetic Algorithms for Solving Job-shop Scheduling Problem. Engineering Design and Automation, vol. 3, no. 2, pp. 133-144, 1997.

Y. Tsujimura, Y. Mafune and M. Gen. Effects of Symbiotic Evolution in Genetic Algorithms for Job-Shop Scheduling. Proc. of the 34th Hawaii International Conference on System Sciences, 2001.

Y. Tsujimura, T. Sugimoto, Y Mafune and M. Gen. A Genetic Algorithm for Job-shop Scheduling by Means of Symbiosis Mechanism. Proc. of the 3rd Australia-Japan Joint Workshop on Intelligent and Evolutionary Systems, Canberra, Australia, pp. 228-231, 1999


Refbacks

  • There are currently no refbacks.