Hybrid deep convolution network and differential evolution algorithm for solving non-permutation flow shop scheduling problem

Abstract

With explosive growth of industrial big data, workshop scheduling faces problems such as high complexity, multi-dimensionality and low stability. Recent years, the wide application of deep learning provides new idea for scheduling problem. In this paper, a hybrid deep convolution network and differential evolution algorithm is proposed to solve the non-permutation flow shop scheduling problem with the goal of minimizing total completion time. Mining relationship between job attributes and process priority by deep convolutional network is core idea of this method. In this paper, differential evolution algorithm is used to obtain the data set for deep learning, and neighborhood search algorithm is used to optimize scheduling solution. Additionally, a method combining k-means algorithm and data statistics is proposed, which provides a reasonable way for priority division. The experimental results show that this method can greatly improve scheduling efficiency.

Keywords

Differential evolution algorithm convolutional neural network K-means algorithm;priority flow shop scheduling

1 Introduction

Workshop scheduling is related to production efficiency and affects competitiveness of enterprises, flow shop as a common type of workshop has been widely studied for a long time [1, 2]. There are two types of flow shop: permutation and non-permutation. The jobs maintain the same processing order in all stages is permutation flow shop (PFS), relaxing the constraint of job processing order is non-permutation flow shop (NPFS) [3]. Non-permutation flow shop scheduling problem (NPFSSP) studies that n independent jobs are processed by m machines in turn, the processing order in different stages can be different, which makes general and practical [4–6].

NPFSSP has been proved to be NP-hard when the number of machines is larger than three [7]. At present, there are mainly three methods to solve NPFSSP: precise algorithm, heuristic algorithm and deep learning method. The precise algorithm can usually find the best solution accurately by searching all solutions according to certain rules. However, scheduling problem is usually complex, as the scale of problem expands, the solution space will increase exponentially [8], which makes solution time increase. Therefore, precise method is usually suitable for small-scale problems.

Heuristic algorithms abstract some phenomena from nature and biological populations into algorithms, and obtain an approximate optimal solution after several iterations [9]. This method can find a feasible solution for scheduling problem within acceptable solution time. However, with the expansion of problem scale, the heuristic algorithms have some randomness in search process, which may lead to unstable feasible solutions. Nevertheless, heuristic algorithms iterate according to specific rules, which makes optimal solutions have certain similarity, that is “survivor feature" [10]. Specifically, in different optimal solutions, one job may tend to be processed in front (or behand), further, if this job is replaced with a similar one and rescheduled, the processing positions of the two jobs in optimal solution are also similar. This phenomenon indicates that the processing order of jobs may be related to certain features. These job features may include processing time, processing cost, delivery time, etc. By mining these job features related to processing order, we can better understand optimization process of scheduling problems and improve performance of heuristicalgorithms.

As an intelligence algorithm, deep learning method can effectively mine hidden connections among data [11]. Convolutional neural network (CNN) are one of the representative algorithms of deep learning, with features of local perception, weight sharing, and pooling. They can reduce computational complexity, improve the generalization ability of model, and reduce overfitting risks. It is widely used in various applications. Additionally, the workshop will generate massive production data in manufacturing process, these production data provide abundant training datasets for deep learning. Therefore, deep learning has great application space in scheduling problem [12]. However, the scheduling data in actual workshop is numerous and miscellaneous, which makes it difficult to obtain high-quality dataset for deep learning.

Based on this, heuristic algorithms can be combined with deep learning. The heuristic algorithm can obtain optimal solutions quickly, these solutions can be used as original training dataset for deep learning. This method can instead of labelling jumbled production data in workshop. In optimal solutions, we select appropriate job features as inputs for deep learning, define processing order as priority, and use it as output of deep learning. The connection between job features and priority can be applied in workshop to quickly obtain approximate processing order of new jobs. In this way, this method can greatly improve production efficiency of workshop.

Therefore, this paper proposes a hybrid differential evolution algorithm, deep convolution neural network and neighborhood search algorithm (DEA-CNN-NS) method for NPFSSP. This method includes two parts: offline training and online scheduling. The offline training part mainly simulates actual production of workshop by generating scheduling task, and solves scheduling problem through DEA. The scheduling solutions from DEA are used as label data for training CNN. For the important attribute: priority, we propose a method combining K-means and data statistics (KM-DS) to obtain priority division method. The online scheduling part mainly solves scheduling problem of new jobs in workshop. Firstly, input new jobs’ attributes into the trained network to obtain corresponding priority, then arranging these new jobs according to their priorities to obtain an initial scheduling sequence. Finally, a neighborhood search algorithm is proposed to acquire higher quality solution. The experimental comparison proves that DEA-CNN-NS is more efficient than commonly used intelligent algorithm.

The rest of this paper is arranged as follows: Section 2 presents related research on NPFSSP. Section 3 describes the research problem through mathematical model. Section 4 introduces the main methods and algorithm framework. Section 5 represents each part of DEA-CNN-NS in detail. Section 6 carries out experimental comparison and reports computational results. Finally, Section 7 summarizes and prospects current research.

2 Literature review

Precise algorithm is often used to solve small-scale scheduling problems. Linear programming, branch and bound algorithm are commonly used precise algorithm. Mehravaran et al. [13] developed a linear mathematical model for NPFSSP, which comply with all of the operational constraints commonly encountered in industry. This method is designed to minimize work-in-process inventory for producer and to maximize the customers service level. Dhouib et al. [14] address the NPFSSP with minimal and maximal time lags between successive operations of each job, proposed a mixed integer linear programming model to minimize the number of tardy jobs and the makespan. Assia et al. [15] formulated a mixed binary integer programming model for NPFSSP with non-availability intervals, to minimize the total energy consumption and makespan. Meng et al. [16] considered two-stage NPFSSP with purpose of minimization of total completion time, presented a mixed integer programming model, and compared experiment results proving that it is more efficient than CPLEX. Gmys et al. [17] developed an efficient branch-and-bound algorithm, which contains a new node decomposition scheme that combines dynamic branching and lower bound refinement strategies in computationally efficient way. They applied this algorithm for the PFSSP with objective of minimizing total completion time. Chung et al. [18] developed a dominance theorem and a lower bound to accelerate branch-and-bound algorithm for minimizing the makespan in PFSSP with learning considerations. The experiment results showed that the branch-and-bound algorithm can solve problems of up to 18 jobs within a reasonable time.

