Single Machine Scheduling Based on EDD-SDST-ACO Heuristic Algorithm

Abstract

A large number of changeovers exist in multi-item and small lot size production mode, which lead to a long setup time and significantly influence productivity. However, setup time has received significantly less attention in previous studies regarding the single machine scheduling (SMS) problem. This paper investigates the SMS problem with sequence-dependent setup time (SDST). First, a model of SMS-SDST is developed to minimise the makespan. An earliest due date (EDD), SDST, and ant colony optimisation (ACO) heuristic algorithm is presented. In order to evaluate the performance of the proposed algorithm, Taguchi’s robust design method is employed to define the best parameter values. Related results are analysed by statistical tools. The computational experiments are compared with an ACO algorithm and a genetic algorithm. The experimental results and statistical analyses show that the proposed EDD-SDST-ACO is effective for the problem.

Keywords

• single machine scheduling
• setup time
• heuristic algorithms
• ant colony optimisation (aco) algorithm