Modelling and solving the job shop scheduling Problem followed by an assembly stage considering maintenance operations and access restrictions to machines

Abstract

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