A genetic algorithm for the unrelated parallel machine scheduling problem with job splitting and sequence-dependent setup times-loom scheduling

Abstract

This paper addresses the unrelated parallel machine scheduling problem with sequence-dependent setup times and job splitting to minimize maximum completion time (makespan). We consider a real-life problem of scheduling looms in a textile industry. Each machine has its own processing times according to the characteristics of the machine as well as the job types. There are machine-and sequence-dependent setup times, and all of the jobs are available at time zero. All of the jobs can be divided into sub-jobs in order to deliver the orders on time. Job splitting has rarely been studied in the literature, especially in the case of parallel machines. Because of the problem's NP-hard structure, heuristics and metaheuristics have been used to solve real-life large-scale problems. Genetic algorithms (GA) are the most preferred approach of this type given their capabilities, such as high adaptability and easy realization. The proposed GA's chromosome representation is based on random keys. The schedule is constructed using a sequence of random key numbers. The main contribution of this paper is to introduce a novel approach that performs job splitting and scheduling simultaneously; to the best of our knowledge, no work has been published with this approach. An important improvement proposed in this paper is assigning the number of sub-jobs dynamically. In addition, the new approach is tested on a real-life problem, and the computational results validate the effectiveness of the proposed algorithm.