Multi-objective hybrid job-shop scheduling with multiprocessor task (HJSMT) problem with cooperative effect

Abstract

In order to solve the problem of discrete manufacturing customization and personalized production scheduling, considering the influence of manual labor on processing time, we propose a multi-objective Hybrid Job-shop Scheduling with Multiprocessor Task(HJSMT) problem with cooperative effect model. Based on the actual production, two optimization objectives are set, i. e. minimizing the maximum completion time and the total tardiness. Firstly, considering the situation where workers’ cooperation reduces job processing time, the cooperative effect of workers co-processing is considered by referring to the learning effect curve in the model. Subsequently, we develop an Improved Non-dominated Sorting Genetic Algorithm-II (INSGA-II) to solve the multi-objective HJSMT problem by improving Precedence Operation Crossover (POX) and Multiple Mutations (MM) operations. Finally, the scheduling results and the C values are compared with other algorithms to verify the effectiveness of the algorithm. Simultaneously, the multi-objective HJSMT problem with the cooperative effect is solved by the INSGA-II algorithm, and the experimental results also demonstrate the superior performance of the algorithm.

Keywords

Hybrid job-shop scheduling multiprocessor task cooperative effect multi-objective optimization improved non-dominated sorting genetic algorithm-II

1 Introduction

With all kinds of manufacturing enterprises have been transformed and upgraded to intelligence, informatization and digitalization, this has led to a trend of intelligent scheduling in workshops. Many large, single-piece discrete manufacturing workshops no longer rely on mass production modes and instead produce personalized and customized products. Unlike small batch manufacturing, which cannot use flow line or robot production, discrete enterprise workshops now have features that allow for parallel processing, processing upgrades, multi-processor tasks, etc. In many cases, the job requires at least one (≥1) machine or worker to process simultaneously, making the original single-processor model of workshop scheduling no longer applicable.

The Job-shop Scheduling Problem (JSP) and Flow-shop Scheduling Problem (FSP) are the most common types of shop scheduling problems, which have been extensively researched with respect to machines, time and various objective functions. To better address modern production needs, hybrid scheduling types such as the Flexible Flow-shop Scheduling (FFS), Flexible Job-shop Scheduling (FJS), Flexible Open-shop Scheduling (FOS), Hybrid Flow-shop Scheduling with multiprocessor task (HFSMT) and Hybrid Job-shop Scheduling with Multiprocessor Task (HJSMT) problem have emerged [16]. One of these models, HJSMT problem [22], is a combination of the classical Job Shop Scheduling (JSP) problem and Multiprocessor Task Scheduling (MTS), where several jobs to be processed have several different operations and an operation for a job requires a set of processors instead of a single processor. However, relatively little research has been done on this problem. In their research, Wang et al. addressed the challenge of hybrid scheduling in network parallel computing, where both multi-step and multi-processor tasks are present [21]. To solve this problem, they combined the PSO algorithm with simulated annealing. Similarly, Fan et al. established a hybrid HJSMT problem model and designed a hybrid genetic algorithm for simulation experiments for the workshop production problem in modern steel manufacturing enterprises [17]. Wang et al. proposed and implemented an improved brainstorming algorithm to solve the non-hybrid multi-processor combined production batch scheduling model discussed in the article [23].

In real manufacturing plants, not all operations are done by machines, workers also process or even cooperate in processing. When workers collaborate on a job, the time spent on processing decreases, resulting in a cooperative effect that can reduce workers’ working time, decrease shop floor energy consumption and improve overall efficiency.

Traditional job-shop scheduling problems typically focus on a single optimization objective. However, with increasing market competition, multi-objective optimization studies of job-shop scheduling have become more important over the last decade. Researchers consider objectives such as minimizing maximum completion time, reducing energy consumption, minimizing total tardiness, and managing machine workload. Wang et al. investigated the Flexible Job-shop Scheduling Problem (FJSP) model to reduce energy consumption [19], while Wang et al. considered completion time, total energy consumption, total tardiness, and total machine load as objectives in their FJSP model [23]. Li et al. included machine workload in addition to total work time in the FJSP model [12], and Amiri et al. considered the maximum completion time, number of delayed jobs, and total flow time for the automated flexible job-shop [9]. To address these problems, researchers such as Deb et al. [14], Coello et al. [4], and Zitzler et al. [34] proposed classical solution algorithms like NSGA-II, MOPSO, and SPEA2. Moreover, many scholars have used improved intelligent algorithms to solve the job-shop scheduling problem. For instance, Erfan et al. used a hybrid NSGA-II and local search algorithm to solve the dynamic facility layout and job-shop scheduling problems, simultaneously [8]. Moslehi and Mahnam developed the MOPSO+LS algorithm by adding a local search algorithm to PSO to solve the multi-objective FJSP model [11]. Sun used the grey wolf optimization algorithm along with a non-dominated ranking genetic algorithm to solve a FJSP problem with three objectives [29]. Leo et al. proposed three multi-objective scatter search hybrid algorithms to solve the multi-objective JSP problem [18]. Xu et al. used the flower pollination algorithm to solve a multi-objective model for flexible job-shop scheduling that used triangular fuzzy number representation [27]. Aghajani and Fouladi proposed a bi-objective mathematical model of the FJSP problem and used an improved NSGA-II to find the Pareto optimal solution [3]. Additionally, An et al. designed two modified precedence operation crossover (named MPOX1 and MPOX2) strategies to inherit and maintain more information from the parent to the child in algorithm to deal with integrated optimization of real-time order acceptance and FJSP rescheduling with multi-level imperfect maintenance constraints [30], and designed an enhanced precedence operation crossover (EPOX) to deal with joint optimization of preventive maintenance and FJSP rescheduling with processing speed selection [31].

The current shift and upgrade of production methods in discrete manufacturing companies favor the use of the HJSMT problem model, which is best suited for the new discrete manufacturing shop. The cooperative effect needs to be considered when simulating actual production as it can reduce workers’ working time, decrease job-shop energy consumption, and improve overall efficiency. Additionally, with the increase of the production-to-order model, delivery time requirements are increasing, and companies need to focus on production goals beyond minimizing maximum completion time. This paper innovates on the research problem by considering the influence of worker cooperative effect on scheduling production, taking the HJSMT problem with cooperative effect as the research object, and minimizing both total tardiness and maximum completion time as the scheduling objectives.

