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

Introduction

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.