On a bi-criteria flow shop scheduling problem under constraints of blocking and sequence dependent setup time
- PDF / 645,952 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 169 Views
On a bi-criteria flow shop scheduling problem under constraints of blocking and sequence dependent setup time Said Aqil1
· Karam Allali1
© Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract In this paper, we propose a bi-criteria optimization model for a flow shop scheduling problem with permutation, blocking and sequence dependent setup time. Indeed, these constraints are the most encountered in the industrial field, which demands high command flexibility. The objective is the minimization of two criteria, in our case the makespan and the total tardiness combined in a single objective function with a weighting coefficient for each criterion. To solve this problem, we propose a mixed integer linear programming method and a set of different metaheuristics. The suggested metaheuristics are; the genetic algorithm, the iterated greedy metaheuristic and the iterative local search algorithm. This last algorithm is proposed in two ways of exploration of the neighborhood. To verify the effectiveness of our resolution algorithms, a set of instances with n jobs and m machines is randomly generated from small instances to relatively large size ones. The analysis of the suggested simulation model allowed us to note that the iterative local search algorithm gives good results compared to the iterative greedy algorithm. Moreover, it was found that the weighting parameter plays an essential role in the problem decision making. However, it was established that it is difficult to find a good solution that minimizes both criteria at once, a suitable compromise will be necessary to be adopted using the weighting coefficient. Keywords Flow shop · Sequence-dependent setup time · Blocking · Bi-criteria optimization · Mixed integer linear programming · Metaheuristic
1 Introduction The blocking flow shop scheduling problem (BFSP) under constraint sequence-dependent setup time (SDST) is one of the most attractive problems in industrial optimization. The constraint of the blocking is often imposed when the stock is of null capacity between the machines. On the other hand, the setup time is important to be considered, for the execution
B
Said Aqil [email protected] Karam Allali [email protected]
1
Laboratory Mathematics and Applications, University Hassan II of Casablanca, FST, P.O. Box 146, Mohammedia, Morocco
123
Annals of Operations Research
of a new job, when the machine requires a time of adjustment or cleaning etc. These two constraints are of great industrial importance that can influence the scheduling plan and therefore the proper decision-making. Hence, recent works on the study of single or multi-objective (MO) scheduling problems under one or both of these constraints have been fullfilled. For instance, Nouri and Ladhari (2018) presented a resolution approach using the non sorting genetic algorithm (NSGA) for solving a multi-objective BFSP. Also, we note that in Takano and Nagano (2017), we find a mixed integer linear programming (MILP) formulation and branch and bound (BB) procedures to mini
Data Loading...