Although precise algorithms can find the optimal solution, their workload increases exponentially with the expansion of problem scale [19]. However, meta heuristic algorithm can obtain the near optimal solution of the problem in a short time. In particular, a well-designed hybrid meta algorithm can achieve better performance than a single algorithm [20]. Aiming at permutation flow shop scheduling problem (PFSSP) with batch delivery to multiple customers, Wang et al. [21] developed a novel meta-heuristic (GA-TVNS) to minimize the total cost of tardiness and batch delivery. Li et al. [22] considered two-machine PFSPP with learning effects involving both experience and forgetting effects, proposed four heuristic algorithms combined with Branch and Bound algorithm (BB) to minimize makespan. Xiao et al. [23] focused on NPFSSP with order acceptance and weighted tardiness, presented a non-linear integer programming model and designed a two-phase genetic algorithm (GA) to solve this problem of medium and large sizes. Cui et al. [24] proposed a hybrid incremental genetic algorithm (HIGA) which combined population diversity super vision scheme and local refinement to solve the large-sized NPFSSP efficiently. Vahedi Nouri et al. [25] studied medium and large scale NPFSSP with learning effect, and proposed an improved meta-heuristic algorithm combining simulated annealing algorithm (SAA) and firefly algorithm (FA) to solve it. Zheng et al. [26] developed a novel quantum differential evolutionary algorithm (QDEA) based on the basic quantum-inspired evolutionary algorithm (QEA) for NPFSSP with the objective of minimizing the maximum completion time. Li et al. [27] developed a heuristic algorithm based on genetic algorithm (GA) to minimize the total weighted completion time in two-machine robotic non-permutation flow shop scheduling. Ying et al. [28] utilized ant colony system (ACS) to deal with NPFSSP with objective of minimizing the makespan. Benavides et al. [29] applied a constructive and an iterated local search heuristic in NPFSSP for minimizing the makespan.

With the continuous development of artificial intelligence technology, deep learning technology are increasingly being applied to the field of workshop scheduling. Olafsson et al. [30] proposed a method of using decision tree to learn scheduling rules from optimized scheduling data, and applied it to single machine scheduling problem. When two jobs are given, the decision tree can predict which job should be processed first. Wang et al. [31] used a branch and demarcation algorithm based on Petri nets to generate efficient solutions. The knowledge is extracted from the decision tree and combined with other heuristic methods to form a compound scheduling rule, which can further improve its performance on the basis of obtaining solution generated by Petri net-based branching algorithm. Shiue et al. [32] established a real-time scheduling knowledge base by combining Q-learning and multiple scheduling rules to solve the problem of dynamic workshop scheduling. Ren et al. [33] utilized reinforcement learning (RL) to solve FSSP, mapped different states in FSP and corresponding optimal scheduling rules to RL actions, and trained neural network to establish the relationship between states and actions, so as to select optimal rules for the states in workshop. To solve the dynamic flexible workshop scheduling problem, Liu et al. [34] set up specialized state and action representations, and used the dual deep Q-network algorithm to train the mapping relationship between variables, thereby achieving real-time scheduling of dynamic workshops. Sun et al. [35] proposed an architecture based on heterogeneous graph networks to capture the complex relationships between operations and machines for flexible JSP, and designed a new deep reinforcement learning (DRL) method to end-to-end learn high-quality priority dispatching rules (PDRs) to solve the problem. Lin et al. [36] studied a job shop scheduling problem (JSSP) under the intelligent manufacturing factory framework based on edge computing, proposed a deep Q network (DQN) combining deep learning and reinforcement learning, and adjusted it using edge computing framework to solve JSP.

It can be summarized that the application of deep learning is mainly to min useful scheduling knowledge from historical scheduling data to guide production. However, there are still some problems in previous research. For example, references [37, 38] directly divided priority according to the number of jobs or divided into three levels without theoretical basis. What’s more, it is not convenient to obtain excellent historical data in many workshops, and the complex potential relationship between job features and priority also increases the difficulty of data mining. Therefore, this paper uses KM-DS to get the priority of job. In addition, using DEA to solve scheduling problem, and generate label data for the training of CNN. Finally, a neighborhood search algorithm is used to remedy the error caused by deep learning.

3 Problem description and modeling

3.1 Problem description

The NPFSSP can be described as follows: a group of jobs N = {1, 2, 3,... , n} are processed on a group of machines M = {1, 2, 3, ... , m}. The processing paths of all jobs are the same, the processing order of jobs on different machines can be changed. The purpose of article is to arrange processing sequence of jobs on each machine, minimizing total process time.

In order to describe this mathematical model, relevant parameters and variables are listed as Table 1.

Table 1
Summary of notations

n The number of jobs

m The number of machines

i Index of jobs, i = 1, 2, 3, …, n

j The set of machine, j = 1, 2, 3, …, m

O _i,j The j-th operation of job i

T _i,j Processing time of operation O_i,j

m _i,j The number of machine for O_i,j

ST _i,j Starting time of operation O_i,j

ET _i,j Ending time of operation O_i,j

p _i,j,k Processing time of O_i,j on machine k

x _i,j,k Equals to 1 if O_i,j is processed on machine k, otherwise 0

r The processing priority

r _i,j Priority of the j-th operation of jobi

ST _k,r The start time of the r-th operation processed on machine k

y _i,j,k,r Equals to 1 if O_i,j is processed at positionr of machine k, otherwise 0

π A scheduling sequence

C_max (π) The makespan of π

Q A number large enough

c _i Occurrence number of job in the i-th position of sequence, i = 1, 2, 3, …, n

L _{Job
_i} Length of one priority determined by job i, i = 1, 2, 3, …, n

a Number of priorities

P _l Priority l, l = 1, 2, 3, …, a

