Jia Luo

Didier El Baz

Rui Xue

Jinglu Hu

Solving the Dynamic Energy Aware Job Shop Scheduling Problem with the Heterogeneous Parallel Genetic Algorithm

Keywords: Job shop scheduling, Energy efficiency, Dynamic scheduling, Parallel genetic algorithm, Multicore processing, GPU computing

Solving the dynamic energy aware job shop scheduling

problem with the heterogeneous parallel genetic algorithm

Introduction

Energy costs due to production have been traditionally treated as externalities that must be incurred [START_REF] Paolucci | Facing energy-aware scheduling: a multiobjective extension of a scheduling support system for improving energy efficiency in a moulding industry[END_REF]. With an increasing interest for industrial sustainability, integrating energy savings into production efficiency is considered as one essential factor in factory practice. There are two kinds of approaches studying energy saving in manufacturing systems [START_REF] Pach | Reactive and energy-aware scheduling of flexible manufacturing systems using potential fields[END_REF]: avoiding peak power consumption and reducing the overall energy cost. The first one [START_REF] Fang | A new shop scheduling approach in support of sustainable manufacturing[END_REF][START_REF] Bruzzone | Energy-aware scheduling for improving manufacturing process sustainability: A mathematical model for flexible flow shops[END_REF][START_REF] Xu | Energy-Efficient Scheduling for Flexible Flow Shops by Using MIP[END_REF] shifts load at energy peaks when the maximum available energy is met. The second one [START_REF] Liu | An investigation into minimising total energy consumption and total weighted tardiness in job shops[END_REF][START_REF] Yi | A new operational framework to job shop scheduling for reducing carbon emissions[END_REF][START_REF] Dai | Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm[END_REF] focuses on decreasing the total energy cost in manufacturing system by subdividing it and switching them among different types and different levels. Most of these research works focus solely on building a mathematical model within a static scenario. However, unexpected events may lead changes in the preset schedule after the start time. Few works focus on dynamic energy aware shop scheduling problems and most of them [START_REF] Tang | Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization[END_REF][START_REF] Zhang | Dynamic rescheduling in FMS that is simultaneously considering energy consumption and schedule efficiency[END_REF][START_REF] Luo | GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem[END_REF] were solved by the complete rescheduling with a risk in instability. Moreover, scheduling problems in dynamic scenarios are more complicated than scheduling problems in static scenarios and the time cost to obtain the optimal solution or even a high-quality solution is heavy. Therefore, an approach proposing an appropriate updated schedule within a reasonable time is highly desirable in this case.

Parallel computing has been widely used for years. The multi-core CPU can run multiple instructions at the same time on separate cores to increase the overall speed while Graphics Processing Units (GPUs) are many-core processor devices providing a highly multi-threaded environment using the Single Instruction, Multiple Threads (SIMT) model. Since most of latest computers are furnished with a multi-core CPU and GPUs, the execution on both is an effective strategy to utilize hardware in an efficient way. Investigation on solving scheduling problems in manufacturing processes by parallel computing methods [START_REF] Dabah | Hybrid multicore CPU and GPU-based B&B approaches for the blocking job shop scheduling problem[END_REF] has received increasing attention in the last decades. However, the sophisticated issue as energy aware shop scheduling in dynamic scenarios was never considered as best as we are aware. On the other side, there is a great number of successful cases [START_REF] Spanos | A new hybrid parallel genetic algorithm for the job-shop scheduling problem[END_REF][START_REF] Zajıcek | Accelerating a Flow Shop Scheduling Algorithm on the GPU[END_REF][START_REF] Somani | Parallel Genetic Algorithm for solving Job-Shop Scheduling Problem Using Topological sort[END_REF] proving that parallel GAs are reliable for solving shop scheduling problems. But most of them either only use the CPU, the GPUs or two of them in sequence which may end up to an underuse of computing resources due to the hardness of designing schemes that efficiently exploit simultaneously different hardware architectures. Thus, the design of parallel GAs on hybrid CPU-GPU frameworks for solving dynamic energy aware shop scheduling problems is a known research challenge following previous works, and this is what we are trying to solve in this paper.

An investigation into minimizing the total tardiness and the total energy cost in the job shop with new urgent arrival jobs is concerned in this paper. To avoid the shortages of the complete rescheduling, the schedule repair with the event driven strategy is utilized to represent the updated solution. Since the response time is sensitive in the dynamic scenario, a dual heterogeneous island parallel GA executed simultaneously on GPUs and a multi-core CPU is utilized. Numerical tests confirm the proposed method can be implemented to solve the problem efficiently and effectively. Our main work can be summed up as follows:

1. A dynamic energy aware job shop scheduling model is studied which seeks a trade-off among the total tardiness, the energy cost and the disruption to the original schedule;

2. A parallel GA is adapted for solving the proposed problem, whose lower level is appropriate for concurrent execution within GPUs or a multi-core CPU while codes from the two sides can be executed simultaneously at the upper level;

3. Numerical experiments have been carried out and witness that the adapted parallel GA can not only solve the proposed problem efficiently but also improve the average results with a significant execution time decrease.

The remaining of our work consists of 5 sections. In section 2, the literature review is presented. Section 3 exposes the research problem and formulates the mathematical model. Section 4 discusses the design of the parallel GA on hybrid CPU-GPU frameworks and its implementation for solving dynamic energy aware shop scheduling problems. Afterwards, computational tests and a case study are conducted in section 5. Finally, conclusions are stated in section 6.

Literature review

Due to environmental concerns and continuously rising cost, there is an increasing interest in energy saving in traditional industrial processes. Since moving the production activities in off-peak periods or inserting idle times for machine may not be acceptable with intense production process or fixed working time shifts [START_REF] Paolucci | Facing energy-aware scheduling: a multiobjective extension of a scheduling support system for improving energy efficiency in a moulding industry[END_REF], minimizing the overall energy cost is considered one main solution. Meng et al. discussed the total energy consumption for flexible job shop scheduling problems in [START_REF] Meng | MILP models for energy-aware flexible job shop scheduling problem[END_REF] and solved it by six new mixed integer linear programming models. He et al. [START_REF] He | A bi-objective model for job-shop scheduling problem to minimize both energy consumption and makespan[END_REF] proposed a model synthesizing the optimization of energy consumption and makespan while the optimal solutions were obtained by the Tabu search. Meanwhile, the GA or the improved GA is one powerful and frequently used method to deal with the total energy cost integrated scheduling problems. Liu et al. [START_REF] Liu | An investigation into minimising total energy consumption and total weighted tardiness in job shops[END_REF] developed a non-dominant sorting GA and obtained the Pareto front for a bi-objective job shop scheduling problem that investigated into minimizing total electricity cost and total tardiness. Similarly, a modified multi-objective GA was studied in [START_REF] Yi | A new operational framework to job shop scheduling for reducing carbon emissions[END_REF] and it was utilized to solve a multi-machine job shop scheduling model with emission aware issues. In one word, numerous efforts have been given to combine the traditional shop scheduling efficiency with the overall energy cost. However, the models used in these researches are deterministic in which the number of jobs is a fixed value [START_REF] Liu | An investigation into minimising total energy consumption and total weighted tardiness in job shops[END_REF]. As an ongoing reactive process where the presence of a variety of unexpected disruptions is usually inevitable [START_REF] Ouelhadj | A survey of dynamic scheduling in manufacturing systems[END_REF], the static scheduling obviously cannot meet the requirements in most real-world environments.

Literature on dynamic scheduling has considered a significant number of works dealing with new arrival jobs and their effects in various manufacturing systems [START_REF] Ouelhadj | A survey of dynamic scheduling in manufacturing systems[END_REF]. Most efforts concentrated only on the efficiency improvement for traditional scheduling problems while neglecting the energy cost. In the dynamic scenario, complete rescheduling and schedule repair are the two most common used strategies. An improved particle swarm optimization was adopted in [START_REF] Tang | Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization[END_REF] to allocate the new jobs and the previous remaining operations simultaneously for an energy saving dynamic scheduling problem. Zhang et al. studied the dynamic rescheduling considering energy consumption in [START_REF] Zhang | Dynamic rescheduling in FMS that is simultaneously considering energy consumption and schedule efficiency[END_REF] where optimal solutions were found by a GA with the complete rescheduling strategy. Even the complete rescheduling provides the optimal solutions, it can result in instability and disruption in manufacturing flows, leading to tremendous production costs [START_REF] Le | Fast reactive scheduling to minimize tardiness penalty and energy cost under power consumption uncertainties[END_REF]. On the opposite, schedule repair only attempts to revise part of the originally created schedule for responding to the production environment changes. In [START_REF] Pach | Reactive and energy-aware scheduling of flexible manufacturing systems using potential fields[END_REF], Pach et al. set up flexible manufacturing systems using potential fields where resources could switch to less energy consumption mode by sensing the intentions from products. Zeng et al. [START_REF] Zeng | Dynamic scheduling of multi-task for hybrid flow-shop based on energy consumption[END_REF] presented a particle swarm optimization to solve the energy consumption based dynamic scheduling problem by introducing idle time windows. To sum up, some efforts concerning energy efficient scheduling problems in dynamic scenarios have been conducted. It shows that the schedule repair strategy is more practical to deal with the dynamic manufacturing system in the real world. But many limitations are still remaining that must be taken into account. One for instance is to get the appropriate updated schedule within a reasonable time, especially for large size manufacturing applications.

With the huge evolution of multi-core CPUs and GPUs, some works have considered the cooperation between them to maximally utilize their compute capability. A parallelization mixing the multi-core CPU and the GPUs was studied by Dabah et al in [START_REF] Dabah | Hybrid multicore CPU and GPU-based B&B approaches for the blocking job shop scheduling problem[END_REF] where a group of blocking job shop scheduling problems were solved efficiently. In [START_REF] Hawick | Mixing multi-core CPUs and GPUs for scientific simulation software[END_REF], Hawick et al. described the use of threading approaches and multi-core CPUs to control independent GPU devices to speed up scientific simulations. Hossam et al. [START_REF] Hossam | Hybrid cluster of multicore CPUs and GPUs for accelerating hyperspectral image hierarchical segmentation[END_REF] introduced a parallel implementation of hybrid CPU/GPU in which CPU and GPU work cooperatively and seamlessly, combining benefits of both platforms. All these works have verified that a scheme exploiting a multi-core CPU and GPUs corporately can increase the hardware occupation and achieve a speedup. However, this strategy is rarely implemented for GAs, in particular for the implementation of parallel GAs to solve dynamic energy aware shop scheduling problems, as far our knowledge is concerned.

Considering the above-mentioned requirements, we seek to study parallel GAs for solving the dynamic energy aware job shop scheduling problem on hybrid CPU-GPU frameworks. All the previous studies have afforded us with a starting point to design a GA that is well suited for parallelization on different architectures. Moreover, this implementation is efficient to provide appropriate solutions for large dynamic energy aware job shop scheduling problems within a short response time.

Problem statement

EDJSP description

The Job Shop scheduling Problem (JSP) is a NP-hard problem [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF] in which there are several jobs and each job consists of a certain amount of operations. One operation is processed by a particular machine and every job is assigned to a group of machines following a predetermined route [START_REF] Liu | An investigation into minimising total energy consumption and total weighted tardiness in job shops[END_REF]. As a layout shown in Figure 1, job A and job B need to be processed by 4 machines and their processing routines are fixed as Machine 0-2-1-3 and Machine 2-0-3-1, respectively. The Energy aware Dynamic Job Shop scheduling Problem (EDJSP) is an extension of the JSP with machine speed scaling [START_REF] Fang | Flow shop scheduling with peak power consumption constraints[END_REF] in which machines are available to be set at different speed levels when dealing with different jobs. The processing time and the energy cost of one operation processed on one machine at a set speed level are known. When a higher speed level is chosen, the processing time is shortened but with an energy cost increase. When machines start to handle original jobs following the preset schedule, a batch of new jobs may arrive and these jobs are requested to be processed as soon as possible. Therefore, the production line conducts them immediately with the highest speed level. The operations being processed are terminated and need to be rescheduled with other unfinished operations of original jobs based on the insertion of new urgent arrival jobs. The updated schedule using the schedule repair refers to some local adjustment of the original one.

There are two possible schedule repair measures for the impact caused by the schedule changes [START_REF] Wu | One-machine rescheduling heuristics with efficiency and stability as criteria[END_REF]: (1) the deviation from the original jobs starting times, (2) the deviation from the original sequence. In this paper, a measure modified from ( 1) is taken into consideration where each original job has an importance weight and a larger importance weight indicates a higher penalty for delaying the finishing time of original jobs from the original schedule. If one operation of a new urgent arrival job is added before one operation of an original job on the same machine, a higher speed level with less processing time but more energy cost is required to make the original job to be completed as close as to its finishing time in the original schedule. Clearly, there are conflicts among the minimization of total tardiness, the minimization of total energy cost and the minimization of disruption to the original schedule. Thus, a trade-off must be made among them. Because of the NP hardness of the JSP, the EDJSP is a NP-hard problem and more complicated than the JSP.

Mathematical model of EDJSP

A description of the notations referred within the remaining sections of this paper is summarized in Table 1.

𝑃 𝑐𝑒𝑐

The crossover rate of the cellular GA

𝑃 𝑐𝑒𝑚

The mutation rate of the cellular GA

𝑃 𝑐𝑎𝑐

The crossover rate of the classic GA

𝑃 𝑐𝑎𝑚

The mutation rate of the classic GA To minimize the total tardiness, the total energy cost and the delay caused by the schedule changes, the formal mathematical model of the EDJPS is derived from the mathematical models presented in [START_REF] Wu | One-machine rescheduling heuristics with efficiency and stability as criteria[END_REF][START_REF] Luna | Parallel Multiobjective Evolutionary Algorithms[END_REF]. The formalization is given as follows.

Objective Function: 𝑃 𝑗(𝑜 𝑗 -1)𝑀 𝑗(𝑜 𝑗 -1) 𝑞 × 𝑍 𝑗(𝑜 𝑗 -1)𝑀 𝑗(𝑜 𝑗 -1) 𝑞 ), 0)

Min: 𝛼 × 𝑇𝑇-𝐸𝑇 𝑚𝑖𝑛 𝐸𝑇 𝑚𝑎𝑥 -𝐸𝑇 𝑚𝑖𝑛 + 𝛽 × 𝑇𝐸-𝐸𝐸 𝑚𝑖𝑛 𝐸𝐸 𝑚𝑎𝑥 -𝐸𝐸 𝑚𝑖𝑛 + 𝛾 × 𝐷𝐸𝑉-𝐸𝐷 𝑚𝑖𝑛 𝐸𝐷 𝑚𝑎𝑥 -𝐸𝐷 𝑚𝑖𝑛 (1) Subject to: 𝑆 𝑗0𝑀 𝑗0 ′ ≥ 𝑅 𝑗 𝑗 ∈ 𝐽 ∪ 𝐽 ′ (2)
𝑆 𝑗(𝑠+1)𝑀 𝑗(𝑠+1) ′ ≥ 𝑆 𝑗𝑠𝑀 𝑗𝑠 ′ + ∑ 𝑝 𝜖 𝐿 𝑃 𝑗𝑠𝑀 𝑗𝑠 𝑝 × 𝑍 𝑗𝑠𝑀 𝑗𝑠 𝑝 𝑗 ∈ 𝐽 ∪ 𝐽 ′ , 𝑠 ∈ 𝑂 𝑗 , 𝑠 > 0, 𝑝 𝜖 𝐿 (3)
𝑆 𝑖𝑡𝑀 𝑖𝑡 ′ ≥ 𝑆 𝑗𝑠𝑀 𝑗𝑠 ′ + ∑ 𝑝 𝜖 𝐿 𝑃 𝑗𝑠𝑀 𝑗𝑠 𝑝 × 𝑍 𝑗𝑠𝑀 𝑗𝑠 𝑝 𝑗 ∈ 𝐽 ∪ 𝐽 ′ , 𝑖 ∈ 𝐽 ∪ 𝐽 ′ , 𝑗 ≠ 𝑖, 𝑠 ∈ 𝑂 𝑗 , 𝑡 ∈ 𝑂 𝑖 , 𝑀 𝑗𝑠 == 𝑀 𝑖𝑡 , 𝑝 𝜖 𝐿, 𝑆 𝑗𝑠𝑚 ≤ 𝑆 𝑖𝑡𝑚 (4)
𝑇𝑇 = ∑ 𝑗∈𝐽 𝑚𝑎𝑥 (𝑆 𝑗(𝑜 𝑗 -1)𝑀 𝑗(𝑜 𝑗 -1) ′ + ∑ 𝑝 𝜖 𝐿 𝑃 𝑗(𝑜 𝑗 -1)𝑀 𝑗(𝑜 𝑗 -1) 𝑝 × 𝑍 𝑗(𝑜 𝑗 -1)𝑀 𝑗(𝑜 𝑗 -1) 𝑝 -𝐷 𝑗 , 0) (5)
In this optimization problem, 𝑆 𝑗𝑠𝑚 ′ and 𝑍 𝑗𝑠𝑚𝑝 are the decision variables. A weighted additive utility function with three normalized objectives is described as [START_REF] Paolucci | Facing energy-aware scheduling: a multiobjective extension of a scheduling support system for improving energy efficiency in a moulding industry[END_REF] where all objectives can be assessed on the same scale. The linear weighted sum approach is taken for this application instead of the Pareto optimal solution for two reasons. Firstly, the most widely used parallel cellular model on GPUs is still immature for solving multi-objective problems where the main stream implementation manages a central Pareto front sequentially [START_REF] Luna | Parallel Multiobjective Evolutionary Algorithms[END_REF][START_REF] Talbi | A unified view of parallel multi-objective evolutionary algorithms[END_REF]. Second, most of the existing literature on the multi-objective job shop scheduling problems adopt the linear weighted sum approach [START_REF] Shen | Multi-objective dynamic job shop scheduling: a survey and prospects[END_REF] whose computational complexity is relatively lower. Meanwhile, this design is suitable for dealing with large size problems in the dynamic scenario by obtaining an adequate renewed scheduling plan in a reasonable time.

