عنوان مقاله [English]
Although batch scheduling has attracted many researchers, they mainly focus on flow 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 floor and to decrease the impact of bottleneck stations. This paper deals with a hybrid flow 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 first 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 first finely tuned using Taguchi method. Then, to evaluate the proposed algorithm, its effectiveness 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 efficient performance of the proposed algorithm over the existing metaheuristics.