s _t Individuals in DEA,t = 1, 2, …, NP

$s_{t}^{λ}$ The λ-th dimensional vector of individual s_t

s_t (g) Individual s_t in the g-th iteration

v _t Variation individual

u _t Cross individual

Fig. 1

The framework diagram.

3.2 Assumptions

Min (C_{max}) = Min (C_{max} (π))

(1)

m_{i, j} = j, i = 1, 2, 3, . . ., n, j = 1, 2, 3, . . ., n

(2)

{ST}_{i, j} + \sum_{k = 1}^{m_{i, j}} p_{i, j, k} \cdot x_{i, j, k} \leq {ST}_{i, j + 1}

(3)

{ST}_{k, r} + \sum_{k = 1}^{m_{i, j}} p_{i, j, k} \cdot y_{i, j, k, r} \leq {ST}_{k, r + 1}

(4)

{ET}_{i, j} \geq 0

(5)

\begin{matrix} {ST}_{i, j} \geq max {{ST}_{k, r} - (1 - y_{i, j, k, r}) \cdot Q, {ST}_{i, j - 1} \\ + \sum_{k = 1}^{m_{i, j - 1}} p_{i, j, k} \cdot x_{i, j, k}} \end{matrix}

(6)

C_{max} \geq E_{i, j} (\forall i, \forall j)

(7)

x_{i, j, k} \in {0, 1}

(8)

y_{i, j, k, r} \in {0, 1}

(9)

Among them, Equation (1) defines the objective of this problem, Equation (2) ensures that each operation can only be processed on corresponding machine, Equation (3) ensures that the next operation of one job can only be started after its previous operation is completed, Equation (4) ensures that the next operation on one machine can only be started after previous operation on this machine is completed, Equation (5) stipulates that completion time of job must be non-negative, Equation (6) ensures that one operation can only be started after its previous operation is completed and previous job on current machine is finished, Equation (7) defines overall completion time, Equations (8) and (9) define value range of decision variables.

4 Data driven learning framework

The framework of DEA-CNN-NS is shown in Fig. 1. It includes offline training part and online scheduling part. The offline training part includes generating scheduling sequence dataset, obtaining training label data, training network. The online scheduling part includes extracting attributes of new jobs, obtaining priorities of new jobs, and NSA. The specific implementation steps of this method are as follows.

Step 1: Using DEA to solve NPFSSP and obtain excellent scheduling sequence for training [39]. Run DEA several times to solve a case of NPFSSP, and retain the optimal solution for each run. These optimal solutions can better reflect the relationship between job attributes and processing priority, and can be used as training dataset for CNN.

Step 2: Obtaining label data from scheduling solutions dataset. In the training of CNN, we select several attributes related to processing as input data. For output data - job priority, we design a reasonable division method, which utilizes K-means algorithm and data statistics to process the dataset and obtain priority from the rules of dataset.

Step 3: Training deep convolution network. This paper uses CNN to mine relationship between job attributes and priority. The trained network is equivalent to a scheduler which can reflect relationship between job attributes and priority. When new jobs arrive, obtain their attributes as input, the output is priority of new job. Arranging new jobs according to their priorities can get an excellent initial scheduling sequence

Step 4: Apply neighborhood search algorithm to improve solution quality. Since a priority may contain more than one job, when generating scheduling sequence code, the jobs in the same priority are automatically arranged, which leads to the quality of solution cannot achieve desired effect. Moreover, there are a little error in training results of network. In order to improve scheduling solution, the solution obtained by network needs to be further optimized. Based on initial scheduling sequence, the neighborhood search is carried out, after several simple iterations, a satisfactory solution can be obtained.

5 Algorithm design

5.1 Offline training framework

This paper proposes an offline training framework based on DEA to driven deep learning. Compared with previous research on job priority, we use KM-DS to get priority division method, which makes result more rigorous. There are three main parts: generating scheduling sequence database by DEA, obtaining training label data, training network.

5.1.1 The DEA

The core idea of DEA is described as follows: select three individuals s₁, s₂, s₃ in population randomly, adding vector difference between s₁and s₂ to s₃ can obtain v_t, then cross s₁ and v_t to obtain u_t, compare s_t with u_t and retain the better one to enter the next iteration. The general process of the algorithm is shown in Fig. 2.

Fig. 2

The framework diagram of DEA.

Coding mode

When generating scheduling sequence, the code is operated by stages, and then connect each stage in turn to form a complete scheduling code, as shown in Fig. 3. In scheduling sequence, the number represents job id, and the m-th occurrence of the number represents the m-th processing stage of this job. When the code is transformed into a specific scheduling scheme, also operated by stages. When a machine is idle, the jobs of corresponding stage are placed on machine in order.

Fig. 3

Chromosome coding.

Processing of boundary condition

Since the number of scheduling code represents different job, the scheduling code must be an integer within a certain range. However, the DEA will generate irregular number during mutation, which requires boundary condition processing for non-integer and out-of-range numbers in scheduling sequence code. If the decimals are rounded directly, it may appear out of range numbers or repeated numbers, which is also unreasonable. So, the boundary condition processing is designed as follows: the numbers in sequence code are sorted by size, and their ranking in sequence code is used to replace this number, as shown in Fig. 4. In this way, it not only ensures that numbers are within a reasonable range, but also ensures that the number of job is not repeated in sequence code.

Fig. 4

Processing of boundary condition.

5.1.2 Priority division

In scheduling sequence, the more front the position of job, the higher the priority is. In NPFSSP, the optimal solution is often not unique, one job may have different positions in different scheduling sequences. This leads to different priorities for the same job in training data. Therefore, this paper uses KM-DS to obtain a reasonable way of priority division, the specific implementation ideas are as follows:

