A Genetic-based Algorithm to Find Better Estimation of Non-Dominated Solutions for a Bi-objective Re-entrant Flowshop Scheduling Problem with Outsourcing

摘要

In this paper, we present a mathematical model for a flowshop scheduling problem with two machines in which each job visits both machines twice. Due to the strict due dates, tardiness is not allowable so the scheduler needs to choose the jobs for being processed in-house and therefore outsources the remaining jobs. This decision shall be made regarding two objective functions: minimization of total completion time for in-house jobs and minimization of outsourcing cost. Since the problem is NP-hard, we propose a genetic-based algorithm to find non-dominated solutions for large-sized problems. By defining efficient dominance properties rather than Pareto and a secondary criterion for making diversification in the population different from crowding distance, we focus our search on middle part of Pareto-front as we believe that the solutions located in this part are more interesting for the decision maker. We compare the quality of solutions found by our proposed algorithm with the simplest variant of NSGA-II. Although proposed algorithm is able to find limited number of non-dominated solutions, the quality of the solutions are improved significantly.