Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times

Abstract

This paper focuses on an identical parallel machine scheduling problem with minimising total tardiness of jobs. There are two major issues involved in this scheduling problem; (1) jobs which can be split into multiple sub-jobs for being processed on parallel machines independently and (2) sequence-dependent setup times between the jobs with different part types. We present a novel mathematical model with meta-heuristic approaches to solve the problem. We propose two encoding schemes for meta-heuristic solutions and three decoding methods for obtaining a schedule from the meta-heuristic solutions. Six different simulated annealing algorithms and genetic algorithms, respectively, are developed with six combinations of two encoding schemes and three decoding methods. Computational experiments are performed to find the best combination from those encoding schemes and decoding methods. Our findings show that the suggested algorithm provides not only better solution quality, but also less computation time required than the commercial optimisation solvers.

Keywords:

• Identical parallel machine scheduling
• total tardiness
• job splitting
• sequence-dependent setup time
• solution encoding and decoding
• simulated annealing
• genetic algorithm

ORCID

BongJoo Jeong http://orcid.org/0000-0002-2891-5718

Additional information

Funding

This work was supported by Incheon National University (International Cooperative) Research Grant in 2017.