Due to the potential relevance of excellent scheduling sequences, although the position of a job in different scheduling sequences is not unique, it is mostly fixed in a few positions. Counting the number of occurrences of the job at each position, get a set of numbers {c₁, c₂, c₃, ·· · , c_n }, the large number in array reflects that the job often appears at that position, several larger numbers are position interval where this job often appears, the length of position interval is the length of priority determined by this job, denoted as L_Jobi. However, it is not rigorous to directly select larger numbers from the array based on subjective judgment. In order to ensure the accuracy of experiment, K-means algorithm is used to cluster the numbers in array into two groups. The K-means algorithm is a commonly used clustering method. It can divide the dataset into K clusters, and the mean of all samples in each cluster is called “centroid". The basic process of the K-means algorithm includes: first, randomly selecting K nodes as initial centroids; then, determining the category of each node based on the distance from each centroid; finally, recalculating the mean of all samples in cluster as the new centroid. Based on statistical data obtained, K-means algorithm can cluster them and obtain the L_Jobi of each job.

As shown in Fig. 5, Job₁often appears in first four positions, so the best priority division determined by Job₁ is that four positions form a priority, while Job₂ is suitable for three positions to form a priority. Perform the same processing on all jobs, get an array {L_Job1, L_Job2, L_Job3, … , L_Jobn }, the highest frequency number is the length of priority.

Fig. 5

Priority division method.

5.1.3 Job attribute extraction

The processing attributes of job refer to some hidden features in job processing. According to the characteristics of flow shop scheduling problem and the attribute-oriented induction method [10], this article extract following attributes.

Operation number: The order of operation in current job. The position of each operation in one job is fixed, so operation number can preliminarily classify training data.

Process time: The process time of each operation on corresponding machine. The processing time has a certain relationship with processing order of job.

Remaining process time: The remaining processing time after job completes current operation, it can reflect completion degree and completion urgency of job to a certain extent.

The proportion of current job’s processing time in total process time of all jobs: Total process time of current job / sum of total process time of all jobs. It can represent the grade of current job’s total process time is high, medium, or low among all jobs.

The proportion of current operation’s processing time in total process time of the job: Process time of current operation / total process time of the job. It is used to represent the grade of current operation’s process time is high, medium, or low among all operations of this job.

The priority of the previous operation of the job: The priority of the previous operation. In FIFO (First In First Out) and FAM (First Available Machine) rules, the job in the first of scheduling sequence is arranged on available machine earliest. In this way, the jobs that processed earlier in previous operation are more likely to be selected by current machine, so the priority of previous operation has a great influence on priority of current operation. When using the trained network to process job attributes of new jobs, this attribute cannot be obtained directly, so special processing is required. This attribute of new job is marked as 0 in the first stage. Inputting training data of the first stage into trained network can get the priority of job in the first stage. For the sake of simplification, this attribute in subsequent stages is marked as the priority of the first stage.

5.1.4 Training neural network

The relationship between job attributes and its priority is complex, so this paper proposed a convolution two-dimensional transformation (CTDT) based on Cartesian product to process job attributes data[12]. Using this transformation, one-dimensional feature data can be transformed into two-dimensional feature data, which are used as the input of CNN. The two one-dimensional vectors used in transformation are related to job attributes, which are defined as follows:

E_{i} = [P_{i, 1}, P_{i, 2}, . . ., P_{i, n}]

(10)

In Equation (10), P_i,n is the proportion of total processing time of Job_i to Job_n, which are represented Equation (11)

P_{i, n} = \frac{\sum_{j = 1}^{m} T_{i, j}}{\sum_{j = 1}^{m} T_{n, j}}, i = 1, 2, 3, . . ., n

(11)

F_{i, j} = [f_{ij, 1}, f_{ij, 2}, f_{ij, 3}, f_{ij, 4}, f_{ij, 5}, f_{ij, 6}]

(12)

In Equation (12), f_ij,1 ∼ f_ij,6 are six job attributes mentioned in the previous section. The specific calculation formula is shown as Table 2.

Table 2

Job attributes in one-dimensional vector

Attribute	Description	Formula
f _ij,1	Operation number	j
f _ij,2	Process time	T _i,j
f _ij,3	Remaining process time	$\sum_{l = j + 1}^{m} T_{i, l}$
f _ij,4	Process time of job i / all jobs in the j - th operation	$\frac{T_{i, j}}{\sum_{i = 1}^{n} T_{i, j}}$
f _ij,5	Process time of operation j /all operations in job i	$\frac{T_{i, j}}{\sum_{j = 1}^{m} T_{i, j}}$
f _ij,6	previous operation priority	r _i,j-1

Cartesian product operation can combine linear characteristics of data to convert it from one dimension to two dimensions, can excavate more comprehensive and deeper information in convolution operation. The conversion in this article described as Equation (13).

D_{α_{1}, α_{2}}^{2 d} = F (α_{1}, α_{2}) = sigmoid (α_{1}, α_{2})

(13)

α_{1} \times α_{2} = {x \cdot y | x \in α_{1}, y \in α_{2}}

(14)

sigmoid (α) = \frac{1}{1 + e^{- α}}

(15)

In Equations (13) and (14), α₁ and α₂ are one-dimensional feature data, × is the sign of Cartesian product operation, mathematical operation is in Equation (14). After Cartesian product, the result is processed by activation function, which is shown in Equation (15). The sigmoid function can convert data between 0 and 1, and convert some very large or very small values into two endpoints of 0 and 1, so as to avoid some extreme outlying value causing over-fitting in the subsequent network. In this paper, α₁ = P_i, α₂ = F_i,j.

The structure of CNN is shown in Fig. 6. At the beginning, convolution layer uses a 5 * 2convolution kernel to preliminarily mine two-dimensional features. The output of convolutional layer is nonlinearly calculated through excitation function Relu. Then the feature data is compressed by maxpooling layer to extract main features and simplify complexity of network computational. In fully connected layer, two-dimensional features are transformed into one-dimensional form. Finally, through softmax layer, the data is converted into output, and the number of output neurons is the number of priority. A trained network is equivalent to a complex function structure that can reflect the relationship between input and output. When new job attributes are input, the network can quickly get corresponding output, that is, the priority of this new job.

Fig. 6

Structure of deep convolution neural network.

5.2 Online scheduling operation

