Modelling and solving the job shop scheduling Problem followed by an assembly stage considering maintenance operations and access restrictions to machines
الموضوعات :Seyed Mohammad Hassan Hosseini 1
1 - Department of Industrial Engineering and Management, Shahrood University of Technology, Shahrood, Iran
الکلمات المفتاحية: Job shop, Assembly, Maintenance operations, Access restrictions to machines,
ملخص المقالة :
This paper considers job shop scheduling problem followed by an assembly stage and Lot Streaming (LS). It is supposed here that a number of products have been ordered to be produced. Each product is assembled with a set of several parts. The production system includes two stages. The first stage is a job shop to produce parts. Each machine can process only one part at the same time. The second stage is an assembly shop that contains several parallel machines. Maintenance operations and access restrictions to machines in the first stage are also considered. The objective function is to minimize the completion time of all products (makespan). At first, this problem is described and modelled as a mixed integer linear programming, and GAMS software is applied to solve small-sized problems. Since this problem has been proved to be strongly NP-hard, two new algorithms based on GA and SA are developed to solve the medium- and large-sized problems. In order to verify the effectiveness of the proposed algorithms, a statistical analysis is used along with Relative Percentage Deviation (RPD) factor and well-known criterion. IMP. Various problems are solved by the proposed algorithms. Computational results reveal that both of the two proposed algorithms have good performance. However, the method based on the genetic algorithm performs better than the other proposed algorithm with respect to the objective functi
Al-Anzi, F.S. &Allahverdi, A. (2013). An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time. Journal of Manufacturing Systems, 32 (4), 825– 830.
Allahverdi A, Al-Anzi F. S (2009). The two-stage assembly scheduling problem to minimize total completion time with setup times. Computers & Operations Research, 36:2740-2747
Berrichi, A., Amodeo, L., Yalaoui, F., Châtelet, E., Mezghiche, M. (2008). Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem. Journal of Intelligent Manufacturing, 20: 389-400.
Buscher, U., & Shen, L. (2009). An integrated tabu search algorithm for the lot streaming problem in job shops. European Journal of Operational Research, 199 (2), 385-399.
Cui, W., Lu, Z., Li, C., & Han, X. (2018). A proactive approach to solve integrated production scheduling and maintenance planning problem in flow shops. Computers & Industrial Engineering 115 (2018) 342–353.
Cummings, D.H., & Egbelu, P.J. (1998). Minimizing production flow time in a process and assembly job shop. International Journal of Production Research, 36(8), 2315–2332.
Chan, F.T.S., Wong, T.C., & Chan, L.Y. (2008). Lot streaming for product assembly in job shop environment. Robotics and Computer-Integrated Manufacturing, 24 (3), 321–331.
Chan, F.T.S., Wong, T.C., &Chan, L.Y. (2009). An evolutionary algorithm for assembly job shop with part sharing. Computers & Industrial Engineering, 57 (3), 641–651.
Chen, J., &Steiner, G. (1997). Lot streaming with detached setups in three-machine flow shops. European Journal of Operational Research. 96(3), 591-611.
Daneshamooz, F., Jabbari, M., &Fattahi, P. (2013). A model for job shop scheduling with a parallel assembly stage to minimize makespan. Journal of Industrial Engineering Research in Production Systems, 2(4), 39-53.
Dauzere-Peres, S., &Lasserre, J.B. (1993). An iterative procedure for lot streaming in job-shop scheduling. Computers & Industrial Engineering, 25 (4), 231-234.
Demir, Y., &Isleyen, S.K. (2014). An effective genetic algorithm for flexible job-shop scheduling with overlapping in operations. International Journal of Production Research, 52(13), 3905-3921.
Eschelman, L., Caruana, R., &Schaffer, D. (1989). Biases in the crossover landscape. Proc. Third international conference on genetic algorithms, Morgan Kaufman Publishing, 21-29.
Fattahi, P., Hosseini, S.M.H., &Jolai, F. (2013). A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem. International Journal of Advanced Manufacturing Technology, 65 (5), 787-802.
Fattahi, P., Daneshamooz, F. (2017). Hybrid algorithms for job shop scheduling problem with lot streaming and a parallel assembly stage. Journal of Industrial and Systems Engineering, 10: 92-112.
Garey, M.R., Johnson, D.S., &sethi, R. (1976). The Complexity of flow shop and job shop scheduling. Mathematics of Operation Research, 1 (2), 117-129.
Jeong, H., Park, J., &Leachman, R.C. (1999). A batch splitting method for a job shop scheduling problem in an MRP environment. International Journal of Production Research, 37 (15), 3583-3598.
Khoukhi, F.E., Boukachour, J., Hilali Alaoui, A.E., (2017). The “Dual-Ants Colony”: A Novel Hybrid Approach for the Flexible Job Shop Scheduling Problem with Preventive Maintenance. Computers & Industrial Engineering, 106, 236-255.
Koulamas Ch, Kyparisis G. J (2001). The three-stage assembly flow shop scheduling problem. Computers & Operations Research 28:689-704
Krikpatrick, S., Gelatt, C.D., &Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220 (4598), 671-680.
Lee, C.Y., Cheng, T.C.E., &Lin, B.M.T. (1993). Minimizing the makespan in the 3-machine assembly-type flow shop scheduling problem. Management Science, 39 (5), 616-625.
Lei, D., &Guo, X. (2013). Scheduling job shop with lot streaming and transportation through a modified artificial bee colony. International Journal of Production Research, 51(16), 4930-4941.
Maleki-Darounkolaei, A., Modiri, M., Tavakkoli-Moghadam, R., &Seyyedi, I. (2012). A three-stage assembly flow shop scheduling problem with blocking and sequence depended setup times. Journal of Industrial Engineering International, 8:26.
Manne, A.S. (1960). On the job shop scheduling problem. Operational Research, 8 (2), 219-223.
Mohammadi, E. (2016). Multi objective job shop scheduling problem with an assembly stage and lot streaming .Master of Science Thesis, Buali-Sina University.
Mokhtari, H., Dadgar, M. (2015). Scheduling optimization of a stochastic flexible job-shop system with time-varying machine failure rate. Computers & Operations Research, 61: 31-45.
Navaei, J., Fatemi-Ghomi, S.M.T., Jolai, F., &Mozdgir, A. (2014). Heuristics for an assembly flowshop with non-identical assembly machines and sequence dependent setup times to minimize sum of holding and delay costs. Computers & Operations Research, 44, 52–65.
Nejati, M., Mahdavi, I., Hassanzadeh, R., &Mahdavi-Amiri, N. (2016). Lot streaming in a two-stage assembly hybrid flow shop scheduling problem with a work shift constraint. International Journal of Production Research, 33(7), 459-471.
Potts C.N, Sevast'Janov S.V, Strusevich V. A, Van Wassenhove L.N, Zwaneveld C.M (1995). The two-stage assembly scheduling problem: Complexity and approximation. Operations Research 43:346-355.
Reiter, S. (1966). A system for managing job-shop production. Journal of Business, 39 (3), 371–393.
Seyedi, I., Maleki-Daronkolaei, A., &Kalashi, F. (2012). Tabu search and simulated annealing for new three-stage assembly flow shop scheduling with blocking. Interdisciplinary Journal of Contemporary Research In Business, 4 (8), 394-402.
Spears, W. M., &De Jong, K. A. (1991). On the virtues of uniform crossover. Proceedings of the Fourth International Conference on Genetic Algorithms, 230-236.
Wagner, B.J., &Ragatz, G. (1994). The impact of lot splitting on due date performance. Journal of Operations Management, 12 (1), 13-25.
Wagner, H. (1959). An integer linear-programming model for machine scheduling. Naval Research logistics Quarterly, 6 (2), 131-140.
Wang, S., & Liu, M. (2014). Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method. International Journal of Production Research, 52(5), 1495–1508.
Wong, T.C., Chan, F.T.S., &Chan, L.Y. (2009). A resource-constrained assembly job shop scheduling problem with Lot Streaming technique. Computers & Industrial Engineering, 57 (3), 983–995.
Wong, T.C., &Ngan, S.C. (2013). A comparison of hybrid genetic algorithm and hybrid particle swarm optimization to minimize makespan for assembly job shop. Applied Soft Computing, 13(3), 1391–1399.
Xiao, L., Song, S., Chen, X., and Coit, D.W. (2016). Joint optimization of production scheduling and machine group preventive maintenance. Reliability Engineering & System Safety, 146, 68–78.
Xiong, F., Xing, K., &Wang, F. (2015). Scheduling a hybrid assembly-differentiation flow shop to minimize total flow time. European Journal of Operational Research, 240, 338-354
Yao L., &Sarin, C.S. (2014). Multiple-Lot Lot Streaming in a Two-stage Assembly System. Essays inProduction Project Planning and Scheduling, Springer US.
Yazdani, M., Amiri, M., &Zandieh, M. (2010). Flexible job shop scheduling with parallel variable neighborhood search algorithm. Expert system with applications, 37(1), 678-687.
Yokoyama, M., &Santos, D.L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research, 161, 754–770.
Zhang, R., &Cheng, W. (2011). A simulated annealing algorithm based on blocking properties for the job shop scheduling problem with total weighted tardiness objective. Computer and operation research, 38 (5), 854-867.