The paper is organized as follows. In the next section, the multi-objective HJSMT problem and the cooperative effect are defined, and a mathematical model is constructed. In Section 3, a suitable optimization algorithm based on the original classical algorithm NSGA-II is designed by improving operations such as POX crossover and multi-round variation. In Section 4, simulation experiments compare the proposed algorithm to verify its effectiveness and analyze the impact of the cooperative effect at different levels of cooperation ratio (70%, 80%, and 90%). Finally, conclusions are given in Section 5.

2 Model construction of multi-objective HJSMT problem with cooperative effect

2.1 Multi-objective HJSMT problem description

According to the HJSMT problem characteristics, it’s defined as: processing a set of jobs J ={ J₁, J₂, …, J_n } on m processors with q_i operations J_i ={ O_ij|j = 1, 2, …, q_i } for each job that must be processed in a certain sequence and with fixed processing times, and each operation requires processing by multiple (≥1) designated processors simultaneously. This paper aims to develop a suitable scheduling plan that adheres strictly to the process route and processing time of each operation.

The problem has several conditions:

Only one operation can be processed at a time on a processor;

Each processor is unique and cannot be mixed;

No sequential order exists between operations of different jobs;

The process cannot be interrupted once it has started;

There are no unexpected situations like raw material shortages, orders insertion or machine damage.

This paper sets the objectives of minimizing maximum completion time and minimizing total tardiness. In practical applications, objectives can be tailored to suit the importance of orders, machine loads, delivery requirements, etc.

2.2 Cooperative effect

During the actual production process, repeated cooperation among two or more workers can lead to a reduction in actual working time due to improvements in coordination and cooperation proficiency. This phenomenon is defined as the cooperative effect in this paper. In HJSMT problem, each operation of the job is not necessarily processed by one processor; it may be processed by several processors simultaneously. In this case, the processor processing can be considered equivalent to worker processing.

In this scenario, assume that there is an original processing te T. The cooperative effect hypothesis suggests that when the same worker combinations reappear for combined processing, the cooperation proficiency increases, leading to increased processing efficiency and a reduction in actual processing time below T. For example, as shown in Table 1, the worker combinations required in the first step of job J3 are M1 and M3, and the same worker combination appears again in step 2 of job J2. As a result of this repetition, the actual processing time will be smaller than the original processing time.

Table 1
Examples of cooperative effect in HJSMT problem

Step 1 Step 2 Step 3

J₁ M₁, M₂ M₂, M₃ M₁

J₂ M₂ M₁, M₃ M₁, M₂, M₃

J₃ M₁, M₃ M₁, M₂, M₃ M₁, M₂

	Step 1	Step 2	Step 3
J₁	M₁, M₂	M₂, M₃	M₁
J₂	M₂	M₁, M₃	M₁, M₂, M₃
J₃	M₁, M₃	M₁, M₂, M₃	M₁, M₂

Previous scholars have conducted limited research on the cooperative effect. However, some scholars have studied the learning effect in job-shop scheduling problems, which implies that workers become more familiar with equipment or operations through continuous work, leading to an increase in proficiency and a reduction in processing time [1 , 26]. Due to its similarity with the cooperative effect, this paper refers to the position-based learning effect curve [7, 10] and uses it to express the actual processing time while considering the cooperative effect in the Equation (1): $y_{k} = y_{1} * k^{α}$ (1)

Here, y_k represents the original processing time of the job processed at the k-th position, while y₁ represents the processing time of the job processed at the first position, $k \in [1, \sum_{i = 1}^{n} q_{i}] \cap k \in N$ . The cooperation factor is denoted by α, α = log ₂ (l) ≤ 0 and the cooperation ratio is represented by l. The cooperation ratio refers to the effect of collaboration among workers after repeated work, with lower values indicating less working time after collaboration. Equations (2)-(4) describe the derivation of the cooperation factor. $y_{2 k} = y_{k} * l$ (2) $l = \frac{y_{2 k}}{y_{k}} = \frac{y_{1} * {(2 k)}^{α}}{y_{1} * k^{α}} = 2^{α}$ (3) $α = {log}_{2} (l)$ (4)

In summary, this paper considers the cooperative effect in HJSMT problem processing, resulting ian actual processing time of t_q = y_q × r^α, y_q set as the original processing time of operation q; r is the number of repeated combinations of workers. For instance, in Table 1, for step 1 of job J3, the same combination of workers is required as for step 2 of job J2. Therefore, if step 1 of J3 is completed first, when step 2 of J2 is processed again, it becomes the second occurrence of the same worker combination, which leads to a value of r = 2.

2.3 Multi-objective HJSMT problem model construction with cooperative effect

Referring to the literature [13], the symbols in the model are defined as shown in Table 2.

Table 2
Symbol definition

Symbols Definition

S Collection of all jobs S ={ J_i|i = 1, 2, …, n }

I The set of all operations, I ={ O_ij|i = 1, 2, …, n ; j = 1, 2, …, q_i }, q_i: Total number of steps required to complete the job J_i

C _i Completion time of the job J_i

D _i Delivery time of job J_i

σ “Start dummy operation”, which starts before all formal operations and sets the processing time to 0

μ “End dummy operation”, which starts after all formal operations are finished, sets the processing time to 0

x _q Start time of operation q

m _q Set of processors required for operation q

y _q Operation q original processing time

t _q Operation q Actual processing time

Symbols	Definition
S	Collection of all jobs S ={ J_i\|i = 1, 2, …, n }
I	The set of all operations, I ={ O_ij\|i = 1, 2, …, n ; j = 1, 2, …, q_i }, q_i: Total number of steps required to complete the job J_i
C _i	Completion time of the job J_i
D _i	Delivery time of job J_i
σ	“Start dummy operation”, which starts before all formal operations and sets the processing time to 0
μ	“End dummy operation”, which starts after all formal operations are finished, sets the processing time to 0
x _q	Start time of operation q
m _q	Set of processors required for operation q
y _q	Operation q original processing time
t _q	Operation q Actual processing time