The online scheduling part solves the scheduling problem of new jobs in workshop, the specific framework is shown in Fig. 7. In online scheduling part, when a new set of jobs arrives, six attributes of new jobs are extracted, then put them into the trained network, the output is their priorities. Arrange new jobs according to their priorities to get an initial scheduling sequence. However, the different arrangement of jobs within the same priority lead to different scheduling solutions. Additionally, in tons of training scheduling data, the same job in different sequences may have different positions, resulting in its priority is not unique, which bring about some errors in network. These problems mean that initial scheduling sequence cannot be directly used for production. This paper designs a neighborhood search algorithm (NSA), starting from initial solution, after simple iterations, the final satisfactory solution is obtained for actual production.

Fig. 7

Framework of online scheduling.

The NSA uses greedy strategy, and (S, F, f) is used to represent this combinatorial optimization problem. S represents space of all solutions, F is the evaluation function, f is neighborhood search function. In neighborhood of initial solution s, a neighborhood solution s’ is generated according to neighborhood search function f. If the result F(s’) is better than F(s), replace s=s’, then starts a new round of neighborhood search, repeat above steps until iteration termination condition is reached. The neighborhood search function f processes the jobs in the same priority, and sets a certain mutation probability to operate jobs with different priorities, that can make neighborhood solution jump to a larger range without departing from initial solution, which can find a better solution and improve search efficiency. The specific process of NSA is as follows:

6 Experimental studies and discussions

In order to prove the effectiveness of DEA-CNN-NS, an experimental study is carried out in a non-permutation flow shop problem. This case includes 5 processing stages and 11 jobs. The processing sequence of jobs are the same.

6.1 Experimental design

The experiment obtains training dataset by DEA, then obtains job attributes and priorities as input and output labels for CNN training, and finally uses NSA to optimize scheduling solution. The specific implementation steps and parameter settings are as follows:

Step 1: Run DEA for many times, retain excellent scheduling sequence in each run, then use KM-DS to get priority division method. In this 11 * 5 flow shop case, at each stage, count the number of times that the job appears in each position, each job will get an array {c₁, c₂, c₃, ·· · , c₁₁ }. So each stage will get an 11 * 11 matrix, each row represents number of occurrences of the job in each position. Table 3 shows statistical results of one stage. K-means algorithm clusters each row into two categories. For the first row, the clustering results are (35, 42, 47, 36, 37) and (9, 24, 26, 19, 14, 9), the smaller category is where this job often appears, and length of this category is recorded as the number of positions within a priority, that is, L_Job1 = 5. Similarly, L_Job2 = 4, L_Job3 = 4. Finally get an array {L_Job1, L_Job2, … , L_Jobn } from this matrix. Doing the same operation for 5 stages to get 55 numbers, perform frequency statistics on 55 numbers, the results are shown in Table 4. According to experimental results, every four positions divide into one priority is the most reasonable.

Table 3
Statistical results of one processing stages

Position 1 2 3 4 5 6 7 8 9 10 11

Job1 9 24 26 35 42 47 36 37 19 14 9

Job2 5 6 6 11 23 26 17 50 65 45 44

Job3 57 60 55 35 20 28 16 11 9 3 4

Job4 11 11 22 15 45 51 41 32 24 23 23

Job5 59 48 50 48 29 14 22 14 3 7 4

Job6 3 1 4 9 12 17 36 34 29 70 83

Job7 16 13 15 24 34 19 33 43 56 23 22

Job8 63 72 52 41 28 18 9 3 6 3 3

Job9 17 10 22 27 38 35 43 32 29 23 22

Job10 1 1 3 4 7 21 28 26 49 78 80

Job11 57 52 43 49 20 22 17 16 9 9 4

Position	1	2	3	4	5	6	7	8	9	10	11
Job1	9	24	26	35	42	47	36	37	19	14	9
Job2	5	6	6	11	23	26	17	50	65	45	44
Job3	57	60	55	35	20	28	16	11	9	3	4
Job4	11	11	22	15	45	51	41	32	24	23	23
Job5	59	48	50	48	29	14	22	14	3	7	4
Job6	3	1	4	9	12	17	36	34	29	70	83
Job7	16	13	15	24	34	19	33	43	56	23	22
Job8	63	72	52	41	28	18	9	3	6	3	3
Job9	17	10	22	27	38	35	43	32	29	23	22
Job10	1	1	3	4	7	21	28	26	49	78	80
Job11	57	52	43	49	20	22	17	16	9	9	4

Table 4

Statistical results

L _Job	Frequency of occurrence	Frequency occupied (%)
1	0	0
2	5	9.0909
3	18	32.7273
4	26	47.2727
5	6	10.9091

Step 2: According to statistical results of previous step, the first 4 positions are divided into the first priority, the middle 4 positions are the second priority, and the last three positions are the third priority. Then the input and output label data of CNN can be obtained. Figure 8 shows training process of deep convolution network and a partial enlarged view of loss process. Table 5 shows the training results of CNN, reflecting the accuracy of network for each classification and the overall classification accuracy. Values on diagonal indicate the times that network predicts correctly for each class data.

Table 5

Confusion matrix of CNN

Output class		1	2	3
Target class	1	5098	524	290
	2	721	4916	538
	3	213	463	4106
Classification accuracy		84.5%	83.3%	83.2%
Overall accuracy		83.7%

Fig. 8

Training process of network.

There is some error in prediction results. Firstly, due to the non-reproducibility of heuristic algorithm, there are diversities between different scheduling solutions, which lead to the same job may correspond to different priorities in different sequences. Additionally, the selected job attributes are limited, which may not fully reflect hidden information related to processing. These problems bring about errors in network training.

Step 3: For new jobs in this flow shop, extract their job attributes, part of data is shown in Table 6, these data are components of parameter F_i,j. The data related to parameter E_i are shown in Table 7. These job attributes data are converted into vectors and input into trained network, the output of network is corresponding priority, as shown in Table 8. Due to some errors in network, the priority obtained may not be accurate. So the initial scheduling sequence obtained by priority need furtherprocessing.

Table 6

The operation attributes of new jobs

