A new memetic global and local search algorithm for solving hybrid flow shop with multiprocessor task scheduling problem
- PDF / 1,054,440 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 94 Downloads / 187 Views
A new memetic global and local search algorithm for solving hybrid flow shop with multiprocessor task scheduling problem Batuhan Eren Engin1 · Orhan Engin2 Received: 28 January 2020 / Accepted: 16 November 2020 © Springer Nature Switzerland AG 2020
Abstract Hybrid flow shop (HFS) scheduling problem is combining of the flow shop and parallel machine scheduling problem. Hybrid flow shop with multiprocessor task (HFSMT) scheduling problem is a special structure of the hybrid flow shop scheduling problem. The HFSMT scheduling is a well-known NP-hard problem. In this study, a new memetic algorithm which combined the global and local search methods is proposed to solve the HFSMT scheduling problems. The developed new memetic global and local search (MGLS) algorithm consists of four operators. These are natural selection, crossover, mutation and local search methods. A preliminary test is performed to set the best values of these developed new MGLS algorithm operators for solving HFSMT scheduling problem. The best values of the MGLS algorithm operators are determined by a full factorial experimental design. The proposed new MGLS algorithm is applied the 240 HFSMT scheduling instances from the literature. The performance of the generated new MGLS algorithm is compared with the genetic algorithm (GA), parallel greedy algorithm (PGA) and efficient genetic algorithm (EGA) which are used in the previous studies to solve the same set of HFSMT scheduling benchmark instances from the literature. The results show that the proposed new MGLS algorithm provides better makespan than the other algorithms for HFSMT scheduling instances. The developed new MGLS algorithm could be applicable to practical production environment. Keywords Hybrid flow shop scheduling · Multiprocessor task · Memetic algorithm · Local search · Makespan
1 Introduction At the flow shop scheduling, each stage, only one machine is available and in the same order of machines, the job visits the stages of the shop [1]. But in the hybrid flow shop scheduling, at each stage, one or more identical parallel machines are available and in the same order of machines at each stage, job visits the stages of the shop and the job is processed only one machine in the parallel environment [1–4]. Gupta [5] and Hoogeveen et al. [6] showed that two-stage HFS scheduling problem is NP-hard in the strong sense even if there is only one machine on the first stage and two machines on the second stage. Arthanari and Ramamurty [7] proposed the first model of the HFS
scheduling from the literature, and they developed a branch and bound method to solve the HFS scheduling problems. The HFS scheduling can be found in the different production environments such as printed circuit board and integrated circuit packaging [8] and machine-vision systems [9]. The HFSMT is a special structure of the HFS scheduling problem. In the HFSMT scheduling, a job requires one or several processors simultaneously at each stage. HFSMT scheduling is proven to be NP-hard in the strong sense [10]. In this contex
Data Loading...
