Hybrid algorithms for Job shop Scheduling Problem with Lot streaming and A Parallel Assembly Stage

Document Type : Research Paper


1 Alzahra University

2 Bu-Ali Sina University


In this paper, a Job shop scheduling problem with a parallel assembly stage and Lot Streaming (LS) is considered for the first time in both machining and assembly stages. Lot Streaming technique is a process of splitting jobs into smaller sub-jobs such that successive operations can be overlapped. Hence, to solve job shop scheduling problem with a parallel assembly stage and lot streaming, decision makers not only need to determine the processing sequences on machines in first stage, but also need to assign each product to a machine and determine the assembly sequences of the products in second stage and the sub-lot sizes of all jobs and products to minimize the makespan. At first, this problem is modeled as a mixed integer linear programming and GAMS software is applied to solve small problems. Since this problem is classified as NP-hard, four hybrid algorithms based on iterative procedures are suggested to solve the problem in medium and large dimensions. In order to verify the effectiveness of the proposed algorithms, a statistical analysis is used along with Relative Percentage Deviation (RPD) factor. Computational results revealed that the hybrid genetic and parallel simulated annealing algorithm (HGAPSA) and the hybrid genetic and parallel variable neighborhood search algorithm (HGAPVNS) perform better than the other proposed algorithms with respect to the objective function. Also, considering lot streaming for both stages instead of applying it only to the first stage leads to achieve better solutions. Finally, the HGAPSA algorithm is compared with a hybrid genetic algorithm (HGA). Experimental results showed that the HGAPSA outperforms the HGA in terms of solution quality.


Main Subjects

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.
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.
Cummings, D.H.,&Egbelu, P.J. (1998). Minimizing production flow time in a process and assembly jobshop. 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 jobshop 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). Amathematical model and extension algorithm for assembly flexible flow shop scheduling problem. International Journal of Advanced Manufacturing Technology, 65 (5),787-802.
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.
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.
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.

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.
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.
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
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 , C.Y. ,  Li, P.,  Guan, Z., Rao, Y. (2007).   A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research, 34 (11), 3229-3242.

Zhang, R.,&Cheng, W. (2011). A simulated annealing algorithm based on blocking properties for the jobshop scheduling problem with total weighted tardiness objective. Computer and operation research, 38 (5), 854-867.