f _ij,1	Job Id	f _ij,2	f _ij,3	f _ij,4	f _ij,5	f _ij,6
1	1	615	1911	0.120564595	0.243467933	0
	2	33	2302	0.00646932	0.014132762	0
	3	902	1659	0.176828073	0.352206169	0
	4	239	1937	0.046853558	0.109834559	0
	5	56	1739	0.01097824	0.031197772	0
⋮	6	487	1691	0.095471476	0.223599633	0
	7	509	1979	0.099784356	0.204581994	0
	...	...	...	...	...	...
5	8	420	0	0.06839277	0.342577488	2
	9	456	0	0.074255007	0.171686747	2
	10	892	0	0.145253216	0.291312867	3
	11	152	0	0.024751669	0.068100358	3

Table 7

The ratio of the processing time between jobs

E ₁	1	0.47100	0.51319	0.55317	0.46674	0.54629	0.44704	0.70595	0.53665	0.47007	0.38406
		87370	77498	16417	53758	20313	10855	23809	15837	53071	73575
E ₂	2.12310	1	1.08957	1.17444	0.99094	1.15983	0.94911	1.49880	1.13936	0.99801	0.81541
	28667		16140	02985	84454	41777	42103	95238	65158	82322	45077
E ₃	1.94856	0.91779	1	1.07789	0.90948	1.06448	0.87108	1.37559	1.04570	0.91597	0.74838
	66104	18983		17910	44549	64117	93328	52380	13574	30479	08290
...	...	...	...	...	...	...	...	...	...	...	...
E ₁₀	2.12731	1.00198	1.09173	1.17677	0.99291	1.16213	0.95099	1.50178	1.14162	1	0.81703
	87183	57029	51795	23880	61747	72639	88692	57142	89592		36787
E ₁₁	2.60370	1.22637	1.33621	1.44029	1.21526	1.42238	1.16396	1.83809	1.39728	1.22393	1
	99494	01350	80874	85074	95789	59972	53222	52380	50678	97542

Table 8

Priority of neural network prediction

Operation Id		1
Job Id	1	2	3	4	5	6	7	8	9	10	11
Priority	2	1	3	2	1	1	2	1	3	1	3
Operation Id		2
Job Id	1	2	3	4	5	6	7	8	9	10	11
Priority	2	1	3	2	1	1	2	1	3	2	3
Operation Id		3
Job Id	1	2	3	4	5	6	7	8	9	10	11
Priority	2	1	3	2	1	1	2	1	3	2	3
Operation Id		4
Job Id	1	2	3	4	5	6	7	8	9	10	11
Priority	3	1	2	2	1	1	3	1	3	3	2
Operation Id		5
Job Id	1	2	3	4	5	6	7	8	9	10	11
Priority	1	1	2	2	1	3	2	2	3	1	3

Step 4: Starting from initial sequence, the neighborhood search is carried out. In each iteration, two priorities are selected, as shown in Fig. 9, P₁, P₃ are selected, the jobs within the two priorities are rearranged to obtain a neighborhood solution. The mutation is shown in Fig. 10, P₁, P₃ are selected, the last two jobs of P₁ are exchanged with the first two jobs in P₃. This operation avoids solution falling into local optimum.

Fig. 9

Job exchange in the same priority.

Fig. 10

Job exchange in different priority.

6.2 Numerical results and comparisons

In order to compare ability of different neural networks in mining job attributes, this paper selects CNN, Back Propagation Network (BP), and Long Short-Term Memory Network (LSTM) for comparison, and uses the same data for training. The comparison of accuracy in training process of three networks is shown in Fig. 11. It can be seen that BP has achieved high accuracy with little train, premature convergence may lead to poor generalization ability of network model, while LSTM has weak ability to mine job attributes, the training result is poor. After training, use the same data to test classification ability of three network models, the forecast results and confusion matrices are shown in Figs. 12–14. Although BP network performs well in training process, it may be because the selected training data are relatively typical and sample, so when it faces new data, its prediction ability is poor. LSTM excels in time series prediction, but is not ideal for mining prioritier. CNN performs well in mining deep relationship of data. Compared with experimental results, CNN is more suitable for mining job attributes data.

Fig. 11

Training process of three network.

Fig. 12

Forecast result and confusion matrix bar graph of CNN.

Fig. 13

Forecast result and confusion matrix bar graph of BP.

Fig. 14

Forecast result and confusion matrix bar graph of LSTM.

In order to verify the superiority of DEA-CNN-NS in this paper, a comparison experiment was performed between DEA, GA, Gray Wolf Algorithm(GWA) and DEA-CNN-NS.

The number of individuals in population is set to 100. Figure 15 shows comparison of four algorithms’ convergence at 150 generations. Then compare performance of four algorithms at 150 generations and 500 generations in Table 9. Run each algorithm 5 times, take medium value from 5 results, the CPU time and makespan are recorded in Table 9. In addition, three network and heuristic algorithms were applied to solve several cases of different scales, the experimental results are recorded in Table 10.

Fig. 15

Compare of four algorithms when iterating 150 times.

Table 9

Experimental results of different algorithms

Indicator	Generat-ion	GA	DEA	GWA	DEA-CNN-NS
Makespan	150	9670	11548	9237	8836
	500	9035	9190	8901	8724
CPU time	150	46.797 s	63.588 s	28.884s	1.305s
	500	153.638 s	224.545 s	93.451s	2.845s

Table 10

Experimental results of different algorithms

	Indicator	DEA-CNN-NS	DEA-BP-NS	DEA-LSTM-NS	DEA-CNN	GA	DEA	GWA
Case 1 (10*10)	Makespan	1152	1367	1304	1405	1238	1209	1196
	CPU time	2.83	2.56	3.03	1.45	48.67	58.94	31.88
Case2 (20*10)	Makespan	1422	1683	1671	1762	1286	1513	1522
	CPU time	4.42	4.51	4.88	2.33	83.21	95.40	79.63
Case3 (20*15)	Makespan	739	892	933	1037	802	737	786
	CPU time	7.32	7.54	8.23	3.69	125.71	108.58	116.32
