A hybrid genetic algorithm for parallel machine scheduling problem with consumable resources

Abstract : This paper deals with the scheduling problem on identical parallel machines when each job depends on the amount of consumed resource and is characterized by different resource requirements. A typical workshop configuration is chosen for detailed study and analysis under several assumptions. This problem is known as NP-hard. To solve it, an integer linear programming based position variables and a genetic algorithm are proposed. A local search procedure is proposed to provide improved solutions. Since small instances of the problem can be solved optimally, the genetic algorithm (with and without local search) were compared to an exact resolution method which enumerates all possible solutions determined from a mathematical model. However, for medium or large instances, the proposed approaches effectiveness is checked on the basis of a heuristic. The analysis of results reveals that the hybrid genetic algorithm performs the best for different structure.