MODELING AND SCHEDULING HYBRID FLOWSHOP WITH BATCH PROCESSING MACHINES

Although batch scheduling has attracted many researchers, they mainly focus on ow shop scheduling problems. Yet, in real world industries, we rarely have a production system with only one processor at each working station. Machines are usually duplicated in parallel at each station to balance the production capacity of shop oor and to decrease the impact of bottleneck stations. This paper deals with a hybrid ow shop scheduling problem with batch processing machines (BPMs). The objective is to minimize makespan (i.e., maximum completion time of jobs). Batch processing machines can simultaneously process several jobs in a batch. The processing time of a batch is the longest processing time among all the jobs in that batch. Once a batch is formed by a set of jobs, it cannot be changed over stages. As the rst study, in this paper, a mathematical model in form of a mixed integer linear programming model is proposed for the mentioned problem. Using CPLEX, the small-sized instances of the problem can be solved to optimality by the model. Yet, due to the NP-hardness of the problem under study, large instances cannot be optimally solved in a reasonable amount of time. Consequently, a novel population-based algorithm based on imperialist competitive metaheuristic algorithm is also proposed. This algorithm includes some advanced features of imperialist behavior mechanisms, imperialist competition operators, and revolutionary phases. The proposed algorithm is rst nely tuned using Taguchi method. Then, to evaluate the proposed algorithm, its eectiveness is compared with a commercial solver (CPLEX) and two available metaheuristics algorithms in the literature, a simulated annealing algorithm, and a particle swarm optimization algorithm. In this regard, a set of large instances is generated and the tested algorithms are compared. The computational results indicate ecient performance of the proposed algorithm over the existing metaheuristics.