A Hybrid Approach for Efficiently Solving Multi-Criteria Scheduling Problems on a Single Machine

Abstract

The presented study investigates the scheduling regarding  jobs on a single machine. Each  job is processed with no interruptions and becomes available for processing at time 0. The aim is to find a processing order with regard to jobs, minimizing “multi-criteria and multi-objective” for two problems. The first problem considers the summation completion time , summation late work , and maximal tardiness , while the second problem considers the total completion time , total earliness , and maximum tardiness . In addition, a sub-problem is presented for each problem and denoted by 1//  and 1//  for the first and second problems, respectively, which is an NP-hard problem. Two meta-heuristics methods “particle swarm optimization (PSO) and bee algorithm (BA)” were applied to acquire the optimal or near-optimal solution. Meta-heuristics methods solve problems of up to  jobs. Finally, in an attempt to increase the overall search efficiency, a hybrid algorithm was created by combining two algorithms, a hybrid between  and  was created to create an alternative search method that incorporates the best properties that each method offers during problem-solving. Moreover, by comparing the performance of local search methods with a hybrid strategy, the hybrid strategy method outperforms BA and PSO. In addition, it can solve problems up to  jobs. Arithmetic results are calculated by coding (programming) algorithms using (MATLAB 2019a).