Case4 (30*20)	Makespan	1868	2534	2461	2642	2031	1957	1924
	CPU time	11.52	11.38	12.21	5.68	141.82	136.14	130.27
Average	Makespan	1295.25	1619	1592.25	1711.5	1339.25	1354	1357
	CPU time	6.5225	6.4975	7.0875	3.1125	99.8525	99.765	89.525
Makespan rank		1	6	5	7	2	3	4
CPU time rank		3	2	4	1	7	6	5

The performance of these algorithms can be described as follows: (1)

Meta heuristic algorithm takes long time to solve large-scale problems. With number of iterations increases, the optimal solution does not improve much, but the time is greatly increased. The algorithm converges too early and the global search ability is poor in later stage.

(2)

DEA-CNN-NS needs a certain amount of time in offline training part, but the trained model can be applied to similar new jobs in the same NPFS, so it can quickly schedule and get excellent scheduling sequence in short time.

(3)

In general, DEA-CNN-NS is easier to find excellent solutions because of its better initial scheduling sequence, and because the neighborhood search function runs faster, its time cost will not increase greatly with the increase of iterations. The superiority of this method is more obvious when dealing with larger scale problems.

It can be seen that the overall performance of DEA-CNN-NS is better, which provides a feasible solution for scheduling problem of similar type jobs in NPFSSP.

7 Conclusion

The jobs processed in the same workshop often have certain similarities, and the historical data in workshop contains many job information related to scheduling results. Mining the potential information for new scheduling problem can greatly improve production efficiency. Therefore, aiming at non-permutation flow shop scheduling problem, a hybrid differential evolution algorithm, deep convolution network and neighborhood search method is proposed. This method takes some time in training part. The trained neural network can greatly improve processing efficiency of similar jobs in this workshop. In addition, DEA, K-means algorithm and neighborhood search algorithm also improve integrity and rationality of this method. Experimental results show that the performance of this method is better than traditional intelligent heuristic algorithm. In addition, there are still some problems. Is there any advantage when the similarity of new jobs is low? What job attributes remain to be mined? Future research will focus on these questions, and will also focus on more complicated scheduling problem, such as hybrid flow shop scheduling problem, distributed job shop scheduling problem, etc.

References

Pan

Q.K.

Wang

J.C.

Duan

J.H.

A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimization, Omega-international Journal of Management Science45 (2014), 42–56. doi: 10.1016/j.omega.2013.12.004.

Wang

J.J.

Wang

A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop, IEEE Transactions on Systems Man Cybernetics-Systems50(5) (2020), 1805–1819. doi: 10.1109/tsmc.2017.2788879.

Rossit

D.A.

Tohmé

Frutos

The non-permutation flow-shop scheduling problem: A literature review, Omega-International Journal of Management Science77 (2018), 143–153.

Benavides

A.J.

Ritt

Fast heuristics for minimizing the makespan in non-permutation flow shops, Computers & Operations Research100 (2018), 230–243. doi: 10.1016/j.cor.2018.07.017.

Zhao

K.D.

Lei

C.J.

Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags, Computers & Industrial Engineering113 (2017), 160–184. doi: 10.1016/j.cie.2017.08.024.

Ying

K.C.

Gupta

J.N.D.

Lin

S.W.

Lee

Z.J.

Permutation and non-permutation schedules for the flowline manufacturing cell with sequence dependent family setups, International Journal of Production Research48(8) (2010), 2169–2184. doi: 10.1080/00207540802534707.

Garey

M.R.

Johnson

D.S.

Sethi

The complexity of flowshop and jobshop scheduling, Math. Oper. Res.1 (1976), 117–129.

Ying

K.C.

Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic, International Journal of Advanced Manufacturing Technology38(3-4) (2008), 348–354.

Y.P.

Zhou

M.C.

Guo

X.W.

Scheduling dual-objective stochastic hybrid flow shop with deteriorating jobs via bi-population evolutionary algorithm, IEEE Transactions on Systems Man Cybernetics-Systems50(12) (2020), 5037–5048. doi: 10.1109/tsmc.2019.2907575.

10.

Koonce

D.A.

Tsai

S.C.

Using data mining to find patterns in genetic algorithm solutions to a job shop schedule, Computers & Industrial Engineering38(3) (2000), 361–374. doi: 10.1016/s0360-8352(00)00050-4.

11.

Tang

X.Y.

Zhao

P.P.

Zhao

G.F.

Zhou

Chen

Q.B.

Virtual network function migration based on dynamic resource requirements prediction, IEEE Access7 (2019), 112348–112362.

12.

Zang

Z.L.

Wang

W.L.

Song

Y.H.

L.Y.

W.K.

Wang

Y.L.

, et al. Hybrid deep neural network scheduler for job-shop problem based on convolution two-dimensional transformation, Computational Intelligence and Neuroscience (2019), 2019. doi: 10.1155/2019/7172842.

13.

Mehravaran

Logendran

Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times, International Journal of Production Economics135(2) (2012), 953–963.

14.

Dhouib

Teghem

Loukil

Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic, Annals of Operations Research267(1-2) (2018), 101–134. doi: 10.1007/s10479-018-2775-5.

15.

Assia

Ikram

E.A.

Barkany

Ahmed Abdellah,

E.B.

Non-permutation flow shop scheduling problems with unavailability constraints to minimize total energy consumption, in: 2019 5th International Conference on Optimization and Applications (ICOA), Kenitra, Morocco (2019), 1–5.

16.

Meng

Q.N.

Solving scheduling problems for a non-permutation assembly flows shop, in: 16th IEEE International Conference on Automation Science and Engineering (CASE) (2020), 508–513.

17.

Gmys

Mezmaz

Melab

Tuyttens

A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem, European Journal of Operational Research284(3) (2020), 814–833. doi: 10.1016/j.ejor.2020.01.039.

18.

Chung

Y.H.

Tong

L.I.

Makespan minimization for m-machine permutation flowshop scheduling problem with learning considerations, International Journal of Advanced Manufacturing Technology56(1-4) (2011), 355–367. doi: 10.1007/s00170-011-3172-2.

