Exact and Local Search Algorithms to Minimize Multicriteria Scheduling Problem

Abstract

In this article , we consider the Multicriteria scheduling problem on a single machine for minimizing the sum of total completion time (∑C_j) with the total tardiness (∑T_j) and maximum earliness (E_max). We propose a branch and bound (BAB) algorithm to find the optimal solution for the problem. In this BAB algorithm, a lower bound (LB) based on the decomposition property of the Multicriteria problem is used. Two local search algorithms, descent method (DM) and simulated annealing (SA) are applied for the problem. The algorithms DM and SA are compared with the BAB algorithm in order to evaluate effectiveness of the solution methods. Conclusions are formulated on the efficiency of the algorithms, Based on findings of computational experiments.