Based on the previous equation (4), when l takes the values of 90%, 80%, and 70%, the corresponding values α are -0.15, -0.32, and -0.51, respectively. For any task J_i ∈ S in the set S consisting of q_i operations, there is J_i = {O_ij|j = 1, 2, …, q_i} and J_i ∈ I. Moreover, for the start and finish dummy operations, m_σ = m_μ = ∅ , t_σ = t_μ = 0, x_μ denotes the maximum completion time. Additionally, the notation A = {{a, b} : a, b ∈ J, anda < b, {a, b} ∈ A} means terations a and b belong to the same job and that operation a must be finished before operation b begins. The notation B = {{a, b} : a ∈ J, b ∈ J′withJ, J′ ∈ S, J ≠ J′ and C_a ∩ C_b ≠ ∅} , {a, b} ∈ B signies that operations a and b belong to different jobs but require at least one common processor for processing.

The mathematical model that addresses the multi-objective HJSMT problem is defined below.

Objective function: ${\begin{matrix} f_{1} = \min x_{μ} \\ f_{2} = \min (\sum_{i = 1}^{q_{i}} \max {C_{i} - D_{i}, 0}) \end{matrix}$ (5)

Constraints: $x_{b} - x_{a} \geq t_{a}, for all {a, b} \in A$ (6) $x_{b} - x_{a} \geq t_{a} \cup x_{a} - x_{b} \geq t_{b}, for all {a, b} \in B$ (7) $x_{a} - x_{σ} \geq 0 \cup x_{μ} - x_{a} \geq t_{a}, for all a \in I$ (8)

In Equation (5), the function f1 represents the objective ominimizing the maximum completion time, while f2 represents the objective of minimizing the total tardiness. Equation (6) represents the operation sequence constraint; Equation (7) corresponds to the processor resource constraint; and Equation (8) denotes the “start and finish dummy operation” constraint.

3 Improved multi-objective genetic algorithm (INSGA-II) design

Based on the characteristics of multi-objective job-shop scheduling problem, scholars have proposed many classical algorithms to solve it, among which the fast non-dominated sorting genetic algorithm NSGA-II [14] is widely used. However, this algorithm cannot be directly applied to the HJSMT problem in this paper, and has defects such as easily falling into local optimality. Therefore, this paper improved the NSGA-II algorithm to retain its original advantages and achieve better performance in solving the problem at hand.

3.1 Code mechanism

Coding is the key to the success of particle swarm algorithm optimization. This paper utilizes a commonly used operation-based coding method for particle swarm algorithm optimization. The encoded particle represents a scheduling, where the number of operations for job i is denoted by |J_i|. The particle is a vector of length equal to the total number of operations, that is $\sum_{i = 1}^{n} q_{i}$ . Positive integers in the vector represent artifacts, and the operation sequence number of each job is represented by the number of occurrences of the artifact number by Algorithm 1. For example, if there are three different jobs with three operations each, a particle is represented as (2, 3, 1, 3, 1, 1, 3, 2, 2), where the first 2 represents the first operation of the second job, the first 3 represents the first operation of the third job, and so on. Figure 1 shows that using O_nm to denote the mth operation of the nth job, the particle corresponds to the operation order (O₁₁, O₃₁, O₂₁, O₃₂, O₁₂, O₁₃, O₃₃, O₂₂, O₂₃).

Fig. 1

Example of encode and decode.

Algorithm 1. Particle coding mechanism

Input: job i

Output: particle p

1: Generating a set p, p

= {p_{r} = 0 | r = 1, 2, \dots, \sum_{i = 1}^{n} q_{i}}

, let i = 1;

2: Generating random number k,

k \in [0, \sum_{i = 1}^{n} q_{i} - 1]

;

3: for

j = 0 \to j = \sum_{i = 1}^{n} q_{i}

If p[k] = 0, then p [k] = i and set i : = i + 1;

end for;

4: if p_r ⊆ p ∩ p_r ≠ 0, stop and output p; otherwise go back to step 2.

3.2 Improved Pority Operation Crossover (IPOX) Strategy

This paper uses the Improved Priority Operation Crossover (IPOX) algorithm [5] depicted in Figs. 2 and 3. A1 and A2 represent the two particles tbe crossed, while B1 and B2 represent the resulting new particles. The algorithm proceeds as follows and runs as Algorithm 2:

Fig. 2

Example of IPOX.

Fig. 3

Example of IPOX.

Step 1: Randomly divide the task set S ={ J_i|i = 1, 2, …, n } into two subsets, S1 and S2.

Step 2: Place the elements belonging to S1 in A1 and the elements belonging to S2 in A2 into B1 without changing their positions.

Step 3: Place the element belonging to S2 in A1 and the element belonging to S1 in A2 into B2 without changing their positions.

Step 4: Calculate the adaptation values for B1 and B2 and select the Pareto dominant particles. If they are not dominated by each other, randomly select one of them.

Algorithm 2. IPOX strategy

Input: parent solutions A₁ and A₂

Output: new solutions B₁ and B₂

1: Randomly divide job set S ={ J_i|i = 1, 2, …, n } into two subsets S₁ and S₂. Let k = 1 and a = 1;

2: Check: if A₁ [k] ∈ S₁, then B₁ [a] = A₁ [k] and set a:=a+1, k:=k+1;

3: Check: if A₂ [k] ∈ S₂, then B₁ [a] = A₂ [k] and set a:=a+1, k:=k+1;

4: Check: if A₁ [k] ∈ S₂, then B₂ [a] = A₁ [k] and set a:=a+1, k:=k+1;

5: Check: if A₂ [k] ∈ S₁, then B₂ [a] = A₂ [k] and set a:=a+1, k:=k+1;

6: if

k \leq \sum_{i = 1}^{n} q_{i}

, go back to step 2; otherwise, algorithm stop and output B₁ and B₂.

3.3 Multiple Mutations (MM) operation

This paper implements a swap operation for particle variation, where two random integers within the range of the particle length are generated and the numbers at those positions are exchanged. For instance, if particle p is (2, 1, 3, 1, 3, 1, 1, 2, 3, 2) and the particle length is 9, two random integers in the range [1, 9] are generated. Assuming the random numbers are 2 and 5, the numbers at position 2 are swapped with those asition 5 to generate the new particle (2, 3, 3, 1, 1, 1, 1, 2, 3, 2).

In this paper’s particle update process, particles are not ted according to the mutation probability b instead replaced by mutation 20 times using Multiple Mutations (MM), as shown in Algorithm 3 the initial particle dominates the particle after each mutation, it is not replaced.f the new particle Pareto dominates, it replaces the old one. When they do not dominate eother, one is randomly chosen.

Algorithm 3. Multiple Mutations operation

Input: parent particles p

Output: new particle p’

1: Generating two random numbers k₁ and k₂,

k_{1}, k_{2} \in [1, \sum_{i = 1}^{n} q_{i}]

;

2: Let a = p[k₁ - 1], p’[k₁ - 1]=p[k₂ - 1^], p′ [k₂ - 1]=a;

3: output p’.

3.4 Fast non-dominated sorting

The Pareto finding step of NSGA-II, designed by Deb [14], uses the fast non-dominated sort algorithm. Given a population P and individuals p in the population, the algorithm computes the number of individuals n_p in the population that are dominated by individuals p and the set S_p of individuals in the population dominated by individuals p. The main steps of the algorithm are as follows [6] and are implemented according to Algorithm 4:

Step 1: Save all individuals n_p = 0 in the population in the set F_i;

Step 2: For each individual i in F1, let s_i be the set of individuals dominated by i, iterate through the individuals l in n_l = n_l - 1, and store the individuals l of n_l = 0 in the set N;

Step 3: Record the stratum of individuals in F1 as the first non-dominated stratum, set N as the current set, and repeat the above steps until the population completes the hierarchy.

Algorithm 4. Fast non-dominated sorting

Input: population P and individuals p

Output: all non-dominated stratum F_i

1: for each p ∈ P;

S_p =∅;

n_p = 0;

for each q∈P;

if (p ≺ q) then S_p = S_p∪ { q };

else if (q≺p) then n_p = n_p + 1;

if n_p = 0 then p_rank = 1, and F₁ = F₁∪ { p };

2: i=1;

while F₁≠ ∅;

Q≠ ∅;

for each p ∈ F_i;

for each q∈S_p;

n_q = n_q - 1;

if n_q = 0 then q_rank = i + 1, and Q = Q∪ { q };

i = i + 1, and F_i = Q;

3: output F_i.

3.5 Congestion distance and elite retention strategy

In the case of two objective functions, the crowding dtance can be calculated as the perimeter of the rectangle formed by the adjacent solutions on both sides, with these two solutions as vertices of the diagonal. Figure 4 illustrates tconcept with five points representing t solutions at the same level, where the cwding distance of the third solution iequal to the perimeter of the rectangle with the second and fourth points as diagonals. A larger crowding distance indicates a more dispersed current solution and greater differences between it and surrounding solutions.

Fig. 4

Crowding-distance icon.

Conversely, a smaller crowding distance represents a denser current solution and higher similarity to surrounding solutions. The crowding distance of boundary particles in the same layer is recorded as infinity, and every other particle receives a crowding distance by running Algorithm 5. Following the elite retention strategy, particles with smaller layers are preferred for the next generation. When solutions are in the same layer, those with larger crowding distances should be selected first for better diversity of solutions

Algorithm 5. Crowding distance assignment

Input: solutions L

Output: distance of each solution

1: l = |L|;

2: for each i, set L [i] _distance = 0;

3: for each objective m

L = sort (L, m);

L [1] _distance = L [l] _distance =∞;

for i → 2 to i → (l - 1)

L {[i]}_{distance} = L {[i]}_{distance} + (L [i + 1]) . m - (L [i - 1]) . m / (f_{m}^{\max} - f_{m}^{\min})

;

3.6 The flow of INSGA-II algorithm

The improved multi-objective genetic algorithm can be summarized into the following steps:

Step 1: Set the parameters, including population size (popsize), maximum number of iterations (N), and crossover probability (Pm).

Step 2: Initialize the population using process-based encoding. Generate particles twice the size of the population and select popsize particles as the initial particles to enter the iterative process.

Step 3: Select parent particles. Generate two random positive integers, rand1 and rand2, select particles A and B from these positions, and choose the particle with superior Pareto dominance in A and B to put into the parent particle set. If they are not dominated by each other, choose the particle with a greater crowding distance. If A and B are not dominated by each other and have the same crowding distance, choose one of them randomly to put into the parent particle set.

Step 4: Perform crossover operation on the parent particles. Take out two parent particles at a time and perform the Improved Priority Operation Crossover (IPOX) operation to generate two new particles. Calculate their fitness values and add them to the child particle set.

Step 5: Apply a modified Multiple Mutations (MM) operation to the particles in the child particle set to generate new particles.

Step 6: Merge the parent and child generations and optimize the particle set. Sort the particles using fast non-dominated sorting and select popsize particles for the next iteration using a combination of the crowding distance and the elite retention strategy.

Step 7: Check if the termination condition is met. If it is, output the final selection of Pareto non-dominated solutions. Otherwise, go back to step 3.

4 Experimental simulation and result analysis

4.1 Experimental simulation of INSGA-II algorithm

In this paper, the delivery time is determined based on the standard problem of job-shop scheduling proposed by scholars [20 , 32]. For a problem with 10 jobs, the processing times of the 2nd and 3rd jobs are added together,nd their sum is multiplied by 1.5 to set their delivery times. The delivery time for the 10th job is set as the sum of its processing time, while t delivery time for the remaining jobs is set aice the sum of their corresponding processing time. For a problem with 5 jobs, the sum of the processing times of all jobs is defined as the standard delivery times. The delivery time for the 2nd job is set at 1.5 times the standard time, the delivery time for the 5th job is set at 1 time the standard time, and the delivery times for the remaining jobs is set at 2 times the standard times.

Since there are no common standard instances for HJSMT problem, we generate instances for problems with 10 jobs each having 5 operations (10-Job problem) and problems with 5 jobs each having 5 operations (5-Job problem) [21]. Specific instances are shown in Tables 3 and 4.

Table 3
Instance of 5-Job problem

Job Operation 1 Operation 2 Operation 3 Operation 4 Operation 5

J₁ M₆, M₂₁ (68) M₄, M₉, M_10, M₁₁, M₁₇ (96) M₆, M₉, M₁₂, M₂₂ (53) M₁, M₁₃, M₁₄, M₁₆, M₂₁ (32) M₃, M₁₁, M₁₈, M₂₀, M₂₂ (64)

J₂ M₃, M₁₄ (99) M₁, M₂, M_5, M₇, M₁₇ (75) M₁ (76) M₁₀ (60) M₃, M₁₉ (83)

J₃ M₁, M₉, M₂₀, M₂₅ (41) M₁₀, M₁₁ (67) M₄, M₁₅, M₂₁ (3) M₁₄, M₁₆, M₂₁ (99) M₇ (15)

J₄ M₁₀, M₁₂, M₂₀ (82) M₁₄, M₂₂ (65) M₉, M₁₅, M₂₁ (26) M₃ (99) M₂ (10)

J₅ M₈, M₁₅ (82) M₁₈, M₂₅ (4) M₃, M₁₀, M₁₆ (90) M₁₀, M₁₁, M₁₄, M₁₈, M₂₂ (74) M₅, M₁₆, M₁₇, M₂₅ (76)

Job	Operation 1	Operation 2	Operation 3	Operation 4	Operation 5
J₁	M₆, M₂₁ (68)	M₄, M₉, M_10, M₁₁, M₁₇ (96)	M₆, M₉, M₁₂, M₂₂ (53)	M₁, M₁₃, M₁₄, M₁₆, M₂₁ (32)	M₃, M₁₁, M₁₈, M₂₀, M₂₂ (64)
J₂	M₃, M₁₄ (99)	M₁, M₂, M_5, M₇, M₁₇ (75)	M₁ (76)	M₁₀ (60)	M₃, M₁₉ (83)
J₃	M₁, M₉, M₂₀, M₂₅ (41)	M₁₀, M₁₁ (67)	M₄, M₁₅, M₂₁ (3)	M₁₄, M₁₆, M₂₁ (99)	M₇ (15)
J₄	M₁₀, M₁₂, M₂₀ (82)	M₁₄, M₂₂ (65)	M₉, M₁₅, M₂₁ (26)	M₃ (99)	M₂ (10)
J₅	M₈, M₁₅ (82)	M₁₈, M₂₅ (4)	M₃, M₁₀, M₁₆ (90)	M₁₀, M₁₁, M₁₄, M₁₈, M₂₂ (74)	M₅, M₁₆, M₁₇, M₂₅ (76)

Note: In the case of operation 1 of job J1, M6, M21 (68) represents the processor (worker) that requires numbers 6 and 21 and takes time 68.

Table 4

Instance of 10-Job problem

Job	Operation 1	Operation 2	Operation 3	Operation 4	Operation 5
J₁	M₁, M₂ (40)	M₁, M₇, M₁₀, M₁₉, M₂₃ (17)	M₅, M₇, M₈, M₂₁, M₂₅ (44)	M₅, M₁₃, M₂₅ (70)	M₁, M₁₅ (19)
J₂	M₁₉ (29)	M₂₀ (8)	M₂, M₂₀, M₂₄ (93)	M₃, M₅ (14)	M₆, M₈, M₁₂, M₂₃ (84)
J₃	M₆, M₈, M₁₀, M₁₅, M₁₉ (26)	M₄, M₇, M₉, M₁₈, M₂₀ (96)	M₁₀, M₁₁ (11)	M₁₈ (70)	M₁₂ (50)
J₄	M₇, M₉, M₁₅, M₁₆, M₂₁ (72)	M₆ (70)	M₁₀, M₁₉, M₂₄, M₂₅ (64)	M₂ (93)	M₇, M₁₃, M₁₄ (68)
J₅	M₁₅ (68)	M₁₁ (62)	M₁₇ (23)	M₆, M₈, M₂₅ (19)	M₄, M₂₀, M₂₁, M₂₃ (58)
J₆	M₁₂ (87)	M₂, M₇, M₁₅ (47)	M₁₁, M₁₄ (22)	M₁₉ (56)	M₁₁, M₁₈, M₂₁ (8)
J₇	M₁, M₂, M₅, M₁₁, M₁₄ (53)	M₁₈, M₂₄ (24)	M₈, M₁₂, M₁₃, M₁₈, M₂₃ (9)	M₁₂ (78)	M₁₁, M₁₂, M₁₆ (79)
J₈	M₉, M₂₄ (38)	M₁₅, M₂₅ (97)	M₁₉ (32)	M₈, M₁₆, M₁₉, M₂₅ (77)	M₁₀, M₁₃, M₁₉, M₂₀, M₂₅ (23)
J₉	M₁, M₁₃, M₁₉ (53)	M₁₅, M₂₄ (18)	M₆ (83)	M₄, M₂₀ (76)	M₃, M₆, M₁₀, M₂₅ (44)
J₁₀	M₁, M₆, M₁₁, M₁₂, M₁₈ (80)	M₄ (24)	M₇, M₁₆, M₂₀ (27)	M₂₁ (69)	M₂, M₃, M₁₀, M₁₁, M₂₀ (17)

As it is not possible to measure the performance of multi-objective algorithms solely in terms of optimal solutions and operation speed, the metric C [28] is used to evaluate the comparison algorithms. The set of non-inferior solutions obtained by any two algorithms are denoted as X and Y. C (X, Y) represents the ratio of the number of particles in X that has at least one solution dominating Y to the sum of the number of particles in Y, i.e. $C (X, Y) = \frac{| {y \in Y; \exists x \in X : x ≺ y} |}{| Y |}$ (9)

C (X, Y) = 1 shows that the set X always has particles that are better than any of the particles in the set Y; if C (X, Y) = C (Y, X) = 0, then the sets X, Y are not dominated by each other.

In this paper, using Windows10 operating system, CPU i7-8550U, processor frequency 1.80GHz and 8G memory, and Java language (Eclipse 4.21.0) to implement algorithm programming, compare the INSGA-II algorithm with both the NSGA-II algorithm and the IMOPSO algorithm [33] in solving 5-Job and 10-Job optimization problems. Each algorithm is run 20 times with separately and randomly, and the solutions produced by each run are recorded for comparison. The final fitness values of each algorithm are also compared.

The IMOPSO algorithm is configured with 20 external populations, 100 internal populations, and 200 iterations. Both the NSGA-II algorithm and the INSGA-II algorithm are set with a variation probability of 0.4, a crossover probability of 0.9, 100 populations, and 200 iterations.

For the 5-Job problem, as shown in Table 5, the NSGA-II algorithm obtains five sets of fitness values, while both the IMOPSO and INSGA-II algorithms obtains only one set of fitness values each, which are the same. As shown in Table 6, C (IN, N) is equal to 1, indicating that the solution sets obtained by INSGA-II dominates the solution sets obtained by NSGA-II. The rest of the C values are 0. Therefore, the solution set obtained by IMOPSO and INSGA-II do not dominate each other, and both algorithms are capable of generating better solutions. Additionally, the INSGA-II algorithm generates a larger number of scheduling solutions compared to the IMOPSO algorithm. The grant chart of the best solution for instance 5-job obtained by INSGA-II is shown in Fig. 5.

Fig. 5

The grant chart of the best solution for instance 5-job obtained by INSGA-II.

Table 5

5-Job problem Comparison results of fitness

Algorithm	Adaptation value		Number of
	f1	f2	different scheduling solutions
IMOPSO	584	25	13
NSGA-II	584	331	20+
	588	238	20+
	597	213	20+
	616	174	20+
	635	25	20+
INSGA-II	584	25	20+

Table 6

5-Job problem Comparison between the C values

C (IM, IN)	C (IN, IM)	C (N, IN)	C (IN, N)
0	0	0	1

Note: IM: IMOPSO, N: NSGA-II, IN: INSGA-II.

In conclusion, the INSGA-II algorithm performs better in solving the 5-Job problem.

For the 10-Job problem, as shown in Table 7, both NSGA-II and INSGA-II algorithms obtains three sets of fitness values, while the IMOPSO algorithm generates relatively fewer results. The number of different scheduling schemes generated by NSGA-II and INSGA-II significantly exceeds that of the IMOPSO algorithm.

Table 7

10-Job problem Comparison results of fitness

Algorithm	Adaptation value		Number of
	f1	f2	different scheduling solutions
IMOPSO	615	405	1
	595	483	9
NSGA-II	587	497	20+
	688	457	2
	711	438	2
INSGA-II	577	493	20+
	580	471	2
	614	437	20+

As shown in Table 8, the solution sets obtained by INSGA-II is not dominated by the solution sets obtained by either IMOPSO or NSGA-II. Moreover, C (IN, IM) is 0.5, indicating that the results generated by the INSGA-II algorithm are superior to those produced by the IMOPSO algorithm. Additionally, C (IN, N) is equal to 1, suggesting that the solution sets obtained by the INSGA-II algorithm dominates the solution sets obtained by the NSGA-II algorithm.The grant chart of the best solution for instance 10-job obtained by INSGA-II is shown in Fig. 6.

Table 8

10-Job problem Comparison between the C values

C (IM, IN)	C (IN, IM)	C (N, IN)	C (IN, N)
0	0.5	0	1

Note: IM: IMOPSO, N: NSGA-II, IN: INSGA-II.

Fig. 6

The grant chart of the best solution for instance 10-job obtained by INSGA-II.

In summary, the INSGA-II algorithm still performs better for the 10-Job problem.

4.2 Experimental simulation of HJSMT problem with cooperative effect

The experimental running environment and parameter settings in this subsection are the same as those described in subsection 4.1. The processing times required for each operation, as well as the processor combination needed, is set according to Table 9. The delivery time is also defined as outlined in subsection 4.1.

Table 9
Cooperative effect example

Job Operation 1 Operation 2 Operation 3 Operation 4 Operation 5

J₁ M1, M3, M5 (68) M2, M4 (96) M1, M5 (53) M3, M4 (32) M1, M3, M5 (64)

J₂ M2, M4 (99) M1, M3 (75) M2 (76) M3, M5 (60) M4 (83)

J₃ M1 (41) M5 (67) M3, M4 (3) M2, M5 (99) M2 (15)

J₄ M1, M4 (82) M1, M3, M5 (65) M2 (26) M2, M4 (99) M1, M3 (10)

J₅ M3, M5 (82) M3 (4) M2, M4 (90) M1, M2 (74) M4, M5 (76)

Job	Operation 1	Operation 2	Operation 3	Operation 4	Operation 5
J₁	M1, M3, M5 (68)	M2, M4 (96)	M1, M5 (53)	M3, M4 (32)	M1, M3, M5 (64)
J₂	M2, M4 (99)	M1, M3 (75)	M2 (76)	M3, M5 (60)	M4 (83)
J₃	M1 (41)	M5 (67)	M3, M4 (3)	M2, M5 (99)	M2 (15)
J₄	M1, M4 (82)	M1, M3, M5 (65)	M2 (26)	M2, M4 (99)	M1, M3 (10)
J₅	M3, M5 (82)	M3 (4)	M2, M4 (90)	M1, M2 (74)	M4, M5 (76)

Tables 10 through 12 present the combination of fitness values and the number of different scheduling solutions generate by the INSGA-II and IMOPSO algorithms under cooperation ratios of 90%, 80%, and 70%. Although the processing time and time window settings are set the same as in subsection 4.1, the number of processors is smaller, resulting in longer overall processing time and tardiness.

As shown in the tables, the IMOPSO algorithm obtains two sets of fitness values at a cooperation ratio of 90% and 80%, and only one set of fitness values at a cooperation ratio of 70%. Meanwhile, the INSGA-II algorithm generates three sets of fitness values at a cooperation ratio of 90% and two sets of fitness values at both 80% and 70% cooperation ratios. Overall, the INSGA-II algorithm achieves a relatively higher number of diverse fitness combinations than the IMOPSO algorithm. The number of scheduling solutions generate by IMOPSO are relatively small, while the INSGA-II algorithm generate over a hundred scheduling solutions in many cases, with multiple sets of fitness values generating numerous scheduling solutions at each cooperation ratio setting. This indicates that the INSGA-II algorithm generates more comprehensive results.

Table 10

Comparison of fitness value when the cooperation ratio is 90%

Algorithm	Adaptation value		Number of
	f1	f2	different scheduling solutions
IMOPSO	765	521	1
	710	533	13
INSGA-II	749	488	2
	715	507	2
	707	533	288

Table 11

Comparison of fitness value when the cooperation ratio is 80%

Algorithm	Adaptation value		Number of
	f1	f2	different scheduling solutions
IMOPSO	675	387	1
	700	279	1
INSGA-II	703	356	2
	671	366	98

Table 12

Comparison of fitness value when the cooperation ratio is 70%

Algorithm	Adaptation value		Number of
	f1	f2	different scheduling solutions
IMOPSO	637	149	1
INSGA-II	584	331	2
	630	255	193

Furthermore, comparing the fitness value results obtained by the same algorithm for the three cooperation ratios, can observe a gradual decrease in the value from a cooperation ratio of 90% to 70%. As per the previous formula, when the cooperative effect is larger, the actual processing time of the job increases, leading to longer completion time and total tardiness, which means that with more skilled worker combinations, the processing time becomes shorter.The grant chart of the best solutions with cooperation ratios of 90%, 80%, and 70% obtained by INSGA-II is shown in Figs. 7 to 9.

Fig. 7

The grant chart of the best solution obtained by INSGA-II when the cooperation ratio is 90%.

Fig. 8

The grant chart of the best solution obtained by INSGA-II when the cooperation ratio is 80%.

Fig. 9

The grant chart of the best solution obtained by INSGA-II when the cooperation ratio is 70%.

Table 13 indicates that at a cooperation ratio of 90%, none of the sets of fitness values obtained by the INSGA-II algorithm are dominated by those obtained by IMOPSO, but all sets of fitness values generate by IMOPSO can be dominated by at least one set of fitness values produced by the INSGA-II algorithm. At a cooperation ratio of 80%, C (IM, IN) and C (IN, IM) are both 0.5, indicating that while both algorithms have one set of fitness value combinations that can be dominated by each other, the INSGA-II algorithm generates significantly more scheduling solutions. Similarly, the effectiveness of the INSGA-II algorithm is demonstrated for a cooperation ratio of 70%.

Table 13

Comparison between the C values

Cooperation ratio	C (IM, IN)	C(IN, IM)
90%	0	1
80%	0.5	0.5
70%	0	1

Note: IM: IMOPSO, IN: INSGA-II.

Figures 10 to 12 present scatter plots of the fitness values generated by IMOPSO and INSGA-II at cooperation ratios of 90%, 80%, and 70%, respectively. The plots show that the points representing the INSGA-II algorithm are closer to the bottom left corner of the plot, indicating that the INSGA-II algorithm is more effective and capable of generating relatively better results.

Fig. 10

Scatter plots of particle fitness values for IMOPSO and INSGA-II (cooperation ratio is 90%).

Fig. 11

Scatter plots of particle fitness values for IMOPSO and INSGA-II (cooperation ratio is 80%).

Fig. 12

Scatter plots of particle fitness values for IMOPSO and INSGA-II (cooperation ratio is 70%).

Based on the experimental results, it can be observed that the IMOPSO algorithm generates a relatively small number of scheduling solutions, while the INSGA-II algorithm is capable of generating more solutions. One possible reason for this discrepancy is that the IMOPSO algorithm employs an external population to record better particles, which is currently set to 20 references from previous studies. It is possible that this value may affect the number of particles obtained in the end. On the other hand, the INSGA-II algorithm keeps a certain number of particles in each iteration to enter the next cycle. During the experimental process, it is found that the particles gradually approach the Pareto front during the iteration. However, the final result converges to the same set of fitness values after 200 iterations. When this set of fitness values happens to be the non-dominated solution, a large number of scheduling solutions can be generated.

5 Conclusion

This paper innovatively considers the cooperative effect into the Multi-objective Hybrid Job-shop Scheduling with Multiprocessor Task problem, proposes a suitable algorithm INSGA-II, and proves the effectiveness of the algorithm as well as the influence of the cooperative effect on the scheduling through simulation experiments, which provides a new perspective and idea for the research of scheduling problems.

We establish a mathematical planning model tailored to this problem and solve it using the improve NSGA-II algorithm, which selects the improved priority operation crossover and adds multiple mutations operation to improve the global search capability and addresses the particle trapped in local optimum problem. Meanwhile, the NSGA-II fast non-dominated sorting and elite retention strategy features are also retained to diversify the optimal solutions obtained.

In the experiments, the INSGA-II algorithm, NSGA-II algorithm, and IMOPSO algorithm are applied to the 5-Job and 10-Job problem cases. When considering cooperation ratios of 90%, 80%, and 70%, the INSGA-II algorithm and IMOPSO algorithm are applied to solve the 5-Job cases, demonstrating the superiority of the INSGA-II algorithm in solving problem with both objectives and calculating multiple efficient scheduling solutions.

In future research, alternative solution objectives will be considered based on realistic conditions to better match the current operational requirements of discrete manufacturing enterprises. Additionally, further algorithm improvements will be explored to address the research problem more effectively and efficiently, and generate diverse and satisfactory scheduling solutions that enhance enterprise efficiency.

Footnotes

Acknowledgment

This work was supported by Humanities and Social Sciences Foundation of the Ministry of Education of China (No. 21YJA630012), the Fundamental Research Funds for the Central Universities (No. 2023SKY06).

References

Agnetis

, Billaut

J.C.

, Gawiejnowicz

, Pacciarelli

, Soukhal

Multiagent Scheduling: Models and Algorithms, Springer, 2014..

Azzouz

, Ennigrou

, Said

L.B.

, Scheduling problems under learning effects: classification and cartography, International Journal of Production Research 56 (2018), 1642–1661.

Aghajani , Fouladi

, A multi-objective mathematical model and genetic algorithm for reliability analysis in flexible job-shop scheduling problem, International Journal of Management Concepts & Philosophy 11 (2018), 1478–1484.

Coello

C.A.

, Lechuga

M.S.

MOPSO: A proposal for multiple objective particle swarm optimization, 2002 IEEE Proceedings of the 2002 Congress on Evolutionary Computation (2002).

Zhang

C.Y.

, Dong

, Wang

X.J.

, Li

X.Y.

, Liu

, Improved NSGA-II for the Multi-objective Flexible Job-shop Scheduling Problem, Journal of Mechanical Engineering 46 (2010), 156–164.

Zhang

C.Z.

, Li

Y.Z.

, Yin

S.G.

, Pei

, Optimization of multi-objective fuzzy flexible job shop scheduling problem, Science, Technology and Engineering 20 (2020), 1099–1106.

Biskup

, Single-machine scheduling with learning considerations, European Journal of Operational Research 115 (1999), 173–178.

Erfani Ebrahimnejad

, Moosavi

, An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm, Journal of Industrial and Management Optimization 16 (2020), 1801–1834.

Amiri

, Shirazi

, Tajdin

, Multi-objective simulation optimization for uncertain resource assignment and job sequence in automated flexible job shop, Applied Soft Computing Journal 75 (2019), 1568–4946.

10.

Gao

Research on production scheduling problem with learning effect and resource allocation, Dalian University of Technology (2018).

11.

Moslehi

, Mahnam

, A Pareto approach to multi-objectiveflexible job-shop scheduling problem using particle swarmoptimization and local search, International Journal ofProduction Economics 129 (2011), 14–22.

12.

, Pan

, Liang

, An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems, Computers & Industrial Engineering 59 (2010), 647–662.

13.

J.C.

, Wu

Y.Y.

, Wang

Y.Y.

, Wu

Y.H.

, Worker job shop scheduling algorithm considering learning effect, Control and Decision 37 (2022), 37–46.

14.

Deb

, Pratap

, Agarwal

, Meyarivan

, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6 (2002), 182–197.

15.

Fan

, Wang

, Zhai

Y.F.

, Li

X.N.

, Scatter search algorithm for the multiprocessor task job-shop scheduling problem, Computers & Industrial Engineering 127 (2019), 677–686.

16.

Fan

, Zhai

, Li

, Wang

, Review and classification of hybrid shop scheduling, Production Engineering 12 (2018), 597–609.

17.

Fan

, Zhai

Y.F.

, Li

X.N.

, Zhou

, Simulation research on Hybrid Job-shop Scheduling with Multiprocessor Task problems, Manufacturing Automation 40 (2018), 94–99.

18.

Hernandez Ramírez

, FraustoSolís

, CastillaValdez

, Gonzalez Barbosa

, Sanchez

H.J-P.

, Three Hybrid Scatter Search Algorithms for Multi-Objective Job Shop Scheduling Problem, Axioms 11 (2022), 1680–2075.

19.

Wang

, Cai

, Shi

, Multi-objective flexible job shop energy-saving scheduling problem based on improved genetic algorithm, Nanjing Li Gong Daxue Xuebao/Journal of Nanjing University of Science and Technology 41 (2017), 494–502.

20.

Lei

, A Pareto archive particle swarm optimization for multi-objective job shop scheduling, Computers & Industrial Engineering 54 (2008), 960–971.

21.

Wang

, Fan

, Zhai

Y.F.

, Li

X.N.

, Study of multiprocessor task scheduling problem in network parallel computing system, Computer Engineering and Applications 53 (2017), 264–270.

22.

Brucker

, Krämer

, Shop scheduling problems with multiprocessor tasks on dedicated processors, Annals of Operations Research 57 (1999), 13–27.

23.

Wang

Q.L.

, Duan

X.H.

, Scheduling of flexible job shop based on high-dimension and multi-objective migrating bird optimization algorithm, China Mechanical Engineering 33 (2022), 2601–2612.

24.

Wang

Q.W.

, Xu

Z.H.

, Gu

X.S.

, Multi-processor combined production batch scheduling problem based on brain storm optimization algorithm, Journal of East China University of Science and Technology 48 (2022), 685–695.

25.

Ponnambalam

S.G.

, Ramkumar

, Jawahar

, A multi-objective genetic algorithm for job shop scheduling, Production Planning & Control 12 (2001), 764–774.

26.

Gawiejnowicz

, A note on scheduling on a single processor with speed dependent on a number of executed job, Information Processing Letters 57 (1996), 297–300.

27.

W.H.

, Wang

, Yan

D.H.

, Ji

C.C.

, Flower pollination algorithm for multi-objective fuzzy flexible job shop scheduling, Journal of System Simulation 30 (2018), 4403–4412.

28.

Bao

X.X.

, Ye

C.M.

, Ji

, Huang

, Improved chaotic firework algorithm for multi-objective scheduling optimization, Application Research of Computers 33 (2016), 2601–2605.

29.

Sun

X.Y.

, Improved grey wolf optimization for solving multi-objective flexible job-shop scheduling problems, Software Engineering 25 (2022), 15–18+14.

30.

Y.J.

, Chen*

X.H.

, Gao**

K.Z.

, Zhang

, Li

Y.H.

, Zhao

Z.Y.

, Integrated optimization of real-time order acceptance and flexible job-shop rescheduling with multi-level imperfect maintenance constraints, Swarm and Evolutionary Computation 77 (2023), 101243.

31.

Y.J.

, Chen*

X.H.

, Hu

J.W.

, Zhang

, Li

Y.h.

, Jiang

J.W.

, Joint optimization of preventive maintenance and production rescheduling with new machine insertion and processing speed selection, Reliability Engineering & Systems Safety 220 (2022), 108269.

32.

Y.Y.

, Fan

, Qu

, Zhou

, Research on multi-objective particle swarm algorithm for solving hybrid job-shop scheduling with multiprocessor task problem, Journal of Chinese Computer Systems 43 (2022), 218–224.

33.

Y.Y.

Research on multi-objective problem of hybrid jobshop scheduling with multiprocessor task problem, Beijing Forestry University (2021).

34.

Zitzler

, Deb

, Thiele

, Comparison of multiobjective evolutionary algorithms: empirical results, Evolutionary Computation 8 (2000), 173–195.

Multi-objective hybrid job-shop scheduling with multiprocessor task (HJSMT) problem with cooperative effect

Abstract

Keywords

1 Introduction

2 Model construction of multi-objective HJSMT problem with cooperative effect

2.1 Multi-objective HJSMT problem description

2.2 Cooperative effect

Table 1 Examples of cooperative effect in HJSMT problem Step 1 Step 2 Step 3 J1 M1, M2 M2, M3 M1 J2 M2 M1, M3 M1, M2, M3 J3 M1, M3 M1, M2, M3 M1, M2

3.1 Code mechanism

3.4 Fast non-dominated sorting

3.5 Congestion distance and elite retention strategy

4 Experimental simulation and result analysis

4.1 Experimental simulation of INSGA-II algorithm

Footnotes

Acknowledgment

References

Table 1
Examples of cooperative effect in HJSMT problem

Step 1 Step 2 Step 3

J₁ M₁, M₂ M₂, M₃ M₁

J₂ M₂ M₁, M₃ M₁, M₂, M₃

J₃ M₁, M₃ M₁, M₂, M₃ M₁, M₂