An Evolutionary Solution to a Multi-objective Scheduling Problem

Abstract

Multi-objective problems have been attractive for most researchers because of its diversity in different areas, reality coming from real life applications and insolvability in polynomial time. Therefore, many algorithms including heuristics and/or evolutionary ones were developed to solve such problems. In this research, we propose a genetic algorithm approach to solve a bicriteria scheduling problem in identical parallel machines. Based on different lambda values, we try to minimize the combination of makespan (C-max) and tardiness (T-max). The problems with those objective functions are proven to be NP-hard in the literature and this combination of the problem is not studied before for parallel machines, to the best of our knowledge. The proposed solution is fairly broad to adapt to other scheduling problems.