Title: Single machine multi-criteria scheduling problem: total completion time, maximum lateness, and maximum earliness performance measures

Authors: Saheed Akande; Ganiyu O. Ajisegiri

Addresses: Department of Mechanical and Mechatronics Engineering, Afe Babalola University, Ado-Ekiti, Nigeria ' Department of Industrial and Production Engineering, University of Ibadan, Ibadan, Nigeria

Abstract: This paper considers the multi-criteria scheduling problem with total completion time, maximum lateness, and maximum earliness as the objectives. The problem is a minimisation problem; the total completion time, a MIN-SUM problem, the maximum earliness, a MIN-MAX problem, and the maximum lateness, a MIN-MAX problem. Though, the problem is NP-hard, shortest processing time (SPT) rule, yields optimal for total completion time while early due date rule (EDD) is the optimal solution for maximum lateness and maximum earliness if each criterion were to be considered separately. Two heuristics, named SOL I and SOL II were proposed and the results for each of the criteria were compared to the optimal of the sub-problems. Results of the computational experiment on small job-sizes (5 ≤ n ≤ 30) and large job-sizes (40 ≤ n ≤ 100) show that the two heuristics results are not significantly different from the optimal at 99% significant level for total completion time and maximum lateness performance measures. However, for maximum earliness, the optimal solutions are significantly better than the two proposed heuristics.

Keywords: multi-criteria scheduling problem; MIN-SUM problem; MIN-MAX problem; optimal; computational experiment.

DOI: 10.1504/IJPS.2021.115618

International Journal of Planning and Scheduling, 2021 Vol.3 No.2, pp.140 - 159

Received: 20 Jul 2020
Accepted: 09 Jan 2021

Published online: 14 Jun 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article