Designing a Multi Objective Job Shop Scheduling Model and Solving it by Simulated Annealing

Document Type : Original Article

Authors

1 MS, Tarbiat Modares University.

2 Professor, Tarbiat Modares University.

3 Ph.D., Tarbiat Modares University.

Abstract

Jobshop manufacturing system is a suitable system for economical manufacturing of parts family and Jobshop scheduling is completely efficient in successfully running in improvement of productivity of system. The jobshop scheduling model has multiple objectives: Minimizing makes pan (Cmax) and Minimizing the Weighted Sum of Earliness and Tardiness penalties (WSET). In this study to achieve these objectives at the same time, Goal Programming (GP) has being used. This model from as computational point of view is NP-Hard, so in this paper we apply the Simulated Annealing (SA) meta-heuristic approach for solve it. One array structure of solution (family parts or parts in family) is used in common methods that lead to decrease of solution space, but in this study hybrid selection of neighborhood structures has been used for determaine the structure of solution; Directed Interchange Scheme (DIS) and Random Interchange Scheme (RIS). The results of research indicate solving goal programming model of Job shop Scheduling by SA is efficient to achieve goals of model.

Keywords

References

1. Abdi, K. M., Abbasi, B. & Dolat Abadi A. (2010). A Simulated Annealing Algorithm for Multi Objective Flexible Job Shop Scheduling With Overlapping In Operations.Journal of Industrial Engineering, 5, 17-28.
2. Ali, M. M., Torn, A. & Viitanen, S. (2002).A direct search Variant of the simulated annealing algorithm for optimization involving continuous variables. Computer and Operations Research, 29, 87-102
3. Bagheri, A., & Zandieh, M., Mahdavi, I., Yazdani, M. (2010). An artificial immune algorithm for the flexible job-shop scheduling problem. Future Gener. Comput. Syst. 26, 533–541.
7. Baker, K. (1990). Scheduling Groups of Jobs in the Two-Machine Flow Shop. Mathematical, Computers and Modeling, 13(3), 29- 36.
8. Fattahi, P., Saidi, M., Jolai, F. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J. Intel. Manuf. 18, 331–342.
9. Frazier, G.V. (1996). An Evaluation of Group Scheduling Heuristics in a Flow-line Manufacturing Cell. International Journal of Production Research, 34(4), 959- 976.
10. GAO, L., Li, X., Wen, X., Lu, C., & Wen, F. (2015). A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem. Computers & Industrial Engineering, 88, 417-429.
11. Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.
12. Groover, M.P. (2008). Automation, Production Systems, and Computer-Integrated Manufacturing, Prentice Hall.
13. Kaplanoğlu, V. (2016). An object-oriented approach for multi-objective flexible job-shop scheduling problem. Expert Systems with Applications, 45, 71-84.
14. Khan, W.A., Raouf, A., Cheng, K. (2011). Virtual Manufacturing. Retrieved from http://www.springer.com/978-0-85729-185-1
15. Kirkpartick, S., Gelatt, C.D.Jr. & Vecchi, M.P. (1983). Science, 220, 4598, 671.
16. Krishna, K., Ganeshan, K., & Janaki Ram, D. (1995). Distributed Simulated Anneasling Algorithms for job shop scheduling.IEEE TRANSACTION ON SYSTEMS, MAN, AND CYBERNETICS, 25(7).
17. Krishnamoorthy, B. & Kamath, M. (2000). Scheduling in a Cellular Manufacturing Environment. A Review of Recent Research, Engineering Valuation and Cost Analysis, 2, 409-423.
18. Logendran, R., Mai, L., Talkington, D. (1995). Combined Heuristics for Bi-level Group Scheduling, Problems. International Journal Production Economics, 38, 133- 145.
19. Mahmoodi, F., Dooley, K. J. & Starr, P. J. (1990). An Investigation of Dynamic Group Scheduling, Heuristics in a Job shop Manufacturing Cell. International Journal of Production Research, 28(9), 1695-1711.
20. Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E. (1953). Journal of Chemical Physics, 21, 1087.
21. Miltenburg. J. (2008).Setting manufacturing strategy for a factory-wiithin-a- factory. International Journal of Production Economics, 113, 307- 323.
22. Naderi, B., Fatemi Ghomi, S.M.T., Aminnayeri, M., Zandieh, M. (2011). Scheduling open shops with parallel machines to minimize total completion time. J. Comput. Appl. Math. 235, 1275–1287.
23. Shahsavari-Pour, N., & Ghasemishabankareh, B. (2013). A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling. Journal of Manufacturing Systems, 32(4), 771-780.
24. Schaller, J. E. (2001). A New Lower Bound for the Flow Shop Group Scheduling Problem. Computers and Industrial Engineering, 41, 151-161.
25. Shafer, S. M., & Charnes, J. M. (1995). A simulation analysis of factors influencing loading practices in cellular manufacturing. International Journal of Production Research, 33(1), 279–290.
26. Shih, W.L., Chien, Y.H., Chung, C.L, Kuo-Ching Ying (2012). Minimizing Total Flow Time in Permutation Flowshop Enviromnt. International Journal of Innovative Computing, 8(10), 6599-6612.
27. Skorin - Kapov, J., & Vakharia, A. J. (1993). Scheduling a Flow – line Manufacturing Cell: a Taboo. Search Approach, International Journal of Production Research, 31(7), 1721-1734.
28. Sridhar, J., & Rajendran, C. (1993). Scheduling in a Cellular manufacturing System: A simulated annealing Approach. International Journal of Production Research, 31(12), 2927-2945.
29. Solimanpur, M., Vrat, P., & Shankar, R. (2004). A heuristic to minimize makespan of cell scheduling problem. International journal of production economics, 88(3), 231-241.
30. Suer, G. A., Saiz, M., & Gonzalez, W. (1999). Evaluation of manufacturing cell loading rules for independent cells. International Journal of Production Research, 37(15), 3445–3468.
31. Vahit, K. (2015). An object-oriented approach for multi-objective flexible job-shop scheduling problem. Expert Systems with Applications. 45, 71-84.
32. Wilhelm, M.R., & Ward, T.L. (1987). Solving Quadratic Assignment Problem by Simulated Annealing. IIE Transactions, 19, 109-119.
33. Xia, W., & Wu, Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48(2), 409-425.
34. Xingong, Z., Yong, W. (2015). Single-machine scheduling CON/SLK due window assignment problems with sum-of-processed times based learning effect. Applied Mathematics and Computation. 250, 628–635.
35. Yang, W. H. (2002). Group scheduling in a two-stage flowshop. Journal of the Operational Research Society, 53(12), 1367-1373.
36. Zhang, G., Shao, X., Li, P., &GAO, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, 56(4), 1309-1318.
37. Zhang, R., Wu, C. (2011). A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective. Computers & Operations Research. 38, 854-867.
38. Zhang, R. (2013). A Simulated Annealing-based Heuristic Algorithm for Job Shop Scheduling to Minimize Lateness. International Journal of Advanced Robotic Systems. 10, 214.
Journal of Industrial Management Perspective
Volume 5, Issue 3 - Serial Number 19
December 2015
Pages 39-63

Files

Share

How to cite

Statistics