Using Evolving Algorithms to Solve Bi-Criteria-Objective Function Machine Scheduling Problems

Abstract

     This research examines the suitability of two new local search-based metaheuristics (i.e., Simulated Annealing (SA) and Particle Swarm Optimisation (PSO)) for addressing single-machine scheduling problems in terms of two complementary objective functions:  and . We also analyze the interaction of the two objectives while converting the maximum lateness into the actual goal function to create the problem formulation, which needs to be solved while simultaneously minimizing the total completion time and the maximum lateness. The methods here proposed are compared to the Branch-And-Bound (BAB) method coupled with some high-performance Greedy Heuristics (GH). The experimental results indicate that SA and PSO are generally significantly more effective than their exact and heuristic counterparts and that they are very robust optimization methods for complex scheduling problems with various conflicting objectives.