1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result;

GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem

2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s);

Jia Luo
LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France
jluo@laas.fr
+33(0)601424241

Shigeru Fujimura
Graduate School of Information, Production, and Systems, Waseda University, Kitakyushu, Japan
fujimura(at)waseda.jp
+81(0)936925017

Didier Elbaz
LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France
elbaz@laas.fr
+33(0)561336303

Bastien Plazolles
Géosciences Environnement Toulouse (CNRS UMR5563), Université de Toulouse, Toulouse, France
Bastien.PLAZOLLES@Get.omp.eu
+33(0)672507810

3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition);

Jia Luo jluo@laas.fr

4. the abstract of the paper(s);

Due to new government legislation, customers’ environmental concerns and continuously rising cost of energy, energy efficiency is becoming an essential parameter of industrial manufacturing processes in recent years. Most efforts considering energy issues in scheduling problems have focused on static scheduling. But in fact, scheduling problems are dynamic in the real world with uncertain new arrival jobs after the execution time. This paper proposes an energy efficient dynamic flexible flow shop scheduling model using the peak power value with consideration of new arrival jobs. As the problem is strongly NP-hard, a priority based hybrid parallel Genetic Algorithm (GA) with a predictive reactive complete rescheduling strategy is developed. In order to achieve a speedup to meet the short response in the dynamic environment, the proposed method is designed to be highly consistent with the NVIDIA CUDA software model. Finally, numerical experiments are conducted and show that our approach can not only solve the problem flexibly, but also gain competitive results and reduce time requirements dramatically.

5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies;

B G

6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission);

(B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.

As far as the solutions’ quality comparison concerned, we discover that the proposed hybrid parallel GA always gains a better performance with the average value, the best value and the variance of the objective function than the classical GA and the cellular GA. Since fine-grained models at the lower level could obtain good population diversity when dealing with high-dimensional variable spaces and island models at the upper level converge faster by subpopulations, the hybrid parallel GA combines the merits from both.

Regarding the execution time comparison, the hybrid parallel GA and the parallel cellular GA maximize the benefits from the GPU framework and almost take the same execution time. On the opposite, the classical GA on single core CPU takes from 14.73 to 25.08 times the execution time of the hybrid parallel GA. Even the effectiveness of the classical GA can be enhanced using the master–slave model with multi-core CPU and SIMD vectorization, the proposed GA still win with less execution time when the amount of individuals is increased.

(G) The result solves a problem of indisputable difficulty in its field.

The problem we have solved in this article is an energy efficient dynamic flexible flow shop scheduling (EDFFS).  There is a power’s peak limitation when the system operates. A set of new jobs may arrive after the start of the original plan. They should be processed sequentially and non-preemptively from the beginning of the rescheduling point with the remaining uncompleted operations of original jobs. As a flexible flow shop problem (FFS) is considered to be NP-hard in essence and difficult to solve, the EDFFS problem is a NP-hard combinatorial optimization problem and more complex than the FFS problem. Few studies have been conducted to integrate GPUs computing in this field as far our knowledge is concerned.

7. a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable);

Luo, J., Fujimura, S., El Baz, D., & Plazolles, B. (2018). GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem. Journal of Parallel and Distributed Computing.

8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors;

Any prize money is to be divided evenly among the co-authors after the traveling budget

9. a statement stating why the authors expect that their entry would be the "best”.

There has been a growing interest in energy efficient shop scheduling problems in a static perspective. However, due to frequently inevitable new arrival jobs in the production environment, a fixed preset scheduling plan could not meet the requirement. In this case, obtaining the renewed adequate scheduling plan in a reasonable response time is greatly desired but difficult to achieve. The proposed GA was developed for solving this NP-hard problem efficiently with a hybrid parallelization. According to the evolution theory and the underlying architecture of GPUs, several advantages can be gained and support our entry to be the “best”:

1）At the lower level of this hybrid design, a fine-grained GA is executed which helps obtain good population diversity by dealing with high-dimensional variable spaces. The limitation of interactions among individuals prevents the premature convergence. A reasonable neighborhood size with GA operators may disseminate the good solutions across the entire population.

2）Concerning the long-held principle in Population Genetics: favorable traits spread faster when the demes are small than when the demes are large, the island GA dominates at the upper level to increase the convergence speed by subpopulations. An appropriate island size with a proper migration interval is able to optimize this performance.

3) GPUs are built up with two-dimensional grid topology at the lower level that matches perfectly the structure of the fine-grained GA. Thousands of GPU threads are powerful to deal with large size individuals concurrently without increasing the time complexity. Meanwhile, the GA operations are carried using the fastest GPU local memory.

4) As GPU threads are grouped into blocks at the upper level, they are compatible with the mechanism of the island GA that divides the population into a few relatively large subpopulations. Isolated islands work on blocks in parallel with the help of GPU shared memory and exchange information by the migration.

10. an indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc.

GA (genetic algorithms)

11. the date of publication of each paper. If the date of publication is not on or before the deadline for submission, but instead, the paper has been unconditionally accepted for publication and is "in press" by the deadline for this competition, the entry must include a copy of the documentation establishing that the paper meets the "in press" requirement.

Published online: 16 August 2018