19.

Lin

S.W.

Ying

K.C.

Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems, International Journal of Production Research47(5) (2009), 1411–1424.

20.

J.Q.

Sang

H.Y.

Han

Y.Y.

Wang

C.G.

Gao

K.Z.

Efficient multi-objective optimization algorithm for hybrid flow shop scheduling problems with setup energy consumptions, Journal of Cleaner Production181 (2018), 584–598. doi: 10.1016/j.jclepro.2018.02.004.

21.

Wang

Luo

Liu

Yue

X.H.

Permutation flow shop scheduling with batch delivery to multiple customers in supply chains, IEEE Transactions on Systems Man Cybernetics-Systems48(10) (2018), 1826–1837. doi: 10.1109/tsmc.2017.2720178.

22.

X.P.

Jiang

Y.L.

Ruiz

Methods for scheduling problems considering experience, learning, and forgetting effects, IEEE Transactions on Systems Man Cybernetics-Systems48(5) (2018), 743–754.

23.

Xiao

Y.Y.

Yuan

Y.Y.

Zhang

R.Q.

Konak

Non-permutation flow shop scheduling with order acceptance and weighted tardiness, Applied Mathematics and Computation270 (2015), 312–333.

24.

Cui

W.W.

Z.Q.

Zhou

B.H.

Han

X.L.

A hybrid genetic algorithm for non-permutation flow shop scheduling problems with unavailability constraints, International Journal of Computer Integrated Manufacturing29(9) (2016), 944–961. doi: 10.1080/0951192x.2015.1130247.

25.

Nouri

B.V.

Fattahi

Ramezanian

Hybrid firefly-simulated annealing algorithm for the flow shop problem with learning effects and flexible maintenance activities, International Journal of Production Research51(12) (2013), 3501–3515. doi: 10.1080/00207543.2012.750771.

26.

Zheng

Yamashiro

A novel quantum differential evolutionary algorithm for non-permutation flow shop scheduling problems, in: 2010 7th International Conference on Electrical Engineering Computing Science and Automatic Control; Tuxtla Gutierrez, Mexico (2010), 357–362.

27.

Zhang

Shangguan

Kise

A GAbased heuristic algorithm for non-permutation two-machine robotic flow-shop scheduling problem of minimizing total weighted completion time, in: 2010 IEEE International Conference on Industrial Engineering and Engineering Management; Macao, China (2010), 1281–1285.

28.

Ying

K.C.

Lin

S.W.

Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems, International Journal of Advanced Manufacturing Technology33(7-8) (2007), 793–802. doi: 10.1007/s00170-006-0492-8.

29.

Benavides

A.J.

Ritt

Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops, Computers & Operations Research66 (2016), 160–169.

30.

Jun

Lee

Chun

Learning dispatching rules using random forest in flexible job shop scheduling problems,-, International Journal of Production Research57(10) (2019), 3290–3310.

31.

Wang

C.L.

Rong

Weng

Feng

Y.P.

Mining scheduling knowledge for job shop scheduling problem,800-805. Ottawa, CANADA, IFAC-PapersOnLine48(3) (2015), 2015.

32.

Shiue

Y.R.

Lee

K.C.

C.T.

Real-time scheduling for a smart factory using a reinforcement learning approach, Computers & Industrial Engineering125 (2018), 604–614.

33.

Ren

J.F.

C.M.

Yang

Solving flow-shop scheduling problem with a reinforcement learning algorithm that generalizes the value function with neural network, Alexandria Engineering Journal60(3) (2021), 2787–2800. doi: 10.1016/j.aej.2021.01.030.

34.

Liu

R.K.

Piplani

Toro

Deep reinforcement learning for dynamic scheduling of a flexible job shop, International Journal of Production Research60(13) (2022), 4049–4069.

35.

Song

Chen

X.Y.

Q.Q.

Cao

Z.G.

Flexible job-shop scheduling via graph neural network and deep reinforcement learning, IEEE Transactions on Industrial Informatics19(2) (2023), 1600–1610.

36.

Lin

C.C.

Deng

D.J.

Chih

Y.L.

Chiu

H.T.

Smart manufacturing scheduling with edge computing using multiclass deep Q network, IEEE Transactions on Industrial Informatics15(7) (2019), 4276–4284.

37.

Koulamas

Panwalkar

S.S.

New index priority rules for no-wait flow shops, Computers & Industrial Engineering115 (2018), 647–652. doi: 10.1016/j.cie.2017.12.015.

38.

Lin

Gen

Hybrid evolutionary optimisation with learning for production scheduling: state-of-the-art survey on algorithms and applications, International Journal of Production Research56(1-2) (2018), 193–223. doi: 10.1080/00207543.2018.1437288.

n	The number of jobs
m	The number of machines
i	Index of jobs, i = 1, 2, 3, …, n
j	The set of machine, j = 1, 2, 3, …, m
O _i,j	The j-th operation of job i
T _i,j	Processing time of operation O_i,j
m _i,j	The number of machine for O_i,j
ST _i,j	Starting time of operation O_i,j
ET _i,j	Ending time of operation O_i,j
p _i,j,k	Processing time of O_i,j on machine k
x _i,j,k	Equals to 1 if O_i,j is processed on machine k, otherwise 0
r	The processing priority
r _i,j	Priority of the j-th operation of jobi
ST _k,r	The start time of the r-th operation processed on machine k
y _i,j,k,r	Equals to 1 if O_i,j is processed at positionr of machine k, otherwise 0
π	A scheduling sequence
C_max (π)	The makespan of π
Q	A number large enough
c _i	Occurrence number of job in the i-th position of sequence, i = 1, 2, 3, …, n
L _{Job _i}	Length of one priority determined by job i, i = 1, 2, 3, …, n
a	Number of priorities
P _l	Priority l, l = 1, 2, 3, …, a
s _t	Individuals in DEA,t = 1, 2, …, NP
$s_{t}^{λ}$	The λ-th dimensional vector of individual s_t
s_t (g)	Individual s_t in the g-th iteration
v _t	Variation individual
u _t	Cross individual