Constraints ( 2) and ( 3) enforce that the first operation can only be processed after the release time while the others are authorized to start after its precedent one. The precedence for sequencing operations on machines is insured by constraint (4). Moreover, equation ( 5) defines the total tardiness of original jobs. As far as the energy cost, constraint [START_REF] Liu | An investigation into minimising total energy consumption and total weighted tardiness in job shops[END_REF] states each operation can only be handled by one machine with a fixed speed level whereas the total energy cost is given by equation [START_REF] Yi | A new operational framework to job shop scheduling for reducing carbon emissions[END_REF]. Finally, constraint (8), ( 9) and ( 10) impose the definition of rescheduling and equation [START_REF] Luo | GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem[END_REF] indicates the weighted finishing time deviation of the updated schedule from the original one.

Solving approach

Event-driven strategy

With the event-driven policy, rescheduling is triggered in response to an unexpected event that alters the current system status [START_REF] Ouelhadj | A survey of dynamic scheduling in manufacturing systems[END_REF]. In the case of EDJSP, the unexpected event is considered as an arrival of urgent jobs. These jobs are requested to be processed as soon as possible even if the original schedule has started. Operations that are being executed need to be terminated and unfinished operations of original jobs must be rearranged in order to leave the machines available to firstly handle urgent jobs. Thus, new urgent arrival jobs are assigned to machines with the highest speed levels at the beginning when the rescheduling is triggered. If the amount of new urgent arrival jobs is not unique, they are scheduled as the regular JSP with the objective of minimizing the total tardiness. Unfinished operations of original jobs are considered at the next step according to the remaining spaces on machines. A dual heterogeneous island parallel GA on hybrid CPU-GPU frameworks is adapted to generate an adequate schedule for them in a limited time. The flow of the event-driven strategy is summarized as in Figure 2. The general procedure of the dual heterogeneous island parallel GA on hybrid CPU-GPU frameworks is a further development from our previously designed parallel GA and its implementations to solve large scale flexible flow shop scheduling in static scenarios [START_REF] Luo | A Dual Heterogeneous Island Genetic Algorithm for Solving Large Size Flexible Flow Shop Scheduling Problems on Hybrid multi-core CPU and GPU Platforms[END_REF]. The algorithm divides the population into two islands. There is an identical amount of individuals on every island in which island A deals with the cellular GA [START_REF] Alba | Cellular genetic algorithms[END_REF] and island B deals with the classic GA [START_REF] Holland | Genetic algorithms[END_REF]. At a certain point, a migration operation is executed to swap individuals between them. The procedure of the dual heterogeneous island parallel GA on hybrid CPU-GPU frameworks is shown in Fig. 3. As far as the software and the hardware levels are concerned, four obvious advantages of this design are summarized as follows:

• Since the cellular GA and the classical GA get new search points in the exploring space using different mechanisms, this design enlarges the range of the searching process and decreases the probability that premature convergence occurs.

• Because of the independent evolution, individuals from heterogeneous islands obtain distinct characters from different solution range. Therefore, the performance of migration is enhanced.

• With respect to the underlying architectures, the cellular GA is designed to be entirely executed in parallel on GPUs while the classic GA can be partially parallelized on a multicore CPU.

• To utilize the computing resources maximally, codes from the host and the device can also be executed simultaneously, in addition to the parallelization within GPUs or a multi-core CPU.

Fig. 3. The procedure of the dual heterogeneous island parallel GA

The implementation for the cellular GA on island A is done with the Compute Unified Device Architecture (CUDA) for GPUs. All CUDA threads in a grid execute the same kernel function where a grid is organized as 2D array of blocks and each block is arranged as 2D array of threads [START_REF] Plazolles | SIMD Monte-Carlo Numerical Simulations Accelerated on GPU and Xeon International[END_REF]. The cellular GA maps individuals in a grid environment [START_REF] Danoy | Hybrid Cellular Genetic Algorithm for Global Trajectory Optimization Problem[END_REF]. Therefore, it can be completely parallelized on CUDA and absolutely matches the underlying architectures. Since the texture memory of CUDA is optimized for 2D spatial locality [START_REF] Sanders | CUDA by example: an introduction to general-purpose GPU programming[END_REF], the overlapping communication region of the cellular GA is designed to be circled as in Fig. 4. At first, two parent individuals are selected from this region and their chromosomes are reassembled to produce a new offspring individual.

After the mutation operation, this newly constituted individual substitutes the initial one only if its fitness value is better. Upon the fitness values, all individuals are finally ordered by the Bitonic-Merge sort [START_REF] Pharr | Gpu gems 2: programming techniques for highperformance graphics and general-purpose computation[END_REF], if the algorithm complies with the island termination condition but not with the final termination condition. The crossover, the replacement and the Bitonic-Merge sort are managed via the global memory whereas the mutation and the fitness evaluation are performed thought the local memory. When a migration point is reached, individuals executed on GPUs are transferred to the CPU and the migration between the two islands is carried out by the CPU. To reduce the amount of factors required to be controlled manually, the migration's execution is decided by a migration threshold value 𝜃. Moreover, the migration rate 𝜆 is formulated as

𝜆 = {1 -𝑚𝑖𝑛{ 𝑓𝑖𝑡 𝐴 𝑓𝑖𝑡 𝐵 , 𝑓𝑖𝑡 𝐵 𝑓𝑖𝑡 𝐴 } 0 1 -𝑚𝑖𝑛{ 𝑓𝑖𝑡 𝐴 𝑓𝑖𝑡 𝐵 , 𝑓𝑖𝑡 𝐵 𝑓𝑖𝑡 𝐴 } < 𝜃 1 -𝑚𝑖𝑛{ 𝑓𝑖𝑡 𝐴 𝑓𝑖𝑡 𝐵 , 𝑓𝑖𝑡 𝐵 𝑓𝑖𝑡 𝐴 } ≥ 𝜃 (12)
The migration is only executed when 1 -𝑚𝑖𝑛{ 𝑓𝑖𝑡 𝐴 𝑓𝑖𝑡 𝐵 , 𝑓𝑖𝑡 𝐵 𝑓𝑖𝑡 𝐴 } < 𝜃 where the 𝜆 percent individuals with the best fitness values are exchanged between the two islands to replace the 𝜆 percent individuals with the worst fitness values in the others. This mechanism helps to diffuse the best individuals efficiently while saving the execution time by avoiding useless information sharing.

Hybrid encoding representation

To solve the EDJSP, a modified operation-based encoding is adopted for representing the chromosomes. In terms of the schedule of original jobs, the chromosome contains two permutations: operation permutation X(k) [START_REF] Spanos | A new hybrid parallel genetic algorithm for the job-shop scheduling problem[END_REF] and speed level permutation Y(k) [START_REF] Zajıcek | Accelerating a Flow Shop Scheduling Algorithm on the GPU[END_REF]. X(k) utilizes the operation-based encoding where each job is represented by a natural number and each number is present as many times as the number of operations of the job it represents [START_REF] May | Multi-objective genetic algorithm for energy-efficient job shop scheduling[END_REF]. By scanning X(k) from left to right, the 𝑣 𝑗 th occurrence of a job j refers to the 𝑣 𝑗 th operation in the technological sequence of this job [START_REF] Park | A hybrid genetic algorithm for the job shop scheduling problems[END_REF]. According to the example provided in [START_REF] Liu | Intelligent optimization scheduling algorithms for manufacturing process and their applications[END_REF], a feasible solution for a 3× 3 job shop is presented as [2, 1, 0, 0, 1, 2, 2, 1, 0] where 2 on the fifth gene position (indexed from 0) indicates the operation 1 (after the operation 0) of job 2 as it is the 1 st occurrence (after the 0 th occurrence) of number 2. Thus, X(k) can be translated to a list of ordered operations as [𝑜 20 , 𝑜 10 , 𝑜 00 , 𝑜 01 , 𝑜 11 , 𝑜 21 , 𝑜 22 , 𝑜 12 , 𝑜 02 ]. Moreover, each element 𝑦 𝑎 (𝑘) shows the selected speed level of its related element 𝑥 𝑎 (𝑘) on the target machine. To leave machines available to conduct new urgent arrival jobs firstly with the highest speed level and rearrange unfinished operations of original jobs, the chromosome of the updated schedule also includes an operation permutation 𝑋′(𝑘) [START_REF] Somani | Parallel Genetic Algorithm for solving Job-Shop Scheduling Problem Using Topological sort[END_REF] and a speed level permutation 𝑌′(𝑘) [START_REF] Meng | MILP models for energy-aware flexible job shop scheduling problem[END_REF]. The initialization rule for both are shown in Algorithm 1. Moreover, the decoding rule is displayed in Algorithm 2.

𝑋 ′ (𝑘) = [ 𝑥 0 ′ (𝑘), 𝑥 1 ′ (𝑘), ⋯ , 𝑥 𝑎 ′ (𝑘), ⋯ , 𝑥 ∑ 𝑗∈𝐽∪𝐽 ′ 𝑜 𝑗 -1 ′ (𝑘) ] ( 15
)
where 𝑥 𝑎 ′ (𝑘)𝜖[0, 𝑛 + 𝑛′ -1], 𝑢 𝑗 == 𝑜 𝑗 .

𝑌 ′ (𝑘) = [ 𝑦 0 ′ (𝑘), 𝑦 1 ′ (𝑘), ⋯ , 𝑦 𝑎 ′ (𝑘), ⋯ , 𝑦 ∑ 𝑗∈𝐽∪𝐽 ′ 𝑜 𝑗 -1 ′ (𝑘) ] (16)
where

𝑦 𝑎 ′ (𝑘)𝜖[0, ℎ -1].

Crossover and mutation operators

To work with the modified operation-based encoding, the operation-based order crossover [START_REF] Liu | An investigation into minimising total energy consumption and total weighted tardiness in job shops[END_REF] is utilized as the crossover operator and works for genes in the chromosome within the range [𝑟2 , ∑ 𝑗∈𝐽∪𝐽 ′ 𝑜 𝑗 -1]. Firstly, it randomly chooses the same operations from two paired parents. The loci of chosen operations are preserved and copied to their own offspring. Afterwards, remaining operations are transmitted to the offspring of the other parent to fill the missing genes while their original orders are also kept. The crossover procedure for a 5×3 job shop example is shown in Fig. 5 where job 0, job 1, job 2, job 3 are original jobs, job 4 is a new urgent arrival job and each machine has 3 speed levels. The integers in red indicates genes out of the range [𝑟2 , ∑ 𝑗∈𝐽∪𝐽 ′ 𝑜 𝑗 -1] while the integers in blue mark the loci of randomly chosen operations.

Numerical Tests

Test 1 checks the efficiency and the effectiveness of the dual heterogeneous island parallel GA on hybrid CPU-GPU frameworks for solving the energy aware JSP while test 2 evaluates the performance of EDJSP by a case study. All the experiments have been made using the Intel Xeon E5640 CPU which has four CPU-cores, 2.67 GHz clock speed each and NVIDIA Tesla K40 with CUDA cores and 12 GB GDDR5 of global memory.

Evaluation

The energy aware JSP without taking into account new urgent arrival jobs is the first to be concerned. In this case, six large size problems are generated as in [START_REF] Storer | New search spaces for sequencing problems with application to job shop scheduling[END_REF]. These instances are referred to as "easy problems" or "hard problems" with names EASY 20× 10, EASY 20× 20, EASY 50× 10, HARD 20× 10, HARD 20× 20 and HARD 50× 10. EASY 20× 10 and HARD 20× 10 are 20-job, 10-machine problems; EASY 20× 20 and HARD 20× 20 are 20-job, 20-machine problems; EASY 50× 10 and HARD 50× 10 are 50-job, 10-machine problems. Every job consists of the same amount of operations as the amount of machines, while one operation is always handled by a single machine. Moreover, every machine has 5 speed levels. As far as the easy problems are concerned, the machine procedure constraints for each job are generated randomly. As an alternative, the hard problems divide the machines into two sets. Each job must pass firstly through the first set, then through the second one. The ordering within the two sets of machines is generated randomly. The data relative to the experience is defined in Table 2. To verify the performance of the proposed algorithm, we compare its solution quality and execution time with the parallel cellular GA on GPUs and the parallel classic GA on a multi-core CPU. For these tested three GAs, the population sizes are all kept as 512 (16×16×2) while each island's subpopulation size of the dual heterogeneous island parallel GA on hybrid CPU-GPU frameworks is 256 (16×16). The final termination criterion is set as 2000 generations. Moreover, the results shown in Fig. 7, Fig. 8, Fig. 9, Fig. 10, Fig. 11, Fig. 12, Table 5 and Table 6 are obtained by 30 independent runs while the results displayed in Table 7 are the average values of 5 runs. Since the parameter configuration has a huge impact to the performance of algorithms, the Taguchi method [START_REF] Taguchi | Introduction to Quality Engineering[END_REF] is used to calibrate the parameters of the tested GAs. As most common optimality criteria of shop scheduling problems are about minimization, the signal to noise ratio (S/N) of the Taguchi method used to assess the performance in our case is calculated as:

S/N ratio = -10 × (𝑠𝑢𝑚(𝐹 2 )/𝑁) (17)
Table 3. The parameters and their levels. As the migration of the proposed GA is carried out by the CPU in which individuals executed on GPUs are transferred to the CPU at this point, its performance may be weakened because of the frequent data exchange. Therefore, we need also test the migration policy execution gap for the dual heterogeneous island parallel GA on hybrid CPU-GPU frameworks, in addition to the crossover rate, the mutation rate and the migration threshold value. The parameters and their levels are given in Table 3. The Minitab software [43] is used to obtain the S/N ratios and the standard deviations in the Taguchi method for each GA. The 𝐿 27 design is selected for the dual heterogeneous island parallel GA while the 𝐿 9 is selected for the parallel classic GA and the parallel cellular GA. The orthogonal array of each design is presented in Table 4 and Table 5 respectively. Regarding the S/N ratios of three GAs displayed in Fig. 7, Fig. 9 and Fig. 11 and the standard deviations presented in Fig. 8, Fig. 10 and Fig. 12 separately, we select their parameters levels as shaded in Table 3. Since the decentralized population in the parallel cellular GA allows to keep the population's diversity for longer [START_REF] Dorronsoro | Cellular genetic algorithms without additional parameters[END_REF], it works as strongly as the parallel classic GA and even defeats the parallel classic GA for half of the cases as shown in Table 6. Because of the separated evolution and the enhanced migration, the dual heterogeneous island parallel GA integrates the advantages from the parallel cellular GA and the parallel classic GA. Therefore, it can always get the best performance for all tested problems with the average value. To confirm this efficiency, the Wilcoxon signed ranks test [START_REF] Derrac | A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[END_REF] is utilized to compare the performance of the dual heterogeneous island parallel GA with the other two considered parallel GAs. Table 7

GAs

Case study

A modified job shop instance incorporating machine speed scaling and new urgent arrival jobs is developed based on the well know 10×10 problem (10 jobs, 10 machines) from Muth and Thompson [START_REF] Muth | Probabilistic learning combinations of local job-shop scheduling rules[END_REF] (MT10) as a case study. There are 10 original jobs and 3 new urgent arrival jobs. Each machine has 5 speed levels. New urgent jobs arrive around 30% of the makespan of the original schedule. The operation sequence of original jobs and their processing times on target machine at speed level 0 are collected from MT10. On the other hand, the values for new urgent arrival jobs are generated following the rule of "hard problems" in subsection 5.1 evaluation. The values of energy cost at level 0 is set as

𝑄 𝑗𝑠𝑀 𝑗𝑠 0 = 𝛿 × 𝑃 𝑗𝑠𝑀 𝑗𝑠 0 2
, where 𝛿=U [START_REF] Pach | Reactive and energy-aware scheduling of flexible manufacturing systems using potential fields[END_REF][START_REF] Bruzzone | Energy-aware scheduling for improving manufacturing process sustainability: A mathematical model for flexible flow shops[END_REF]. The release times (𝑅 𝑗 ) of original jobs are fixed as 0 while the due times are generated as 𝐷 𝑗 = 𝑃 𝑗 × (1 + 𝜎), where 𝜎=U[0, 2] and 𝑃 𝑗 = ∑ 𝑠 (∑ 𝑝 𝑃 𝑗𝑠𝑀 𝑗𝑠 𝑝 /ℎ). Concerning the importance weight of original jobs, we make 𝑤𝑡 0 = 𝑤𝑡 1 = 4, 𝑤𝑡 𝑗 = 2 for j = 2, 3, …, 7 and 𝑤𝑡 8 = 𝑤𝑡 9 = 1. All details are shown in Table 9. Moreover, the processing time and the energy cost when operation s of job j handled by target machine m at different levels is defined as 𝑃 𝑗𝑠𝑚𝑝 =𝑃 𝑗𝑠𝑚0 × 𝑉 𝑝 and 𝑄 𝑗𝑠𝑚𝑝 =𝑄 𝑗𝑠𝑚0 ÷ 𝑉 𝑝 , respectively, where 𝑉 = (1, 1.3, 1.55, 1.75, 2.1). Finally, we keep the values of 𝛼, 𝛽 equal to 1 while a very large constant is assigned to 𝛾 which indicates the importance of the schedule repair strategy.

The best-found solution of the original schedule is shown by the Gantt chart in Fig. 13. Since new urgent jobs arrive at time 600, all operations are being operated at this moment need to be canceled and leave machines available for processing them firstly. In this case, some machines are occupied at some periods after scheduling new urgent arrival jobs. Therefore, unfinished operations of original jobs are rearranged to make use of machines only when they are idle. By implementing the schedule repair strategy, the best-found solution illustrated by the Gantt chart of the updated schedule in Fig. 14 presents that the processing time of some operations is obviously decreased. As a result, most original jobs' finishing time are only delayed slightly which is confirmed by the details displayed in Table 10.

In addition to the M10, we have extended another four classic cases from the literature to test the relationship among the three objectives of the EDJSP. The problems ABZ5 and ABZ7 are two problems from [START_REF] Adams | The shifting bottleneck procedure for job shop scheduling[END_REF]. The problems LA35 and LA40 are two problems from [START_REF] Lawrence | Resouce constrained project scheduling: An experimental investigation of heuristic scheduling techniques[END_REF]. The operation sequence of these jobs and their processing times on target machines are treated as original jobs at speed level 0 in the EDJSP. The importance weights of original jobs are randomly drawn integers from the interval [START_REF] Paolucci | Facing energy-aware scheduling: a multiobjective extension of a scheduling support system for improving energy efficiency in a moulding industry[END_REF][START_REF] Bruzzone | Energy-aware scheduling for improving manufacturing process sustainability: A mathematical model for flexible flow shops[END_REF]. The amount of new urgent arrival jobs is an integer generated randomly from U [START_REF] Paolucci | Facing energy-aware scheduling: a multiobjective extension of a scheduling support system for improving energy efficiency in a moulding industry[END_REF][START_REF] Zhang | Dynamic rescheduling in FMS that is simultaneously considering energy consumption and schedule efficiency[END_REF] while their arriving time is set by a random value from a uniform distribution on the interval [0, the makespan of the original schedule]. Moreover, the other settings are kept the same as the MT10 based EDJSP. Because of the relationship among the total tardiness, the total energy cost and the disruption to the original schedule, the decision maker can achieve their preference through controlling the importance weight of each normalized objective function. The dual heterogeneous island parallel GA was run 30 times for the above mentioned five EDJSP cases with different settings of 𝛼, 𝛽, 𝛾 and the average results are displayed in Table 11. It can be observed that the third objective is the most sensitive one to the importance weight in all cases while the second objective is the least. Thus, in industrial practice, decision makers are suggested to pay more attention to minimize the values of the disruption to the original schedule and the total tardiness while limiting the total energy cost in a reasonable range. Moreover, three different scenarios are analyzed underneath corresponding to different combinations of 𝛼, 𝛽 and 𝛾.

Scenario 1: When the decision-maker only wants to consider the minimum total tardiness, the importance weights can be set to 𝛼=100, 𝛽=1 and 𝛾=10. The disruption to the original schedule is the most sensitive one among three objectives. For the problems ABZ7 and LA35, its standard deviation is more than the double of the standard deviation of the total energy cost. Therefore, when there is no specific preference between the disruption to the original schedule and the total energy cost, the latter one can be neglected.

Scenario 2: When the decision-maker only wants to consider the minimum total energy cost, the importance weights can be set to 𝛼=1, 𝛽=100 and 𝛾=10. Although the gap of standard deviation between the total tardiness and the disruption to the original schedule is not so significant, the difference may still be obvious for some cases as the problem LA35. Thus, after the minimization of the total energy cost, the decision makers are advised to control the disruption to the original schedule prior to the total tardiness. Scenario 3: When the decision-maker only wants to consider the minimum disruption to the original schedule, the importance weights can be set to 𝛼=10, 𝛽=1 and 𝛾=100. The total tardiness is also very sensitive to the importance weight. For the problems MT10 and ABZ7, its standard deviation is quite close to the standard deviation of the disruption to the original schedule. Hence, a relative larger weight should be assigned to the total tardiness rather than the total energy cost in this case.

Conclusions and Future Works

In this paper, an investigation into minimizing the total tardiness, the total energy cost and the disruption to the original schedule in the job shop with new urgent arrival jobs was studied. To provide an adequate renewed scheduling plan in a reasonable time, a dual heterogeneous island parallel GA executed simultaneously on different parallel platforms was adopted. This design consisted of a cellular GA on GPUs and a classic GA on a multi-core CPU which was totally compliant with the underlying architectures of two-level parallelization. To improve the performance of the utilized GAs, the Taguchi method was used to calibrate their parameters firstly in the evaluation. Afterwards, the proposed method presented that it could obtain better solutions for solving six large size energy aware JSP through the integration of advantages from two different islands. In the meantime, it decreased the execution time obviously because of the simultaneously parallel execution on the host and the device while indicating the significance of computation capability balance between two sides. Concerning the EDJSP in the case study, the best-found solution of the updated schedule was shown by the Gantt chart. Compared with the original schedule, the processing time of some operations was significantly decreased. Finally, an experiment was carried to analyze the relationship among three objectives with different importance weights. After a discussion around three scenarios, some useful suggestions were made for industrial practice.

In the future, the Pareto optimal solution will be considered to solve the dynamic energy aware shop scheduling problems. It can be easily found in the literature that the Pareto optimal solution is a common approach to deal with the multi-objective optimization problems, apart from the linear combination method. The ranking and crowding mechanisms from the NSGA II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] are the mostly used strategy in the area. However, the non-dominated set of solutions managed during the optimization procedure is generally structured as the centralized Pareto front [START_REF] Luna | Parallel Multiobjective Evolutionary Algorithms[END_REF][START_REF] Talbi | A unified view of parallel multi-objective evolutionary algorithms[END_REF]. This strategy is hard to achieve parallelism in the population level. On the other hand, any partial parallelization on GPUs may lead to frequent communication overheads and offset the effectiveness. Therefore, developing a fine-grained Pareto based approach mapping onto GPUs underlying architecture and achieving the full parallelization deserves further study.

Fig. 1 .

 1 Fig. 1. A job shop layout

′ 1 𝜆 1 𝜑F

 11 New start time of operation s of job j on machine m, 𝑗 ∈ 𝐽 ∪ 𝐽′, 𝑠 ∈ 𝑂 𝑗 , 𝑚 𝜖 𝑀 TT Total tardiness of all jobs 𝐸𝑇 𝑚𝑎𝑥 Estimated maximum value of TT 𝐸𝑇 𝑚𝑖𝑛 Estimated minimum value of TT TE Total energy cost 𝐸𝐸 𝑚𝑎𝑥 Estimated maximum value of TE 𝐸𝐸 𝑚𝑖𝑛 Estimated minimum value of TE 𝑤𝑡 𝑗 Importance weight of original job j, 𝑗 ∈ 𝐽 DEV Weighted finishing time deviation of the updated schedule from the original one 𝐸𝐷 𝑚𝑎𝑥 Estimated maximum value of DEV 𝐸𝐷 𝑚𝑖𝑛 Estimated minimum value of DEV 𝛼, 𝛽, 𝛾 Weight of each normalized objective function. 𝜃 Migration threshold value, 0 ≤ 𝜃 ≤ Migration rate, 0 ≤ 𝜆 ≤ Migration policy execution gap, the frequency to perform the migration policy as defined in equation (12). 𝑓𝑖𝑡 𝐴 The best individual's fitness value of subpopulation A on island A 𝑓𝑖𝑡 𝐵 The best individual's fitness value of subpopulation B on island B a, b, c, f Gene indices in a chromosome 𝑣 𝑗 Index of occurrence time of job j 𝑢 𝑗 Occurrence time of job j U Set of occurrence time of a job number, 𝑈 = {0,1,2, … , 𝑢 𝑗 -1} 𝑘 Current generation number of the GA 𝑋(𝑘) Operation permutation of original schedule at generation k 𝑌(𝑘) Speed level permutation of original schedule at generation k 𝑋′(𝑘) Operation permutation of new schedule at generation k 𝑌′(𝑘) Speed level permutation of new schedule at generation k 𝑜 𝑗𝑠 Operation s of job j d, e Indices for operations on machine m 𝑜 𝑚 ′ Number of operations on machine m before operation s of job j is assigned on it 𝑂 𝑚 ′ Set of operations on machine m before operation s of job j is assigned on it, 𝑂 𝑚 ′ = {0,1,2, … , 𝑜 𝑚 ′ -1} N The number of orthogonal arrays in the Taguchi method The response values in the Taguchi method

Fig. 2 .

 2 Fig.2. The flow of the event-driven strategy for the EDJSP 4.2 Dual heterogeneous island parallel GA on hybrid CPU-GPU frameworks

Fig. 4

 4 Fig.4The procedure to generate new solutions by the cellular GA Because of the high frequency use of the roulette wheel selection, the classic GA on island B utilizes it for selecting individuals from the population according to their fitness values. As the next step, two randomly paired parent individuals carry out the crossover and the new offspring individual implements the mutation. After these steps, the all-time best individual is maintained and is used to replace the worst individual in the current generation. At the end, all individuals are sorted under the same condition as the cellular GA on GPUs. To respect the original mechanism without requesting specific underlying architecture, a master-slave model is utilized to parallelize the classic GA. In this case, only the fitness evaluation and the Bitonic-Merge sort are performed on a multi-core CPU as slave nodes while the rest procedures are handled at the master side in sequential. When this procedure is implemented, the OpenMP [37] (Open Multi-Processing) is used for programming parallel threads in multi-core applications.

X

  [k] = [ 𝑥 0 (𝑘), 𝑥 1 (𝑘), ⋯ , 𝑥 𝑎 (𝑘), ⋯ , 𝑥 ∑ 𝑗∈𝐽 𝑜 𝑗 -1 (𝑘) ] (13) where 𝑥 𝑎 (𝑘)𝜖[0, 𝑛 -1], 𝑢 𝑗 == 𝑜 𝑗 . Y[k] = [ 𝑦 0 (𝑘), 𝑦 1 (𝑘), ⋯ , 𝑦 𝑎 (𝑘), ⋯ , 𝑦 ∑ 𝑗∈𝐽 𝑜 𝑗 -1 (𝑘) ] (14) where 𝑦 𝑎 (𝑘)𝜖[0, ℎ -1].

  ) = [2, 0, 1, 4, 4, 4, 0, 1, 1, 3, 3, 2, 3, 0, 2] 𝑌′(𝑘) = [2, 1, 0, 2, 2, 2, 1, 2, 0, 0, 2, 1, 0, 1, 1] Fig.5An example of the operation-based order crossover The swap mutation is used for 𝑋′(𝑘) where different arbitrary genes within the range [𝑟2 , ∑ 𝑗∈𝐽∪𝐽 ′ 𝑜 𝑗 -1] are chosen and exchange values. Concerning 𝑌′(𝑘), unfixed number of genes are substituted by randomly generated values within the range, aside from the original ones. Following the above example, this procedure is illustrated in Fig.6where genes in green illustrate the execution of mutation. Before mutation 𝑋′(𝑘) = [2, 0, 1, 4, 4, 4, 0, 1, 3, 2, 2, 1, 3, 3, 0] 𝑌′(𝑘) = [2, 1, 0, 2, 2, 2, 1, 2, 0, 1, 0, 2, 0, 1, 2] After mutation 𝑋′(𝑘) = [2, 0, 1, 4, 4, 4, 0, 1, 0, 2, 2, 1, 3, 3, 3] 𝑌′(𝑘) = [2, 1, 0, 2, 2, 2, 1, 0, 0, 1, 0, 2, 0, 1, 2] Fig.6. An example of the mutation

Fig. 7 .Fig. 8 .Fig. 9 .Fig. 10 .Fig. 11 .Fig. 12 .

 789101112 Fig.7. The S/N ratio of the dual heterogeneous island parallel GA

  displays the 𝑅 -, 𝑅 + and p-values computed by SPSS [46] where the dual heterogeneous island parallel GA shows an improvement over the parallel cellular GA for instances EASY 20× 10, EASY 50× 10, HARD 20× 10, HARD 20× 20 and HARD 50× 10, over the parallel classic GA for instances EASY 20× 10, EASY 20× 20, EASY 50× 10, HARD 20× 10 and HARD 20× 20 when the significance level equals to 0.1.

Fig. 13 .Fig. 14 .

 1314 Fig. 13. The Gantt chart of the best-found solution of the original schedule for the M10 based EDJSP

Table 1

 1

	The used notations
	Notation	Description
	𝑗, 𝑖, l, x, z	Job indices
	𝑠, 𝑡, y	Operation indices
	𝑚	Machine index
	p, q, w	Speed level indices
	𝑛	Amount of original jobs
	𝑛′	Amount of new urgent arrival jobs
	r1	Amount of completed operations of original jobs before the rescheduling point
	r2	Sum of completed operations of original jobs before the rescheduling point and operations of new urgent arrival jobs
	𝑜 𝑗	Amount of operations of job j
	𝑔	Amount of machines
	h	Amount of speed levels

𝐽

Set of original jobs, 𝐽 = {0,1,2, … , 𝑛 -1} 𝐽′ Set of new arrival jobs, 𝐽′ = {0,1,2, … , 𝑛′ -1} 𝑂 𝑗 Set of operations of job j, 𝑂 𝑗 = {0,1,2, … , 𝑜 𝑗 -1} M Set of machines, 𝑀 = {0,1,2, … , 𝑔 -1} L Set of speed levels, L = {0,1,2, … , ℎ -1} 𝑅 𝑗 Release time of job j, 𝑗 ∈ 𝐽 ∪ 𝐽′ 𝐷 𝑗 Due time of job j, 𝑗 ∈ 𝐽 ∪ 𝐽′ 𝑇 𝑗 Tardiness of job j, 𝑗 ∈ 𝐽 ∪ 𝐽′ 𝑀 𝑗𝑠 Target machine handling operation s of job j, 𝑗 ∈ 𝐽 ∪ 𝐽′, 𝑠 ∈ 𝑂 𝑗 𝑅𝑆 Rescheduling point 𝑃 𝑗𝑠𝑚𝑝 Processing time when operation s of job j handled by target machine m at speed level p, 𝑗 ∈ 𝐽 ∪ 𝐽 ′ , 𝑠 ∈ 𝑂 𝑗 , 𝑚 𝜖 𝑀, 𝑝 𝜖 𝐿 𝑄 𝑗𝑠𝑚𝑝 Energy cost when operation s of job j handled by target machine m at speed level p, 𝑗 ∈ 𝐽 ∪ 𝐽 ′ , 𝑠 ∈ 𝑂 𝑗 , 𝑚 𝜖 𝑀, 𝑝 𝜖 𝐿 𝑍 𝑗𝑠𝑚𝑝 Boolean variable, it is equal to 1 if operation s of job j is handled by target machine m at speed level p, otherwise, it equals to 0, 𝑗 ∈ 𝐽 ∪ 𝐽 ′ , 𝑠 ∈ 𝑂 𝑗 , 𝑚 𝜖 𝑀, 𝑝 𝜖 𝐿 𝑆 𝑗𝑠𝑚 Original start time of operation s of original job j on machine m, 𝑗 ∈ 𝐽, 𝑠 ∈ 𝑂 𝑗 , 𝑚 𝜖 𝑀

Table 2 .

 2 The data relative to the experience of the energy aware JSP 𝑃 𝑗𝑠𝑀 𝑗𝑠 𝑝 U[START_REF] Paolucci | Facing energy-aware scheduling: a multiobjective extension of a scheduling support system for improving energy efficiency in a moulding industry[END_REF][START_REF] Xu | Energy-Efficient Scheduling for Flexible Flow Shops by Using MIP[END_REF]

	𝑄 𝑗𝑠𝑀 𝑗𝑠 𝑝	𝛿 × 𝑃 𝑗𝑠𝑀 𝑗𝑠 𝑝 2	, where 𝛿=U[2, 4]
	𝑅 𝑗	U[0, 𝑃], where 𝑃 = ∑ 𝑗	(∑ 𝑠	(∑ 𝑝 𝑃 𝑗𝑠𝑀 𝑗𝑠 𝑝 /ℎ)/𝑜 𝑗 )
	𝐷 𝑗	𝑅 𝑗 + 𝑃 𝑗 × (1 + 𝜎), where 𝜎=U[0, 2] and 𝑃 𝑗 =
		∑ 𝑠	(∑ 𝑝 𝑃 𝑗𝑠𝑀 𝑗𝑠 𝑝 /ℎ)
	𝛼	1
	𝛽	1

Table 4 .

 4 The orthogonal array 𝐿 27

	Run order	𝑃 𝑐𝑎𝑐	𝑃 𝑐𝑎𝑚	𝑃 𝑐𝑒𝑐	𝑃 𝑐𝑒𝑚	𝜃	𝜑
	1	1	1	1	1	1	1
	2	1	1	1	1	2	2
	3	1	1	1	1	3	3
	4	1	2	2	2	1	1
	5	1	2	2	2	2	2
	6	1	2	2	2	3	3
	7	1	3	3	3	1	1
	8	1	3	3	3	2	2
	9	1	3	3	3	3	3
	10	2	1	2	3	1	2
	11	2	1	2	3	2	3
	12	2	1	2	3	3	1
	13	2	2	3	1	1	2
	14	2	2	3	1	2	3
	15	2	2	3	1	3	1
	16	2	3	1	2	1	2
	17	2	3	1	2	2	3
	18	2	3	1	2	3	1
	19	3	1	3	2	1	3
	20	3	1	3	2	2	1
	21	3	1	3	2	3	2
	22	3	2	1	3	1	3
	23	3	2	1	3	2	1
	24	3	2	1	3	3	2
	25	3	3	2	1	1	3
	26	3	3	2	1	2	1
	27	3	3	2	1	3	2

Table 5 .

 5 The orthogonal array 𝐿 9 Run order 𝑃 𝑐𝑎𝑐 /𝑃 𝑐𝑒𝑐 𝑃 𝑐𝑎𝑚 /𝑃 𝑐𝑒𝑚

	1	1	1
	2	1	2
	3	1	3
	4	2	1
	5	2	2
	6	2	3
	7	3	1
	8	3	2
	9	3	3

Table 6 .

 6 The solutions' quality comparison

	Problems	Parallel heterogeneous GA Average Best	Parallel cellular GA Average Best	Parallel classic GA Average Best
	EASY 20× 10	0.0481	0.0224	0.0551	0.0308	0.0623	0.0490
	EASY 20× 20	0.0901	0.0568	0.0911	0.0468	0.1007	0.0831
	EASY 50× 10	0.0585	0.0110	0.1290	0.0378	0.0643	0.0292
	HARD 20× 10	0.0412	0.0258	0.0441	0.0227	0.0747	0.0499
	HARD 20× 20	0.1025	0.0421	0.1750	0.0916	0.1219	0.0849
	HARD 50× 10	0.0706	0.0236	0.0932	0.0075	0.0709	0.0291

Table 11 .

 11 The relationship among three objectives

	Problems NO. of machines	NO. of jobs	Weight of each normalized objective function 𝛼 𝛽 𝛾	𝑇𝑇 -𝐸𝑇 𝑚𝑖𝑛 𝐸𝑇 𝑚𝑎𝑥 -𝐸𝑇 𝑚𝑖𝑛
				100	10	1	0.0469
				100	1	10	0.0464
				10	100	1	0.1864
	MT10	10	10	1	100	10	0.1813
				10	1	100	0.0460
				1	10	100	0.0520
					Standard deviation	0.0702
				100	10	1	0.0845
				100	1	10	0.0794
				10	100	1	0.2169
	ABZ5	10	10	1	100	10	0.2292
				10	1	100	0.1043
				1	10	100	0.1098
					Standard deviation	0.0674
				100	10	1	0.0937
				100	1	10	0.0904
				10	100	1	0.2049
				1	100	10	0.2199
	ABZ7	15	20	10	1	100	0.1100
				1	10	100	0.1136
					Standard deviation	0.0579
				100	10	1	0.2354
				100	1	10	0.2363
				10	100	1	0.3075
	LA35	10	30	1	100	10	0.2973
				10	1	100	0.2405
				1	10	100	0.2412
					Standard deviation	0.0333
				100	10	1	0.1814
				100	1	10	0.1800
				10	100	1	0.2832
	LA40	15	15	1	100	10	0.2852
				10	1	100	0.1903
				1	10	100	0.1928
					Standard deviation	0.0508

Acknowledgement

This work is supported in part by the Japan Society for the Promotion of Science. Moreover, Didier El Baz is grateful to NVIDIA Corporation for the donation of the Tesla K40 GPUs used in this work and the authors would like to express their gratitude to the editors and the reviewers for their helpful comments.

The execution time of three parallel GAs with different population sizes are shown in Table 8.

Because of the simultaneous execution on both sides, the dual heterogeneous island GA on the hybrid platform overcomes the parallel cellular GA on GPUs and the parallel classic GA on a multicore CPU in most cases. This phenomenon is even more remarkable when the difference of the execution time on two islands is smaller. However, the advantage from the hybrid platform may be reduced because the overall performance is limited to the island who takes longer execution time. Therefore, it indicates the significance of computation capability balance between the multicore CPU and the GPUs when the dual heterogeneous island GA is implemented. For some extreme situations, the weak node may perform as a bottleneck and decreases the global effectiveness.


Alain Walcarius
email: alain.walcarius@univ-lorraine.fr

Promises of the "Nano-World" for Electrochemical Sensing and Energy Devices

Introduction

Does talking about nano to a chemist make sense? Indeed, chemists are "playing" with very small objects (i.e., molecules) for as long as chemistry exists. But it is clear that the "Nano-World" has revolutionized many areas of Chemistry, among them electrochemistry. The reasons are not so much that small is beautiful or the need for miniaturization, but rather that the properties of an object can be intrinsically different when its size becomes smaller than a critical dimension or when its structure/morphology can be tuned at the nanoscale. One can clearly understand that reducing (or increasing) the size by a factor ten in one dimension will contribute to decrease (or enlarge) areas and volumes by a factor of a hundred or a thousand, respectively, with the associated dramatic variations in terms of surface boundary effects or surface-to-volume ratios. Similarly, when introducing a porosity at the nanometre scale (or below) in a solid object, this may not only increase its specific surface area by several orders of magnitude but also modify its intrinsic reactivity compared to a bulk material of the same composition. One example illustrative of the first concept is that of ultramicroelectrodes (µm size or less), which were first designed to local measurements in the human body but have been much more largely used afterwards owing to their unconventional properties, making them likely to be used in poorly conductive media or to enable analytical investigations in the nanosecond time scale, which is not possible with electrodes of conventional size (mm size) [START_REF] Amatore | Molecular electrochemistry of inorganic, bioinorganic and organometallic compounds[END_REF]. Another example to illustrate the second concept is that of nanostructured electrode materials, which are characterized by ultrahigh density of active sites while maintaining a high level of accessibility for effective mass transport, and therefore very attractive for applications in the field of electrochemical sensing or energy storage and conversion, for instance [2][START_REF] Moldoveanu | Handbook of Nanoelectrochemistry[END_REF][START_REF] Manthiram | [END_REF][5]. A third aspect, actually featured by both families of nanomaterials (nanoparticles and nanostructured solids), is related to their electrocatalytic properties induced by their small size and/or structuration at the nanoscale [6]; such catalytic features can accelerate charge transfer reactions and thereby offer benefits to current and future technologies with social relevance where electrochemistry is involved and for which the basic foundations are similar [2,[7][8][9]. Many things have been already made in these directions but, scientifically-peaking, there is still a lot of questions to be answered and many developments calling electrochemists. I'll try to consider very briefly some aspects of two topics in the next paragraphs: sensing and energy, two domains in which electrochemists have great role to play nowadays.

Electrochemical sensing

Electrochemical sensors are a sub-class of chemical sensors that are basically interesting for low-cost, on-site quantification purposes and real-time monitoring, compared to other analytical techniques requiring more sophisticated facilities associated to sample preparation procedures (which are often not simple enough for point-of-care applications). Their ability to determine the concentration of target species, either directly (heavy metals or pesticides, for instance) or indirectly (redox-inactive species involved in biological reactions that can be detected via an electrochemical transduction), makes them promising but at the condition to be sensitive and selective enough and offering an acceptable long-term operational stability.

If the glucose sensors and some other electrochemical biosensors are now established among the commercially successful technologies [10][11][12] and if wearable and/or skin electrochemical sensors appear to be very promising for economically viable applications [13][14][15], there are still a lot of room for improvement. Nanomaterials have proven to be suitable candidates contributing to the evolvement of electrochemical sensing platforms and hundreds of reviews are available dealing with the use of various kinds of electrode modifiers, such as nanoparticles, 2D layered nanomaterials or 3D nanostructures owing to their electrocatalytic response and/or recognition capabilities (see some illustrative examples [16][17][18][19][20][21]). However, the focus of many studies is targeted towards feasibility demonstration, association of multiple nanomaterials for signal amplification, determination of analytical figures of merit and comparing systems between them, etc. but not always with a good knowledge of the associated mechanisms and the objective of real sample analyses (i.e., not intentionally spiked media). Some key issues that are ripe for investigation are: the distinction between real synergistic effects and 'simple' additive contributions in case of using multiple nanocomponents; the elucidation of signal amplification mechanisms, notably with respect to the question of selectivity (e.g., what about the interest of using an electrocatalyst that is active for several species, including possible interference?); an integrative approach might be useful to determine the most adequate electrode modifier(s) for a target analyte (perhaps data mining could help on that matter, providing the analytical procedures and results can be compared); the optimal design of an electrode material exhibiting mass and electron transfer processes as fast as possible (which probably needs to be associated to an effective recognition element to ensure proper selectivity of the sensitive detection); smart sensors based on miniaturized multi-electrodes (lab on chip) associated to artificial intelligence for improving selectivity by cross-talking; or determining the electrochemical behaviour of recently discovered nanomaterials (e.g., non-carbonaceous 2D or 3D materials). This will require more fundamental understanding of both the amplification strategies and the physico-chemical properties of such electrode modifiers [22], as wall as suitable nanoengineering design to build electrochemical sensing devices for environmental or health issues monitoring, which one may hope to be suitably addressed from closer collaborations between materials scientists and electrochemists.

Energy devices

A domain where such close collaboration is perhaps more straightforward is that or energy conversion and storage, probably for historical reasons, which is notably illustrated through the Nobel Prize in Chemistry 2019 for the development of lithium-ion batteries. Indeed, nanomaterials, and especially nanostructured materials, are at the centre of most electrochemistry-related technologies pertaining to energy and, again, hundreds of reviews are available dealing with the attractiveness of the "Nano-World" in developing batteries, capacitors, fuel cells, solar cells or other electrochemical energy-harvesting systems (see some illustrative examples [START_REF] Simon | Nanotechnology for the Energy Challenge[END_REF][START_REF] Gogotsi | [END_REF][25][26][27][28][29]). Optimization of existing technologies and finding of new energy-generation/conversion and storage solutions will certainly require that the researches in support of electrochemistry application in energy should be oriented towards the elucidation of its fundamental aspects. Good practices to evaluate and compare the performance of such devices are also necessary [30]. A sub-domain for which fundamental electrochemical investigations have been particularly useful is that of capacitors, notably via the insightful elucidation of electrical double layer energy storage with microporous carbon electrodes [31]. Just to keep focusing on one aspect of this very wide area of research, a domain where nanoscience and nanotechnology are expected to play a major role in near future is that of supercapacitors, which are energy storage devices with both high energy and power density [32][33][34][35]. The search for new materials likely to increase the energy density of classical electrochemical capacitors (i.e., based on double layer charge/discharge processes) led to the emergence of so-called supercapacitors involving pseudocapacitive materials [36] in which a faradic contribution is added to the conventional capacitive behaviour (the word "pseudocapacitive" is used here even if the border between supercapacitors and batteries is still a matter of debate from the terminological point of view [37,38]). What needs to be done in this case is the design and development of composite materials containing the necessary constituents ensuring a large charge storage capacity along with fast electron transfer rates.

This could be ideally obtained from large area conducting supports (as multi-dimensional carbon nanostructures or more recent two-dimensional materials) carefully modified with thin layers of faradic compounds. Nowadays, such layers are mainly metal monolayers generated by underpotential deposition or insertion/intercalation coatings usually used in batteries but suffering therefore from slow reaction rates (both in terms of electron transfer kinetics or diffusional limitations). Strategies are thus to be found to get large area electrodes uniformly coated with thin films displaying a huge contribution of efficient self-exchangebased charge transfer and fast coupled mass transport [39,40]. A possible avenue would be the molecular engineering of rigid nanostructures with redox sites anchored via flexible arms to enable high electron transfer rates between adjacent electroactive centers whereas the open rigid framework ensures rapid diffusion of counter ions.

Conclusion

Through these two sub-fields of electrochemical science, it is clear that combining the "Nano-World" with electrochemistry has contributed, is still contributing, and will contribute in the future to the development of emerging technologies useful to the human being.

Electrochemistry, as well as nanoscience and nanotechnology, are in their golden age.

Nevertheless, despite the abundance of research funds for applied scientific research, much work has still to be performed in building the fundamentals of these areas, and this is not incompatible as one learned from many successful stories in the past. Moreover, independently on the target applications, the same basics of electrochemistry can be useful in several fields which may appear distant from each other (e.g., similar concepts of electrocatalysis are likely to be exploited in bioelectrochemistry, electrochemical sensing or energy). Hoping it can inspire the younger generation for the future, without forgetting that most glaring discoveries and breakthroughs originate from very simple ideas.

Acknowledgements

The author is grateful to Professor Dr. Fritz Scholz for his kind invitation to write such a small contribution to the special issue entitled "Future tasks of electrochemical research".


Generation of the induced pluripotent stem cell line

  UHOMi002-A from peripheral blood mononuclear cells of a healthy male donor Mathieu Fieldes, Engi Ahmed, Chloé Bourguignon, Joffrey Mianné, Martin Mélanie, Cécile Arnould, Isabelle Vachier, Said Assou, John de Vos, Arnaud Bourdin To cite this version: Mathieu Fieldes, Engi Ahmed, Chloé Bourguignon, Joffrey Mianné, Martin Mélanie, et al.. Generation of the induced pluripotent stem cell line UHOMi002-A from peripheral blood mononuclear cells of a healthy male donor. Stem Cell Research, 2020, pp.102037. 10.1016/j.scr.2020.102037. hal-02965353