Journal of Networks, Vol 6, No 7 (2011), 974-981, Jul 2011

Mathematical Model and Hybrid Scatter Search for Cost Driven Job-shop Scheduling Problem

Bai Jie, Sun Kai, Yang Gen Ke


Job-shop scheduling problem (JSP) is one of the most well-known machine scheduling problems and one of the strongly NP-hard combinatorial optimization problems. Cost optimization is an attractive and critical research and development area for both academic and industrial societies. This paper presents a cost driven model of the job-shop scheduling problem in which the solutions are driven by business inputs, such as the cost of the product transitions, revenue loss due to the machine idle time and earliness/tardiness penalty. And then, a new hybrid scatter search algorithm is proposed to solve the cost driven job-shop scheduling problem by introducing the simulated annealing (SA) into the improvement method of scatter search (SS). In order to illustrate the effectiveness of the hybrid method, some test problems are generated, and the performance of the proposed method is compared with other evolutionary algorithms such as genetic algorithm and simulated annealing. The experimental simulation tests show that the hybrid method is quite effective at solving the cost driven job-shop scheduling problem.


cost optimization, job-shop scheduling problem, scatter search, simulated annealing


[1] M. R. Garey, D. S. Johnson, and R. Sethi, “The Complexity of Flowshop and Jobshop Scheduling”, Mathematics of Operations Research, Vol. 1, No. 2, pp.117-129, 1976.

[2] J. Adams, E. Balas, and D. Zawack, “The shifting bottleneck procedure for job shop scheduling”, Management Science, Vol. 34, pp.391–401, 1988.

[3] L. W. Cai, Q. H. Wu, and Z. Z. Yong, “A genetic algorithm with local search for solving the job problems”, Lecture Notes in Computer Science, Vol. 1803, pp.363-365, 2000.

[4] Y. Li, Y. Chen, “A genetic algorithm for job-shop scheduling”, Journal of Software, Vol 5, pp.269-274, 2010.

[5] M. Kolonko, “Some new results on simulated annealing applied to the job shop scheduling problem”, European Journal of Operational Research, Vol. 133, No. 1, pp. 123-13,6, 1999.

[6] V. P. Eswaramurthy, and A. Tamilarasi, “Tabu search strategies for solving job shop scheduling problems”, Journal of Advanced Manufacturing Systems, Vol. 6, No.1, pp.59-75, 2007.

[7] D. Y. Sha, and C. Y. Hsu, “A hybrid particle swarm optimization for job shop scheduling problem”, Computers & Industrial Engineering, Vol. 51, pp.791–808, 2006.

[8] M. Lansiti, and R. Levien, “Strategy as Ecology’, Harvard Business Review, Vol. 3, pp.68-78, 2004.

[9] E. M. Goldratt, and J. Cox, “The Goal - A Process of Ongoing Improvement”, North River Press, Croton-on-Hudson, New York, 1984.

[10] Y. Z. Lu, “Profit driven manufacturing enterprise optimization: Problem and Solution”, Plenary Presentation, Proceedings of 23rd Chinese Control Conference, August, 2004.

[11] L. W. Jiang, Y. Z. Lu, Y. W. Chen, “Cost Driven Solutions for Job-shop Scheduling with GA.”, Control Engineering of China. Vol. 44, pp. 72—74, 2007.

[12] A. Allahverdi, J. N. D. Gupta, and T. Aldowaisan, “A Review of Scheduling Research Involving Set-up Considerations”, Omega, Vol. 27, No.2, pp.219-239, 1999.

[13] D. R. Sule, and K. Y. Huang, “Sequency on two and three machines with set-up, processing and removal times separated”, International Journal of Production Research, Vol. 21, pp.723-732, 1983.

[14] F. Glover, “Scatter search and path relinking”, In: Corne, D., Dorigo, M., Glover, F. (Eds.), New Ideas in Optimization. McGraw-Hill, pp. 297–316, 1999.

[15] R. A. Russel, and W. C. Chiang, “Scatter search for the vehicle routing problem with time windows”, European Journal of Operational Research, Vol. 169, pp.606-622, 2006.

[16] A. Haq, M. Saravanan, A. Vivekraj, and T. Prasad, “A scatter search approach for general flowshop scheduling problem”, International Journal of Advanced Manufacturing Technology, Vol.31, No.7, pp.731-736, 2007.

[17] N. Mansour, C. Kehyayan, H. Khachfe, “Scatter search algorithm for protein structure prediction”, International Journal of Bioinformatics Research and Applications. Vol.5, No.5, 501-15, 2009.

[18] S. Kirkpauick, C. D. Geian, and M. P. Vecchi, “Optimization by simulated annealing”, Science, Vol. 220, pp.671-680, 1983.

[19] H. Fisher. and G. L. Thompson, “Industrial scheduling”, Englewood Cliffs, NJ: Prentice-Hall, 1963.

[20] S. Lawrence, “Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques”, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, 1984.

Full Text: PDF

Journal of Networks (JNW, ISSN 1796-2056)

Copyright @ 2006-2014 by ACADEMY PUBLISHER – All rights reserved.