GPU-Based Hybrid Cellular Genetic Algorithm for Job-Shop Scheduling Problem

GPU-Based Hybrid Cellular Genetic Algorithm for Job-Shop Scheduling Problem

Abdelkader Amrane (Department of Computer Science, University Mustapha Stambouli of Mascara, Algeria), Fatima Debbat (Department of Computer Science, University Mustapha Stambouli of Mascara, Algeria) and Khadidja Yahyaoui (Department of Computer Science, University Mustapha Stambouli of Mascara, Algeria)
Copyright: © 2021 |Pages: 15
DOI: 10.4018/IJAMC.2021040101
OnDemand PDF Download:
No Current Special Offers


In task scheduling, the job-shop scheduling problem is notorious for being a combinatorial optimization problem; it is considered among the largest class of NP-hard problems. In this paper, a parallel implementation of hybrid cellular genetic algorithm is proposed in order to reach the best solutions at a minimum execution time. To avoid additional computation time and for real-time control, the fitness evaluation and genetic operations are entirely executed on a graphic processing unit in parallel; moreover, the chosen genetic representation, as well as the crossover, will always give a feasible solution. In this paper, a two-level scheme is proposed; the first and fastest uses several subpopulations in the same block, and the best solutions migrate between subpopulations. To achieve the optimal performance of the device and to reshape a more complex problem, a projection of the first on different blocks will make the second level. The proposed solution leads to speedups 18 times higher when compared to the best-performing algorithms.
Article Preview


In manufacturing, Scheduling refers to a management process whereby production capacity is optimally allocated to meet the demand. Unfortunately (Pinedo, 2016), finding the optimal solutions in these areas gives rise to complex combinatorial optimization problems (NP-hard) (Adams, Balas, & Zawack, 1988), and for the performance of manufacturing systems (MS) a satisfactory solution in an acceptable time span is crucial. Among the well-known combinatorial optimization problems that reflect a reality in machine scheduling is Job-shop scheduling problem (JSSP) (Jain & Meeran, 1999).

The objective is to minimize the make span in the shortest time with a decrease in computation consumption resources. Heuristic rules (Kannan & Ghosh, 1993) have been used to treat the JSSP, shifting bottleneck procedure (Adams, Balas, & Zawack, 1988) the branch & bound (Carlier & Pinson, 1989) are well-known classical resolution methods, which allow finding the optimal solutions. However, it is limited to small problem instances, which are often extremely time-consuming when solving problems with large dimensions, it is not at all practical to use it to solve problems with more than 14 jobs-machines. Lately the meta-heuristics are widely applied to solve this problem such as genetic algorithm (Gonçalves, Mendes, Resende, 2005; Wang & Zheng, 2001), particle swarm optimization(Rameshkumar & Rajendran, 2018; Lin, Horng, Kao, Chen, Run, Chen, & Kuo, 2010), neural networks(Foo, Takefuji, & Szu, 1995), ant colony optimization(Huang & Liao, 2008) and bee colony optimization(Chong, Low, Sivakumar, & Gay, 2006). The computational demand made these methods not easy to use for real-time control. A parallel genetic algorithm is proposed (Asadzadeh & Zamanifar, 2010) ; this approach is based on a coarse-grained model. The population is divided into sub-populations, all the sub-populations are evolved separately and a migration of chromosomes is applied between sub-populations. A genetic island model algorithm to solve the JSSP is proposed,(Kurdi, 2015) this approach has a new self-adaption in which the best individuals are selected for a local search using taboo search, and the worst individuals are used to perform a global search applying the random mutation operators. The work above (Asadzadeh & Zamanifar, 2010; Kurdi, 2015) does not ensure a high degree of parallelism, which brings us to a load unbalancing. In GPU implementation, most of the previous works on JSSP were centered on classical resolution methods. The well-known Branch & Bound algorithms(Dabah, Bendjoudi, El-Baz, & Aitzai, 2016) and shifting bottleneck procedure (Vilasagarapu & Reddy, 2015) implemented on GPU allow for finding the optimal solutions, but the shared memory limitation of GPU architecture does not allow important elements to be assigned to a single instance. Distributed taboo search (Bożejko, Uchroński, & Wodecki, 2012) is also designed to be executed using GPU, but the disadvantage of these architectures is that an external memory is the intermediary to ensure the synchronization and sharing between the different islands.

In this paper two types of improvement which are based on hybridization between a distributed model and cellular model (HCGA) are proposed for solving JSSP using a Graphic Processing Unit (GPU).The first HCGA consists of several sub-populations that locate in the same device and the same block, it is useful for solving low and medium complexity problems, while for problems that are more complex the island occupies the whole block, and migration between islands (blocks) is asynchronous. GA is implemented in various populations in a parallel manner; the communication between the groups is carried out by exchanging migrants, in which the best individuals are recruited. The remainder of this paper is structured as follows: in section 2, the main interpretations and formulations of the problem are described. Sections 3 to 4 illustrate the parallel approach with the various axes that surround it, such as migration, codification and GPU representation. The proposed approach (PGA-GPU) is described in section 5, Experimental results of the proposed algorithm applied to different classes of literature are compared with existing approaches in Section 6.Finally, section 7 presents the conclusions.

Complete Article List

Search this Journal:
Volume 13: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing