Sage Journals: Discover world-class research

Abstract

The new technology of intelligent manufacturing makes the data of process planning and shop scheduling easier to interconnect, and the integration optimization of different manufacturing processes is an important technology to ensure the implementation of intelligent manufacturing. Integrated process planning and scheduling is a significant research focus in recent years, which could improve the performance of manufacturing system. At present, the research on integrated process planning and scheduling is insufficient to consider the multi-objective and uncertain characteristics widely existing in real manufacturing environment. Therefore, multi-objective integrated process planning and scheduling problem with uncertain processing time and due date is addressed in this article. The mathematical model of multi-objective uncertain integrated process planning and scheduling problem with uncertain processing time and fuzzy due date is established based on fuzzy set, in which the calculation method of uncertainty measurement objective is designed. An effective modified honey bees mating optimization algorithm has been designed to solve the proposed model. Queens set is constructed to maintain the non-dominated solutions found in the optimization process. The calculation method of mating probability between drone and queen bee based on Euclidean distance is designed. Fuzzy operators were utilized to evaluate fitness, judge the non-dominated relationship, and decode the scheduling solution. Different instances were designed and carried out to test the performance of the proposed method. The results show that the proposed method is very effective for solving multi-objective uncertain integrated process planning and scheduling.

Keywords

Integrated process planning and scheduling fuzzy processing time fuzzy due date honey bees mating optimization multi-objective optimization

Introduction

Modern manufacturing faces multiple pressures from the economy, society, and the environment, and manufacturing companies need to further improve efficiency, stabilize production, and enhance brand effects. Research on the theory of operational optimization of advanced manufacturing systems is particularly important for the development of manufacturing companies. In recent years, the rapid development of technologies such as intelligent manufacturing and industrial robot systems has greatly shortened the gap between theoretical research and practical applications. Process planning and shop scheduling are very important in modern manufacturing system, which have vital impact on the product processing capabilities, resource utilization, and production efficiency of the manufacturing system. The purpose of process planning is to select the appropriate processing methods and processing parameters for jobs by analyzing the machining characteristics, accuracy, materials, and so on.^1,2 After the process plans of jobs are determinate, the scheduling is to allocate the operations of all these jobs on machines over time by satisfying the precedence constraints in the process plans.³ Although they are independent of each other and have different functions, they are mutually restricted. Considering process planning and shop scheduling as separate subsystems is not conducive to improve the production efficiency and equipment utilization ratio of the manufacturing system, which will bring a series of conflicts.⁴ If only the operation sequence and processing resources of a single job are taken into account in the process planning stage, it is very easy to generate resource conflicts in the shop scheduling process. To match the real-time status of the workshop, 20%–30% of the previously processed plans must be replanned.⁵ With the rise of intelligent manufacturing, the new technology of intelligent manufacturing makes the data of process planning and shop scheduling easier to interconnect, and the integration optimization of different manufacturing processes is an important technology to ensure the implementation of intelligent manufacturing.^6
–8 Integrated process planning and scheduling (IPPS) can effectively overcome the conflicts caused by independent research, thus improving the efficiency of manufacturing systems.⁹

IPPS problem is more complicated compared with process planning and shop scheduling problems which are non-deterministic polynomial (NP)-complete problems.¹⁰ The IPPS problem has complex machine flexibilities, operation sequence flexibilities, and processing flexibilities, which makes problem solution space enormous and intricate.¹¹ As a result, developing an effective algorithm to deal with IPPS is a challenging work. Furthermore, many different objectives are involved in IPPS problem, such as makespan, total machine workload, total flow time, total tardiness, and so on.^12,13 Decision makers need to make a trade-off among different objectives. On the other hand, there are often a series of uncertain factors in actual production scheduling, such as uncertain processing time for operations, breakdown of machinery, due date variation, order change, and so on,¹⁴ which makes it difficult for the deterministic optimization scheduling scheme to be executed smoothly during implementation. Srinivasan et al.¹⁵ pointed out that the model mismatch caused by the existence of uncertain factors has become the bottleneck of application optimization technology in actual production. Considering multi-objectives and uncertain factors simultaneously could make IPPS problem more representative of real-world situations.

In recent years, researchers begin to study IPPS problem under uncertain environments, but only a few of these studies pay attention to multi-objective uncertain IPPS problem. A large number of scholars have used fuzzy set theory to study uncertain job shop scheduling problems, focusing on the uncertain processing time described by triangular fuzzy numbers and the uncertain due date described by triangle fuzzy numbers.¹⁶ The research results of uncertain job shop scheduling problem can be extended to multi-objective uncertain IPPS problem. Swarm intelligence optimization algorithms based on Pareto optimization have been widely utilized to settle various multi-objective shop scheduling problems.^17

–20 Honey bees mating optimization (HBMO) algorithm has been proposed based on the marriage behavior of the bees, which simulated the mating process of the queen of the hive. It has been applied to many combinatorial optimization problems successfully.^21,22 It is a meaningful work to apply HBMO to multi-objective uncertain IPPS problem based on fuzzy set and Pareto optimization.

In this article, multi-objective IPPS problem with uncertain processing time and due date is addressed by modified HBMO (MHBMO). The mathematical model of multi-objective uncertain IPPS problem with uncertain processing time and fuzzy due date is established based on fuzzy set, in which the calculation method of uncertainty measurement objective is designed. The following operations are designed to modify HBMO to solve multi-objective uncertain IPPS problem. Since the result of multi-objective optimization problem is a set of solutions rather than a solution, the queens set is constructed to maintain the non-dominated solutions found in the optimization process. Because of the multiple objectives that need to be considered, the calculation method of mating probability between drone and queen bee based on Euclidean distance is designed. The brood differentiation strategy is designed based on fast non-dominated sorting scheme. The instances of multi-objective uncertain IPPS problems with different scales were designed, and the proposed optimization method is utilized to solve the instances. The experimental results verify the effectiveness of the proposed method.

The remainder of this article is organized as follows. The “Literature review” section reviews the related works about IPPS in recent years. Problem description is elaborated in the “Problem formulation” section. The “Proposed MHBMO for multi-objective uncertain IPPS” section presents the workflow of the proposed MHBMO for multi-objective uncertain IPPS. The “Experiments and discussion” section shows the experiment results and discussion while the conclusion and future works are given in the last section.

Literature review

In manufacturing companies, process planning and shop scheduling are often two separate departments. It is not realistic to integrate the two departments. Considering this practical problem, IPPS mainly focuses on how to increase the information interaction between process planning and shop scheduling. According to different information interaction methods, the integration model of process planning and shop scheduling is mainly divided into three categories¹: nonlinear method, closed-loop method, and distributed method. There are also some novel IPPS models proposed in recent years. Chu et al.²³ proposed a novel method for IPPS under production uncertainties. The integrated problem was formulated into a bi-level program. To solve the integrated problem, a hybrid method was developed, which iterated between a mixed-integer linear programming solver for the planning problem and an agent-based reactive scheduling method. Jin et al.²⁴ developed some novel mixed integer linear programming (MILP) models for IPPS in a job shop flexible manufacturing system, which were able to express and utilize flexibilities contained in network graphs, and hence had the power to solve network graph-based instances. The established models had been tested on typical test bed instances to verify their correctness. Rietz et al.²⁵ addressed the integration of medium-term production planning and short-term scheduling models. A new detailed scheduling model based on a pseudo-polynomial network flow formulation that can be used to solve real size instances was described and analyzed. Different strategies were explored to simplify the model and reduce its number of constraints. Aguirre and Papageorgiou²⁶ presented a medium-term optimization-based approach for the integration of production planning, scheduling, and maintenance. A multiproduct single-stage batch process plant with parallel units and limited resources was considered in this research. Li²⁷ studied IPPS model for sustainable manufacturing and remanufacturing. Dai et al.²⁸ established an energy-saving IPPS model, in which the energy consumption objectives included the total energy consumption of all working machines in the manufacturing system during the production and nonproduction phases. Zhang et al.²⁹ proposed an integration model based on nonlinear process planning to implement energy-saving method, and the Therblig-based model was used to predict the energy consumption of machine tools in product manufacturing process. It can be seen from the above studies that more optimization objectives and constraints were considered in the establishment of the IPPS model to provide effective serve for the actual production operation process.

According to the different number of optimization objectives considered during the search process, the IPPS solution method can be divided into single-objective optimization method and multi-objective optimization method. Li et al.⁹ presented an effective hybrid algorithm based on genetic algorithm and variable neighborhood search to solve IPPS problem in packaging machinery factory. Zhang and Wong^30,31 proposed an object-coding genetic algorithm and constructive meta-heuristics to deal with IPPS problem. Zhang et al.³² combined extended imperialist competitive algorithm with genetic algorithm to solve the distributed IPPS problem. Ausaf et al.³³ designed a priority-based optimization algorithm to settle multi-objective IPPS problem. Jin et al.³⁴ proposed a multi-objective memetic algorithm for IPPS problem. Zhang et al.³⁵ studied the IPPS problem in remanufacturing environment and proposed a multi-objective genetic algorithm based on simulation to optimize the optimization objectives in process planning stage and shop scheduling stage. Luo et al.¹² proposed a multi-objective genetic algorithm based on immune principle and external archive to settle multi-objective IPPS. Manupati et al.³⁶ constructed a mobile agent-based approach to optimize the IPPS problem with maximum completion time and machine utilization for the network manufacturing environment. Milica et al.³⁷ proposed a particle swarm optimization algorithm based on chaos theory to optimize the maximum completion time, mean flow time, and machine load balance of IPPS. Elahe³⁸ used the weighted method to deal with three objectives of the IPPS problem and solved the problem using a genetic algorithm.

In general, the research method of single-objective IPPS problem is more mature, mainly focusing on the design of effective hybrid algorithms. Multi-objective IPPS solution methods can be divided into non-Pareto methods and Pareto-based methods. The non-Pareto methods belong to the pretest method, that is, the determination of the weight represents the preference of the decision maker, and the setting of the weight will bring certain subjective influence factors to the optimization result. The Pareto-based methods belong to the posttest method, that is, the optimization is made first. The optimization process is only related to the characteristics of the problem itself, and less subjective factors. Because the Pareto-based method can more objectively reflect the characteristics of the problem, it is the focus of current research. This article will adopt Pareto-based methods to handle multi-objective uncertain IPPS problem.

To make theoretical results better serve actual production, more and more researchers have begun to pay close attention to IPPS under uncertain environment. Seker et al.³⁹ applied genetic algorithm and fuzzy neural network to solve the uncertain IPPS problem in mass customization environment. The genetic algorithm was used to obtain the optimal scheduling sample data, and the fuzzy neural network was adopted to obtain the dynamic scheduling knowledge to guide the regeneration of the optimal scheduling scheme in the dynamic workshop environment. Liu et al.⁴⁰ proposed the ant colony optimization algorithm to solve the IPPS problem by considering the uncertainty of the arrival of new jobs. Xia et al.⁴¹ constructed a mathematical model of dynamic IPPS problem, considering the dynamic events of machine faults and new job arrivals. The rolling window technology was applied to the solution of dynamic IPPS problems. Yu et al.⁴² proposed a hybrid genetic-particle swarm optimization algorithm to solve the dynamic IPPS problem. The solution process was divided into static phase and dynamic phase. In the dynamic phase, IPPS could better cope with dynamic events by adjusting the process plans of jobs to be processed during the machine failure time period. Wen et al.⁴³ designed an improved genetic algorithm to settle multi-objective uncertain IPPS model by considering fuzzy processing time. Wang et al.⁴⁴ used interval numbers to describe the uncertainty of processing time in IPPS problem.

The research on IPPS problems under uncertain environment focuses on the following two aspects: using fuzzy numbers and interval numbers to describe the uncertainty of processing time and due date, and using rolling window technology, fuzzy neural network, increasing buffer time window, and so on to respond the uncertain events, such as machine failures and new job arrivals. Compared with IPPS problem in static environment, the uncertain IPPS problem brings the new uncertainty evaluation objectives. Due to the randomness of the uncertain events, the calculation of uncertainty evaluation objectives for uncertain IPPS is very complicated. Therefore, this article will design a novel calculation method of uncertainty evaluation objective.

Problem formulation

Fundamental theory of fuzzy sets

In actual production process, factors such as the condition of different machines in the workshop and the different degree of operators’ proficiency have certain uncertainties, so the processing time of jobs is often difficult to express with a certain value. The customer’s due date requirement for jobs is usually an interval, and the customer will have the highest satisfaction when jobs can be delivered within this interval. Early or delayed delivery will reduce customer satisfaction. According to the characteristics of processing time and due date in the actual production process, many researchers use the triangular fuzzy numbers to describe the uncertain processing time of jobs and trapezoidal fuzzy numbers to describe the uncertain due date of jobs in the research of uncertain job shop scheduling.⁴⁵

The scheduling type of multi-objective uncertain IPPS problem studied in this article is job shop scheduling, therefore, the triangular fuzzy number is used to describe the indeterminate processing time of jobs, and trapezoidal fuzzy number is used to describe the indefinite due date of jobs in mathematical model.

When solving the multi-objective uncertain IPPS problem, the following fuzzy number operations need to be used.

(1) Addition operation

When calculating the fuzzy processing time and the fuzzy completion time of each job, the addition operation of the triangular fuzzy numbers need to be used. If the two triangular fuzzy numbers are $\tilde{M} = (m_{1}, m_{2}, m_{3})$ and $\tilde{N} = (n_{1}, n_{2}, n_{3})$ , the addition operation is given in formula (1)

\tilde{M} \oplus \tilde{N} = (m_{1} + n_{1}, m_{2} + n_{2}, m_{3} + n_{3})

(2) Taking large operation

In the decoding process of the job shop scheduling stage, the fuzzy start time of each operation need to be computed by using the taking large operations of the triangular fuzzy numbers. If two triangular fuzzy numbers are $\tilde{M} = (m_{1}, m_{2}, m_{3})$ and $\tilde{N} = (n_{1}, n_{2}, n_{3})$ , the taking large operation is given in formula (2)

\tilde{M} \lor \tilde{N} ≅ (m_{1} \lor n_{1}, m_{2} \lor n_{2}, m_{3} \lor n_{3})

After the two triangular fuzzy numbers having undergone the taking large operation, the result is an approximate triangular fuzzy number.

(3) Comparison operation

Comparison operation is needed during decoding process of job shop scheduling, judging the dominant relationship and determining the fuzzy maximum completion time. If the two triangular fuzzy numbers are $\tilde{M} = (m_{1}, m_{2}, m_{3})$ and $\tilde{N} = (n_{1}, n_{2}, n_{3})$ , the following criteria are adopted to rank fuzzy numbers:

Criterion 1: Set $C_{1} (\tilde{A}) = \frac{a_{1} + 2 a_{2} + a_{3}}{4}$ , if $C_{1} (\tilde{M}) > C_{1} (\tilde{N})$ , then $\tilde{M} > \tilde{N}$ .

Criterion 2: If $C_{1} (\tilde{M}) = C_{1} (\tilde{N})$ , set $C_{2} (\tilde{A}) = a_{2}$ , and if $C_{2} (\tilde{M}) > C_{2} (\tilde{N})$ , then $\tilde{M} > \tilde{N}$ .

Criterion 3: If $C_{2} (\tilde{M}) = C_{2} (\tilde{N})$ , set $C_{3} (\tilde{A}) = a_{3} - a_{1}$ , and if $C_{3} (\tilde{M}) > C_{3} (\tilde{N})$ , then $\tilde{M} > \tilde{N}$ .

(4) Distance calculation operation

If two triangular fuzzy numbers are $\tilde{M} = (m_{1}, m_{2}, m_{3})$ and $\tilde{N} = (n_{1}, n_{2}, n_{3})$ , the Euclidean distance between them is given in formula (3)

d (\tilde{M}, \tilde{N}) = \sqrt{\frac{1}{3} [{(m_{1} - n_{1})}^{2} + {(m_{2} - n_{2})}^{2} + {(m_{3} - n_{3})}^{2}]}

Mathematical model for multi-objective uncertain IPPS

The multi-objective uncertain IPPS problem focused in this article can be defined as follows¹¹: There are a set of n jobs to be processed on m machines. Each job has various operations and alternative process plans. The processing time and due date of each job is uncertain. One operation is allowed to be executed by alternative machines. The aim of multi-objective uncertain IPPS is to select suitable manufacturing resources for each job, determine the operations’ processing sequence and the start time of each operation on each machine by satisfying the precedence constraints among operations and achieving the corresponding multi-objectives simultaneously.

Based on the multi-objective IPPS mathematical model¹² and the basic theory of the above fuzzy sets, a multi-objective uncertain IPPS optimization problem model is established. To better describe the model, the following symbols are defined at first:

n: the number of all jobs to be machined;

m: the number of all machines in the production workshop;

$\tilde{D_{i}}$ : the due date of job i, which is descried as trapezoidal fuzzy numbers;

g_i : the number of all alternative process plans for each job;

n_il : the number of operations contained in the lth process plan of job i;

o_ijl : the jth operation in lth process plan of job i;

k: the optional machine number of o_ijl ;

${\tilde{P}}_{i j l k}$ : processing time of o_ijl machined in machine k, triangular fuzzy numbers;

${\tilde{C}}_{i j l k}$ : the earliest completion time of o_ijl machined in machine k, triangular fuzzy numbers;

${\tilde{C}}_{i}$ : the completion time of job i, triangular fuzzy numbers;

A: a very large positive number; $X_{i l} = \{\begin{cases} 1 & the l th process plan of operation i is selected \\ 0 & otherwise \end{cases};$

$Y_{i j l x y z k} = \{\begin{cases} 1 o_{i j l} is machined before o_{x y z} in machine k \\ 0 otherwise \end{cases}; and$

$Z_{i j l k} = \{\begin{cases} 1 o_{i j l} machined in machine k \\ 0 otherwise \end{cases}$ .

The optimization objectives involved in multi-objective uncertain IPPS problem can be divided into two categories. One is the objectives represented as triangular fuzzy numbers, such as fuzzy maximum makespan, fuzzy maximum machine load, and fuzzy total machine load. Another is the objectives about the uncertainty measure, which contains the mean customer satisfaction and the spread of makespan. The five objective functions are provided as follows:

f ₁: Minimize fuzzy makespan

Min f_{1} = \tilde{C} = max_{i \in [1, n]} \tilde{C_{i}}

f ₂: Minimize fuzzy maximum machine load

Min f_{2} = MMW = max_{k \in [1, m]} \sum_{i = 1}^{n} \sum_{j = 1}^{n_{i l}} \sum_{l = 1}^{g_{i}} ({\tilde{P}}_{i j l k} \times X_{i l} \times Z_{i j l k})

f ₃: Minimize fuzzy total machine load

Min f_{3} = TMW = \sum_{k = 1}^{m} \sum_{i = 1}^{n} \sum_{j = 1}^{n_{i l}} \sum_{l = 1}^{g_{i}} ({\tilde{P}}_{i j l k} \times X_{i l} \times Z_{i j l k})

f ₄: Maximize average customer satisfaction

Max f_{4} = S T = \frac{1}{n} \sum_{i = 1}^{n} S T_{i}

f ₅: Minimize the spread of fuzzy makespan if $\tilde{C} = (c_{1}, c_{2}, c_{3})$

Min f_{5} = Spread = c_{3} - c_{1}

The following constraints need to be satisfied:

(1) The earliest completion time of the first operation in the lth process route of job i need to satisfy the following constraint

\begin{array}{l} ({\tilde{C}}_{i 1 l k} \times Z_{i 1 l k} \times X_{i l}) + A (1 - X_{i l}) \geq ({\tilde{P}}_{i 1 l k} \times Z_{i 1 l k} \times X_{i l}) \\ i \in [1, n], l \in [1, g_{i}], k \in [1, m] \end{array}

(2) The earliest completion time of the last operation in the lth process route of job i need to satisfy the following constraint

\begin{array}{l} ({\tilde{C}}_{i n_{i l} l k} \times Z_{i n_{i l} l k} \times X_{i l}) - A (1 - X_{i l}) \leq \tilde{C} \\ i \in [1, n], l \in [1, g_{i}], k \in [1, m] \end{array}

(3) Operation constraint: Only one operation of each job can be processed at the same time

\begin{array}{l} ({\tilde{C}}_{i j l k_{0}} \times Z_{i j l k_{0}} \times X_{i l}) - ({\tilde{C}}_{i (j - 1) l k_{1}} \times Z_{i (j - 1) l k_{1}} \times X_{i l}) + A \times (1 - X_{i l}) \geq ({\tilde{P}}_{i j l k_{0}} \times Z_{i j l k_{0}} \times X_{i l}) \\ i \in [1, n], j \in [1, n_{i l}], l \in [1, g_{i}], k_{0}, k_{1} \in [1, m] \end{array}

(4) Machine constraint: Each machine can only process one process at a time

\begin{array}{l} ({\tilde{C}}_{x y z k} \times Z_{x y z k} \times X_{x z}) - ({\tilde{C}}_{i j l k} \times Z_{i j l k} \times X_{i l}) + A \times (1 - X_{i l}) + A \times (1 - X_{x z}) \\ + A \times (1 - Y_{i j l x y z k} \times Z_{x y z k} \times X_{x z} \times Z_{i j l k} \times X_{i l}) \geq ({\tilde{P}}_{x y z k} \times Z_{x y z k} \times X_{x z}) \\ ({\tilde{C}}_{i j l k} \times Z_{i j l k} \times X_{i l}) - ({\tilde{C}}_{x y z k} \times Z_{x y z k} \times X_{x z}) + A \times (1 - X_{i l}) + A \times (1 - X_{x z}) \\ + A \times (Y_{i j l x y z k} \times Z_{x y z k} \times X_{x z} \times Z_{i j l k} \times X_{i l}) \geq ({\tilde{P}}_{i j l k} \times Z_{i j l k} \times X_{i l}) \\ ​ \\ i, x \in [1, n], j, y \in [1, n_{i l, x z}], l, z \in [1, g_{i, x}], k \in [1, m] \end{array}

(5) Process plan constraint: Only one process plan can be selected each job at a time

\sum_{l = 0}^{g_{i l}} X_{i l} =1 l \in [1, g_{i l}]

(6) Only one optional machine can be selected for each operation

\sum_{k = 1}^{m} Z_{i j l k} = 1 i \in [1, n], j \in [1, n_{i l}], l \in [1, g_{i}]

(7) The completion time of all operations should meet the following constraint

{\tilde{C}}_{i j l k} \times Z_{i j l k} \times X_{i l} \geq 0 i \in [1, n], j \in [1, n_{i l}], l \in [1, g_{i}]

In the above multi-objective uncertain IPPS problem model, the objectives for uncertainty measure contain mean customer satisfaction and the spread of fuzzy makespan. The greater the average customer satisfaction, the more satisfied the customer is with the uncertain due date. The smaller the spread of the fuzzy maximum completion time, the smaller the uncertainty of the fuzzy makespan. The evaluation method of customer satisfaction in multi-objective uncertain IPPS problem will be discussed in the following section.

Evaluation method of customer satisfaction in uncertain IPPS

In a deterministic environment, makespan and due date of the job are determined value, and it is easy to evaluate whether the job is delayed or completed in advance. However, when the makespan and due date of the job are uncertain values, the relationship between uncertain makespan and the due date of each job is very complicated. How to evaluate the relationship between the makespan and the due date of the job is very important. In the research of uncertain job shop scheduling problems, scholars generally use customer satisfaction to evaluate the relationship between fuzzy makespan and fuzzy due date. It is very necessary to consider optimizing customer satisfaction when conducting a research on multi-objective uncertain IPPS problem.

Suppose in a scheduling scheme, the fuzzy makespan of job i is ${\tilde{C}}_{i} = (c_{i 1}, c_{i 2}, c_{i 3})$ , fuzzy due date is ${\tilde{D}}_{i} = (d_{i 1}, d_{i 2}, d_{i 3}, d_{i 4})$ . Membership functions $μ_{{\tilde{C}}_{i}} (x)$ and $μ_{{\tilde{D}}_{i}} (x)$ for ${\tilde{C}}_{i}$ and ${\tilde{D}}_{i}$ , respectively, are shown in formulas (16) and (17)

μ_{{\tilde{C}}_{i}} (x) = \{\begin{cases} 0, & x \leq c_{i 1} \\ \frac{x - c_{i 1}}{c_{i 2} - c_{i 1}}, & c_{i 1} \leq x \leq c_{i 2} \\ \frac{x - c_{i 3}}{c_{i 2} - c_{i 3}}, & c_{i 2} \leq x \leq c_{i 3} \\ 0, & x > c_{i 3} \end{cases}

μ_{{\tilde{D}}_{i}} (x) = \{\begin{cases} 0, & x \leq d_{i 1} \\ \frac{x - d_{i 1}}{d_{i 2} - d_{i 1}}, & d_{i 1} \leq x \leq d_{i 2} \\ 1, & d_{i 2} \leq x \leq d_{i 3} \\ \frac{x - d_{i 4}}{d_{i 3} - d_{i 4}}, & d_{i 3} \leq x \leq d_{i 4} \\ 0, & x > d_{i 4} \end{cases}

Traditionally, most of the literature used customer satisfaction calculation method based on the intersection area of membership function, which is given in formula (18)

A I_{i} = (area {\tilde{C}}_{i} \cup {\tilde{D}}_{i}) / (area {\tilde{C}}_{i})

The method has the following problems:

According to the different positions between the three vertices of the triangular fuzzy number and the four vertices of the trapezoidal fuzzy number, $A_{7}^{7} / (A_{3}^{3} \times A_{4}^{4}) = 35$ different positional relationships will be generated between the fuzzy completion time and the fuzzy delivery date. The calculation method of the intersection area of each position relationship is generally different, which will greatly increase the calculation time of the customer satisfaction during the problem-solving process.

When the makespan of job i is located at three different positions as shown in Figure 1, according to the traditional customer satisfaction evaluation method, customer satisfaction is the same in all three locations. However, as can be clearly seen from Figure 1, when the makespan of the job i is in the position 2, all possible makespan can ensure maximum customer satisfaction of the job. When the completion time of job i is at position 1, if the makespan of job i is between (d_i ₁, d_i ₂), the customers’ satisfaction cannot be maximized. Similarly, when the completion time of job i is at the position 3, the makespan of job i may drop in (d_i ₃, d_i ₄), and the customer satisfaction cannot be maximized at this time. It can be seen that the decision makers tend to choose the scheme in the actual production process when the makespan of the job i is at the position 2. Compared with the other two schemes, position 2 can avoid the risks in the uncertain environment. However, if formula (18) is used as the customer satisfaction evaluation index, it is impossible to distinguish these three different schemes. If the decision maker evaluates the customer satisfaction based on formula (18), it cannot evade the deterioration of the objective value in the worst case of the uncertain environment.

Figure 1.

Three different positional relationships between fuzzy makespan and fuzzy due date.

In view of the shortcomings of the evaluation method based on formula (18), this article makes some improvements on the satisfaction evaluation method proposed by Hu et al.,⁴⁶ which is used to comprehensively evaluate the customers’ satisfaction with the scheduling scheme under the uncertain environment. The proposed method is consistent with the evaluation method based on intersection area, while the calculation is relatively simple. This method of evaluating customer satisfaction is detailed as below.

Since the makespan of job i is a triangular fuzzy number, it is necessary to consider not only the degree of customer satisfaction at the most possible completion time but also the influence of customer satisfaction when the completion time deviates from the most likely completion time. As shown in Figure 2, $μ_{{\tilde{D}}_{i}} (c_{i 2})$ could be directly used to evaluate customer satisfaction with the most possible completion time of job i. However, when evaluating the customers’ satisfaction with the possible completion time of the job i in the worst case, it is not suitable to directly use $μ_{{\tilde{D}}_{i}} (c_{i 1})$ and $μ_{{\tilde{D}}_{i}} (c_{i 3})$ for evaluation. This is because c_i ₁ and c_i ₃ represent the most optimistic completion time and the most pessimistic completion time of job i, that is, the worst possible result, but their credibility is 0, so there is no reference value. Suppose the customer satisfaction is ST_il when the worst possible result occurs while only the delay time of job i is considered. Suppose the customer satisfaction is ST_ie when the worst possible result occurs while only earlier completion of job i is considered. In this case, the following definitions are given

S T_{i l} = inf_{x} max (1 - μ_{{\tilde{C}}_{i}} (x), μ_{(- \infty, μ_{{\tilde{D}}_{i}} (x)]} (x))

S T_{i e} = inf_{x} max (1 - μ_{{\tilde{C}}_{i}} (x), μ_{[μ_{{\tilde{D}}_{i}} (x), + \infty)} (x))

Figure 2.

Schematic diagram of customer satisfaction under trapezoidal due date.

According to the possibility theory proposed by Zadeh,⁴⁷ $(- \infty, {\tilde{D}}_{i}]$ is less than or equal to the fuzzy number of ${\tilde{D}}_{i}$ , $[{\tilde{D}}_{i}, + \infty)$ is more than or equal to the fuzzy number of ${\tilde{D}}_{i}$ . As shown in Figure 2, the membership functions are $μ_{(- \infty, {\tilde{D}}_{i}]} (y) = sup_{x \geq y} μ_{{\tilde{D}}_{i}} (x)$ and $μ_{[{\tilde{D}}_{i}, + \infty)} (y) = sup_{x \geq y} μ_{{\tilde{D}}_{i}} (x)$ . The formula (19) represents the minimum possibility that ${\tilde{C}}_{i}$ is less than ${\tilde{D}}_{i}$ . Formula (20) represents the maximum possibility that ${\tilde{C}}_{i}$ is less than ${\tilde{D}}_{i}$ . The intersection of the left of $1 - μ_{{\tilde{C}}_{i}} (x)$ and $μ_{[{\tilde{D}}_{i}, + \infty)} (x)$ is (c_ie , ST_ie ). The intersection of the right of $1 - μ_{{\tilde{C}}_{i}} (x)$ and $μ_{(- \infty, {\tilde{D}}_{i}]} (x)$ is (c_il , ST_il ). The corresponding positions are shown in Figure 2, where ST_il is the infimum of $max (1 - μ_{{\tilde{C}}_{i}} (x), μ_{(- \infty, μ_{{\tilde{D}}_{i}} (x)]} (x))$ and ST_ie is the infimum of $max (1 - μ_{{\tilde{C}}_{i}} (x), μ_{[μ_{{\tilde{D}}_{i}} (x), + \infty)} (x))$ . According to the mathematical meaning, ST_il represents the minimum possibility that the fuzzy completion time is less than the fuzzy due date. The greater the possibility that the fuzzy completion time is smaller than the fuzzy delivery date, the larger ST_il is. As a result, ST_il can be used to measure the customers’ satisfaction with the completion of job i only the tardiness penalty is considered. Similarly, ST_ie represents the minimum possibility that the fuzzy completion time is more than the fuzzy due date. The greater the possibility that the fuzzy completion time is larger than the fuzzy due date, the larger the ST_ie is, so ST_ie can be used to evaluate the customers’ satisfaction with completion of job i only the early penalty is considered. As can be seen from Figure 2, the point c_ie and the point c_il have a certain credibility under the membership function. Therefore, ST_ie and ST_il are defined as the worst possible outcomes results of jobs’ advance/tardiness with certain credibility. They are able to assess the changes in customer satisfaction in the worst case while taking into account certain credibility.

In the case where only the job is considered to be penalized in advance, when the completion time of the job is greater than or equal to d_i ₂, the job may not be prematurely completed, and the customers’ satisfaction is maximum. When the completion time of the job is less than d_i ₂, there is a possibility of early completion, and the customers’ satisfaction is gradually reduced. In the case where only the job is considered to be penalized in tardiness, when the completion time of the job is less than or equal to d_i ₃, the job is unlikely to be completed, and the customers’ satisfaction is maximum. When the completion time of the job is larger than d_i ₃, there is a possibility of tardiness, and the customers’ satisfaction is gradually reduced.

Based on the above analysis, it can be concluded that there are three possibilities for the value of ST_il :

when $c_{i 2} \geq d_{i 4}$ , $S T_{i l} = 0$ ;

when $c_{i 2} < d_{i 4}$ and $c_{i 1} > d_{i 3}$ , $S T_{i l} = \frac{d_{i 4} - c_{i 2}}{c_{i 3} - c_{i 2} + d_{i 4} - d_{i 3}}$ ;

when $c_{i 3} \leq d_{i 3}$ , $S T_{i l} = 1$ .

There are also three possibilities for the value of ST_ie :

when $c_{i 2} \leq d_{i 1}$ , $S T_{i e} = 0$ ;

when $c_{i 2} > d_{i 1}$ and $c_{i 1} < d_{i 2}$ , $S T_{i e} = \frac{c_{i 2} - d_{i 1}}{d_{i 2} - d_{i 1} + c_{i 2} - c_{i 1}}$ ;

when $c_{i 1} \geq d_{i 2}$ , $S T_{i e} = 1$ .

The early or delayed completion of jobs will result in a certain degree of decrease in customer satisfaction. Under normal circumstances, the customers’ tolerance for the early completion of the job is higher than that of tardiness. Therefore, in this research, ST_il and ST_il are given different weights ω_l and ω_e, while $ω_{l} > ω_{e}, ω_{l} + ω_{e} = 1$ .

Based on the above discussion, the customers’ satisfaction with job i can be computed by formula (21)

S T_{i} = \{\begin{cases} \begin{matrix} \frac{ω_{e} \times S T_{i e} + ω_{l} \times S T_{i l} + μ_{{\tilde{D}}_{i}} (c_{i 2})}{2} & otherwise \end{matrix} \\ \begin{matrix} 0 & \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} ​ & ​ \end{matrix} & ​ \end{matrix} & ​ & ​ \end{matrix} & ​ & ​ \end{matrix} & ​ & c_{i 1} > d_{i 4} \end{matrix} o r \end{matrix} c_{i 3} < d_{i 1} \end{cases}

This evaluation method only needs to pay attention to the position of the three points (c_ie , ST_ie ), $[c_{i 2}, μ_{{\tilde{D}}_{i}} (c_{i 2})]$ , (c_il , ST_il ). This calculation method is simpler than the evaluation method of the intersection area, which can better avoid the impact of worst possible results on the solution in an uncertain environment and reflect the customers’ satisfaction with a given solution.

Proposed MHBMO for multi-objective uncertain IPPS

The basic principle of HBMO

The HBMO algorithm simulates the mating process of the queen in the hive. At the beginning of the whole mating flight, the queen flies away from the nest and performs a dance, and then the drones follow the queen and mate with her in the air. It means that some sperm from the drones will reach the queen’s spermatheca to form the genetic pool of the colony. The queen uses the stored sperms to fertilize eggs. Each time a queen lays fertilized eggs, she retrieves a mixture of the sperms stored in the spermatheca randomly. The queen mates multiple times, and the drones will die after mating with the queen once.

The mating flight can be considered as a set of transitions in a state-space. At the start of the flight, the queen is initialized with some energy and speed, and she will return to her nest when the energy is less than a threshold or when her spermatheca is full. The queen moves between the different states in the space in some speed and mates with the followed drones at each state probabilistically. A drone mates with the queen probabilistically using an annealing function as follows²¹

Prob(Q, D) = e^{- \frac{Δ (f)}{Speed(t)}}

where Prob(Q, D) is the probability of adding the sperm of drone D to spermatheca of queen Q (i.e. the probability of a successful mating); $Δ (f)$ is the absolute difference between the fitness of D and the fitness of Q; and Speed(t) is the speed of the queen at time t. It is apparent that the probability of mating is high either when the queen is still in the start of her mating flight or when the fitness of the drone is as good as the queen’s. If the mating is successful, the drone’s sperm is stored in the queen’s spermatheca.

After each transition in space, the queen’s speed and energy are reduced using the following equations²¹

Speed (t + 1) = α \times Speed (t)

Energy (t + 1) = α \times Energy (t)

where the $α \in (0, 1)$ , it means that the speed and energy of the queen will be reduced after each transition and each step.

After the mating flight, the queen uses the sperms stored in the spermatheca to create the new broods by the crossover operator. Because the broods contain different parts of the genotype in the drones’ sperm, the quality of the new broods has more exploration abilities.

As the role of workers in the colony is restricted to brood care, the workers are employed to improve the broods produced by the crossover operator. In HBMO algorithm, each worker is represented as a heuristic which help improve a set of broods. The number of workers contains two parts ( $w = w 1 + w 2$ ), w1 is the number of single local search strategies and w2 is the number of their combinations. Each new produced broods will choose one worker to improve it randomly. The queen will be replaced by the new brood, which has better fitness than her. Otherwise, the brood becomes one of the drones in the next flight if its fitness is better than one of the drones.

With the basic characters of the honey bees’ mating described above, it is clear that the HBMO algorithm consists of three main components:

The queen’s mating flight: In this component, the queen starts a mating flight and mates with the drones followed.

Generation of broods: In this component, a queen generates a number of new broods using the sperms in its spermatheca.

Improvement of broods: In this component, the new produced broods choose a worker to improve itself randomly. This component can increase the exploration abilities of the algorithm.

The basic HBMO algorithm is well applied in combinatorial optimization problems and is generally superior to genetic algorithm and particle swarm optimization algorithm. But it only works for single-objective optimization problems. To solve the problem that the basic HBMO algorithm is difficult to optimize multi-objectives at the same time, this article mainly improves the basic HBMO algorithm as follows:

There is only one queen in the basic HBMO algorithm, which represents the optimal solution found in the process of optimization. Since the target of multi-objective optimization problem is to find a set of non-dominated solutions rather than a solution, a set of queens is designed in MHBMO to save the non-dominated solutions found in the algorithm optimization process.

Each bee has multiple evaluation objectives when solving multi-objective optimization problems, so the calculation method of $Δ (f)$ in formula (22) needs to be changed. Therefore, a method for calculating the mating probability of drones and queen bees based on Euclidean distance is designed.

In the single-objective optimization problem, the differentiation pattern of the broods can be carried out by simply comparing the fitness value. This method is not suitable for multi-objective optimization problems. Aiming at the multi-objective optimization problem that needs to be solved in this article, a broods differentiation strategy based on fast non-dominated sorting is designed.

The details of the above specific changes to HBMO are described in specific in the “MHBMO for uncertain job shop scheduling” section.

The framework of the proposed method

Based on the integration model proposed by Li et al.,⁹ the workflow of the proposed MHBMO for multi-objective uncertain IPPS is given in Figure 3.

Figure 3.

Workflow of proposed MHBMO for multi-objective uncertain IPPS. MHBMO: modified honey bees mating optimization; IPPS: integrated process planning and scheduling.

The main steps of the proposed method are described as follows:

Step 1: Generate the initial process plan population for each job randomly.

Step 2: Optimize the process plan for each job by HBMO respectively.

Step 3: Output near-optimal process plans represented by queen for each job.

Step 4: According to the determinate process plan for each job, generate the initial job shop scheduling population randomly.

Step 5: Optimize uncertain IPPS by MHBMO.

Step 6: Output the optimized process plan for each job and the corresponding scheduling plan.

Step 7: Update the non-dominated set for uncertain IPPS.

Step 8: If the number of current generation reaches to the maximum generation of uncertain IPPS, output the non-dominated set. Otherwise, go to step 2.

HBMO for uncertain process planning

The aim of process planning in this research is to provide various near-optimal process plans for the scheduling system. HBMO is applied to optimize process planning population in this article. Encoding and decoding schemes in Li et al.⁹ were used to initial the population of process planning. The algorithm workflow is the same with the algorithm presented in Wen et al.²¹ The crossover operations in Luo et al.¹² were utilized to generate broods. The local strategies as workers are the same with the method proposed in Wen et al.²¹ As the processing times of operations are fuzzy numbers, the related operations of fuzzy numbers were utilized to evaluate fitness of bees in the population. The difference in fitness between different bees is calculated using formula (3).

MHBMO for uncertain job shop scheduling

After the uncertain process planning, fuzzy maximum machine load and fuzzy total machine load are determinate. The target of scheduling optimization in uncertain IPPS is minimizing fuzzy makespan, spread of fuzzy makespan, and customer satisfaction simultaneously. MHBMO is designed to tackle the multi-objective uncertain job shop scheduling problem. The flowchart of MHBMO for uncertain job shop scheduling is shown in Figure 4 and the details of the algorithm will be described as follows.

Figure 4.

Workflow of MHBMO for uncertain job shop scheduling. MHBMO: modified honey bees mating optimization.

Initial population and fitness evaluation

For each individual in the scheduling population, the operation-based encoding method is used as the encoding method.⁴⁸ Assuming that the number of jobs to be machined is 4, after using the HBMO algorithm to optimize the flexible process plans of each job, the operation number of each job can be determined. Suppose that job 1 has six operations, job 2 has five operations, job 3 has three operations, and job 4 has five operations. A feasible encoding scheme in the shop scheduling population is [1 1 2 3 4 4 2 4 1 1 2 4 2 1 1 4 2 3 3]. The sixth element in the sequence is 4, 4 has been repeated twice, so this element represents the second operation of job 4. Each chromosome should be decoded into active schedules in the decoding procedure.⁴⁹

Since the operation-based encoding method does not generate infeasible solutions, this article randomly generates the initial bee colony of the job shop scheduling. The fuzzy makespan, spread of fuzzy makespan, and customer satisfaction of the scheduling scheme represented by each honey bee in the bee colony can be calculated after the decoding operation.

The fast non-dominated sorting approach in non-dominated sorted genetic algorithm-II (NSGA-II) proposed by Deb et al.⁵⁰ is utilized to divide the population into mutually disjoint non-dominated subpopulations (F ₁, F ₂, F ₃,…) according to fuzzy makespan, spread of fuzzy makespan, and customer satisfaction. The individuals in the subpopulations with a high non-dominated rank are dominated by the individuals with a low non-dominated rank. The honey bees with rank 1 are the non-dominated individuals in the current population. After fast non-dominated sorting, all bees in the bee colony are given a non-dominated grade, and individuals with lower non-dominated grades have better fitness values.

Improvement of broods by workers

In the proposed MHBMO algorithm, each worker bee is equivalent to a local search strategy. Therefore, worker take care of broods is equivalent to using a local search strategy to update the broods. Since the job shop scheduling considered in uncertain IPPS is a multi-objective optimization problem, the calculation time required for each comparison between individuals is greatly increased compared to the single-objective optimization problem. Therefore, it is not suitable to spend too much time in the local search process. Therefore, a worker was randomly selected to improve broods.

Based on the encoding method used in the job shop scheduling stage, two neighborhood structures (N1, N2) are used to construct the workers, and the number of workers is two. The specific neighborhood structures are as follows:

N1: Randomly select two different values in the genotype of the broods and exchange the two values.

N2: Randomly select three different values in the genotype of the broods, and the three values are completely arranged to generate five new individuals. Calculate the three objective function values (fuzzy makespan, spread of fuzzy makespan, and customer satisfaction) of the five new individuals. The non-dominated individuals are selected to replace the original broods, and if there are multiple non-dominated individuals, randomly select one as the new brood.

Based on the above strategy, workers can be compared to the local search process. The detailed steps are as follows:

Step 1: Set the maximum number of iterations of workers to improve broods in job shop scheduling system is LS_max, set t = 1.

Step 2: Randomly select a worker from the candidate worker bee w_i , $i \in {1, 2}$ . w_i is employed to improve brood τ, new brood τ' will be obtained after the improvement.

Step 3: If brood τ' can dominate brood τ, τ is replaced by τ'.

Step 4: Set t = t + 1, if $t < L S_{max}$ , go to step 2. Otherwise, the cultivation operation of workers is terminated.

MHBMO for uncertain job shop scheduling

The main steps of the proposed MHBMO for uncertain job shop scheduling are as follows:

Step 1: Initialize the parameters of MHBMO algorithm, including the number of iterations Gen_max, attenuation coefficient of queen’s velocity and energy α, energy threshold of the queen’s mating flight threshold, the capacity of queen’s spermatheca SperSize, number of honey bees PopSize, number of queens QueenSize, number of broods BroodSize, number of workers WorkerSize, and number of iterations of workers L _max.

Step 2: According to the output of the process planning system, randomly generate PopSize honey bees according to the method in the “Initial population and fitness evaluation” section. Each honey bee represents a scheduling scheme. Calculate the three objective function values represented by each honey bee. Clear the queens set, set Gen = 0.

Step 3: Initialization of drones population and queens set.

Step 3.1: Deposit non-dominated individuals in the current population into the queens set. If the number of non-dominated solutions in the current population is greater than the number of queens, then calculate the crowded distance of each individual in the non-dominated solution set and put the individuals with large crowding distance into the queens set. The calculation method of individual crowding distance can refer to the literature.⁵⁰

Step 3.2: Remove the QueenSize individuals deposited in the queen of bees from the colony. Randomly generate QueenSize individuals and add these individuals to the bee colony. At this time, PopSize individuals are used as drones population.

Step 4: Queen’s mating flight. Randomly select a bee from the queens set as the queen, initialize the speed and energy of the queen, and empty the queen’s spermatheca. Set a represent the number of drone genotypes in the queen’s spermatheca, set a = 0. Let t represent the number of flights of the queen, set t = 0. If the energy of queen $Energy (t) > threshold$ and $a < SperSize$ , repeat the following steps:

Step 4.1: Randomly select a drone from the population.

Step 4.2: Calculate the probability value of the drone mating with the queen bee by formula (22).

Because the first objective value for each individual in the current population is triangular fuzzy numbers, the second objective and the third objective values are real numbers, $Δ (f)$ is calculated by formula (25)

Δ (f) = \sqrt{d {({\tilde{Q}}_{f_{1}}, {\tilde{D}}_{f_{1}})}^{2} + {(Q_{f_{2}} - D_{f_{2}})}^{2} + {(Q_{f_{3}} - D_{f_{3}})}^{2}}

where $Q_{f_{i}}$ and $D_{f_{i}}$ represent the ith objective function value of the scheduling scheme represented by the queen bee and the drone, respectively. Randomly generate a real number between 0 and 1, if the real number is less than the calculation result of formula (22), deposit the genotype of the drone into queen’s spermatheca. Remove the drone from the drone colony. Set a = a + 1, otherwise, no operation is performed.

Step 4.3: Update the speed and energy of the queen according to formulas (23) and (24). Set t = t + 1.

Step 5: Broods generation. Randomly select a genotype from the queen’s spermatheca, and use the crossover operators in the literature²¹ to cross the queen to generate broods until BroodSize broods are generated.

Step 6: Improve the genotype of each brood using the operations designed in the “Improvement of broods by workers” section.

Step 7: Update queens set and drones population.

Step 7.1: Combine the original drones population and the broods population into a population P _temp, divide P _temp into non-dominated subpopulation F = {F1,…, Fi} by fast non-dominated sorting approach, calculate the density of each individual in the population based on immune principle presented in Luo et al.¹²

Step 7.2: Update queens set. Combine the individuals in F1 with the individuals in the queens set to generate temporary population and find out the non-dominated solutions in this temporary population. If the number of non-dominated solutions is greater than QueenSize, calculate the crowded distance of each individual in the non-dominated solution set and deposit the QueenSize individuals with the largest crowded distance into the queens set. If the number of non-dominated solutions is less than or equal to QueenSize, then directly deposit these non-dominated individuals into the queens set. Remove the individual deposited in the queens set from F1.

Step 7.3: Update drones population. Empty the current drones population, set $n_{0} = 0$ , i = 1.

Step 7.4: Randomly generate a real number between 0 and 1 as r_i , set $n_{i} = [|F_{i}| \times r_{i}]$ . If $n_{i} < DroneSize - \sum_{k = 0}^{i - 1} n_{k}$ , then, add n_i individuals with the lowest concentration in Fi to the drones population. Otherwise, select $DroneSize - \sum_{k = 0}^{i - 1} n_{k}$ individuals with the lowest concentration in Fi, set i = i + 1.

Step 7.5: If the current number of individuals in the drone population reaches DroneSize, go to step 8. Otherwise, return to step 7.4.

Step 8: The drone population is updated using the diversity maintenance strategy based on the immune principle proposed in Luo et al.¹²

Step 9: Gen = Gen + 1. Determine whether the algorithm termination criterion is satisfied, and the algorithm termination criterion is to reach the maximum number of iterations of the algorithm. If Gen < Gen_max, jump to step 4. Otherwise, output the final set of queens obtained from the scheduled population, each of which contains the process plans of each job and the final scheduling scheme.

Experiments and discussion

The above MHBMO algorithm for solving multi-objective uncertain IPPS problems is programmed by Visual C++. The computer performance of the running program is 2.0 GHz Core (TM) 2 Duo CPU, 2.00 GB memory. Two sets of multi-objective uncertain IPPS instances are designed in this article. The proposed MHBMO was utilized to solve the instances. The value λ of the diversity maintenance strategy based on the immune principle is set to 0.9, the non-dominated solution set size is set to 40, and the maximum number of iterations of the algorithm is set to 100. The algorithm termination criterion is that the current iterations number reaches the maximum iterations number of the algorithm. The algorithm parameters of other process planning and shop scheduling sections are shown in Table 1.

Table 1.

Parameters in MHBMO.

Parameters	Process planning	Scheduling
Number of iterations	Random [1,10]	100
Number of queens	1	10
Queens’ velocity and energy attenuation coefficient	0.90	0.90
Energy threshold of queens’ mating flight	0.0001	0.0001
Number of bees	100	200
Size of queen’ s spermatheca	50	100
Number of broods	50	100
Number of workers	5	2
Number of iterations of workers	20	10

MHBMO: modified honey bees mating optimization.

Experiment 1

Experiment 1 contains two instances (5 × 5, 10 × 5) of different scales. Among them, the processing information of the instance 5 × 5 (five jobs processed in five machines) is shown in Tables 2 and 3.

Table 2.

The process information of five jobs processed in five machines.

Jobs		Alternative machines and corresponding fuzzy processing time					Flexible process plans	Fuzzy due date
Jobs		M ₁	M ₂	M ₃	M ₄	M ₅	Flexible process plans	Fuzzy due date
Job 1	O ₂	(52, 57, 60)	(35, 40, 45)	(85, 88, 90)	(58, 62, 67)	(72, 77, 80)	O ₄-O ₅-O ₂-O ₃	(160, 180, 190, 196)
	O ₃	(5, 7, 10)	(8, 10, 12)	(8, 11, 15)	(8, 10, 13)	(3, 5, 8)	O ₅-O ₄-O ₂-O ₃
	O ₄	(90, 95, 97)	(70, 74, 80)	(73, 76, 82)	(65, 71, 75)	(89, 93, 97)	O ₃-O ₅-O ₂-O ₄
	O ₅	(19, 24, 29)	(13, 18, 23)	(16, 22, 27)	(23, 28, 33)	(22, 26, 32)	O ₄-O ₂-O ₅-O ₃
Job 2	O ₁	(80, 84, 89)	(72, 76, 80)	(62, 68, 74)	(93, 98, 102)	(80, 84, 89)	O ₁-O ₂-O ₄	(182, 190, 200, 214)
	O ₂	(15, 20, 25)	(7, 10, 13)	(12, 15, 18)	(17, 20, 23)	(16, 19, 23)	O ₁-O ₄-O ₂
	O ₄	(87, 91, 95)	(83, 88, 95)	(93, 98, 103)	(82, 87, 93)	(85, 90, 95)	O ₄-O ₂-O ₁
	O ₄	(87, 91, 95)	(83, 88, 95)	(93, 98, 103)	(82, 87, 93)	(85, 90, 95)	O ₂-O ₁-O ₄
Job 3	O ₁	(60, 65, 70)	(82, 87, 93)	(52, 58, 64)	(75, 80, 84)	(70, 74, 80)	O ₃-O ₅-O ₁-O ₄	(160, 180, 190, 196)
	O ₃	(42, 46, 54)	(17, 21, 26)	(33, 38, 43)	(48, 52, 57)	(13, 18, 24)	O ₁-O ₅-O ₃-O ₄
	O ₄	(13, 19, 24)	(18, 22, 27)	(12, 19, 23)	(9, 14, 19)	(16, 22, 28)	O ₁-O ₅-O ₆
	O ₅	(68, 73, 78)	(51, 56, 64)	(59, 64, 70)	(65, 72, 80)	(55, 60, 65)	O ₅-O ₃-O ₁-O ₄
	O ₆	(92, 96, 100)	(93, 98, 103)	(91, 96, 101)	(90, 95, 100)	(93, 98, 103)
Job 4	O ₂	(8, 13, 18)	(4, 7, 13)	(10, 13, 17)	(9, 12, 16)	(4, 11, 19)	O ₂-O ₃-O ₅-O ₄	(182, 190, 200, 214)
	O ₃	(46, 52, 58)	(59, 64, 69)	(92, 97, 103)	(42, 47, 53)	(35, 40, 45)	O ₃-O ₂-O ₅-O ₄
	O ₄	(15, 20, 25)	(25, 30, 35)	(12, 17, 23)	(5, 11, 16)	(9, 14, 19)	O ₅-O ₃-O ₂-O ₄
	O ₅	(89, 94, 99)	(61, 66, 69)	(75, 80, 84)	(74, 79, 83)	(91, 95, 100)	O ₄-O ₃-O ₅-O ₂
Job 5	O ₁	(89, 94, 99)	(92, 97, 103)	(50, 55, 60)	(73, 78, 83)	(80, 85, 90)	O ₄-O ₁-O ₃	(168, 200, 220, 243)
	O ₃	(25, 31, 37)	(17, 23, 28)	(14, 19, 24)	(37, 42, 47)	(12, 17, 23)	O ₄-O ₇
	O ₄	(83, 88, 93)	(62, 65, 67)	(71, 76, 85)	(59, 64, 69)	(75, 80, 85)	O ₄-O ₃-O ₁
	O ₇	(83, 88, 92)	(69, 74, 79)	(85, 90, 95)	(87, 92, 96)	(70, 75, 80)	O ₁-O ₄-O ₃

Table 3.

Fuzzy due date for 10 jobs in instance 10 × 5.

Jobs	Fuzzy due date	Jobs	Fuzzy due date
1	(140, 150, 160, 166)	6	(140, 150, 160, 166)
2	(152, 160, 170, 175)	7	(152, 160, 170, 175)
3	(164, 170, 180, 185)	8	(164, 170, 180, 185)
4	(170, 180, 190, 194)	9	(170, 180, 190, 194)
5	(178, 190, 200, 203)	10	(178, 190, 200, 203)

The first five jobs and the last five jobs of instance 10 × 5 are the same with jobs in instance 5. To verify the performance of the proposed MHBMO algorithm for solving multi-objective uncertain IPPS problems, NSGA-II-based optimization method was used to solve multi-objective uncertain IPPS problem in experiment 1 simultaneously, the optimization method is the same as the process described in the fourth section, but the shop scheduling part is optimized using the NSGA-II algorithm. The two algorithms run independently 20 times, and the performance of the two algorithms is evaluated using generation distance (GD) and inverse GD (IGD). The calculation results are shown in Table 4. The relationship between the fuzzy makespan and the fuzzy due date of the five jobs with the mean satisfaction degree of 0.475705 and 0.288272 is shown in Figures 5 and 6, respectively.

Table 4.

Computation results for experiment 1.

Problems	Evaluation indicators		MHBMO	NSGA-II
5×5	GD	Max	1.77943 × 10⁻²	1.83776 × 10⁻²
		Min	6.84552 × 10⁻³	1.08679 × 10⁻²
		Mean	1.411443 × 10⁻²	1.423315 × 10⁻²
	IGD	Max	1.09445 × 10⁻²	1.15245 × 10⁻²
		Min	8.0801 × 10⁻³	8.95728 × 10⁻³
		Mean	9.23527 × 10⁻³	1.008415 × 10⁻²
	119 non-dominated solutions were found, in which 74 were obtained by HBMO and 45 by NSGA-II.
10×5	GD	Max	1.58283 × 10⁻²	1.7565 × 10⁻²
		Min	5.05718 × 10⁻³	5.03527 × 10⁻³
		Mean	1.05982 × 10⁻²	1.133578 × 10⁻²
	IGD	Max	8.10472 × 10⁻³	1.34748 × 10⁻²
		Min	5.78362 × 10⁻³	5.8292 × 10⁻³
		Mean	6.68673 × 10⁻³	7.83223 × 10⁻³
	98 non-dominated solutions were found, in which 66 were obtained by HBMO and 32 by NSGA-II.

HBMO: honey bees mating optimization; MHBMO: modified honey bees mating optimization; GD: generation distance; IGD: inverse generation distance.

The bold-faced values indicate that the values obtained by MHBMO are better than the values obtained by NSGA-II.

Figure 5.

The completion status of five jobs when the average customer satisfaction is 0.475705 in non-dominated solutions of instance 5 × 5.

Figure 6.

The completion status of five jobs when the average customer satisfaction is 0.288272 in non-dominated solutions of instance 5 × 5.

Experiment 2

Experiment 2 contains three instances (instance 8 × 8, 10 × 10, and 15 × 10) of different scales. In the instance 8 × 8, the first five jobs have the same machining process and flexible process plans as five jobs of the instance 5 × 5 in experiment 1. The last three jobs have the same processing information as the last three jobs in the instance 5 × 5. Each operation has eight optional machines, in which the optional machine 1 to machine 5 of each process has the same fuzzy processing time as the five optional machines of instance 5 × 5 in experiment 1. The fuzzy processing time of the optional machine 6 to the optional machine 8 is the same as the fuzzy processing time of the optional machine 3 to machine 5 in instance 5 × 5. The fuzzy due date of the eight jobs is the same as the due date of the first eight jobs in instance 10 × 5. The 10 jobs in instance 10 × 10 have the same processing information as jobs in instance 10 × 5. Each job has 10 optional machines. The machine 1 to machine 5 has the same fuzzy processing time as the machine 1 to machine 5 of the jobs corresponding to instance 10 × 5. The fuzzy processing time of machine 6 to machine 10 is the same as the fuzzy processing time of machine 1 to machine 5. The fuzzy due date of the 10 jobs is the same as the fuzzy due date of the job in instance10 × 5. The first 10 jobs in instance 15 × 10 have the same machining information as the 10 jobs in instance 10 × 10. The last five jobs have the same machining information as the last five jobs in instance 10 × 10.The fuzzy delivery date of the first 10 jobs is the same as the fuzzy due date of 10 jobs in instance 10 × 10, and the fuzzy due date of the last five jobs is the same as the fuzzy due date of the last five jobs in the instance 10 × 10.

The MHBMO algorithm and the NSGA-II algorithm were used to solve the three different scale instances in experiment 2. Each algorithm runs 20 times independently. The performance of the two algorithms is evaluated by GD and IGD. The computation results are shown in Table 5.

Table 5.

Computation results for experiment 1.

Problem	Evaluation indicators		MHBMO	NSGA-II
8 × 8	GD	Max	1.88231 × 10⁻²	1.74619 × 10⁻²
		Min	7.39968 × 10⁻³	9.1553 × 10⁻³
		Mean	1.222024 × 10⁻²	1.307351 × 10⁻²
	IGD	Max	1.13012 × 10⁻²	1.23725 × 10⁻²
		Min	8.47599 × 10⁻³	8.35284 × 10⁻³
		Mean	9.36371 × 10⁻³	1.008737 × 10⁻²
	96 non-dominated solutions were found, in which 58 were obtained by HBMO and 38 by NSGA-II.
10 × 10	GD	Max	1.47163 × 10⁻²	1.59113 × 10⁻²
		Min	5.94302 × 10⁻³	7.56059 × 10⁻³
		Mean	9.75953 × 10⁻³	1.166546 × 10⁻²
	IGD	Max	7.61908 × 10⁻³	1.12717 × 10⁻²
		Min	6.13287 × 10⁻³	6.85037 × 10⁻³
		Mean	6.80766 × 10⁻³	8.229 × 10⁻²
	141 non-dominated solutions were found, in which 88 were obtained by HBMO and 55 by NSGA-II
15 × 10	GD	Max	1.09097 × 10⁻²	1.28108 × 10⁻²
		Min	7.15843 × 10⁻³	6.07453 × 10⁻³
		Mean	9.20077 × 10⁻³	8.83527 × 10⁻³
	IGD	Max	7.46994 × 10⁻³	9.85495 × 10⁻³
		Min	5.52359 × 10⁻³	6.23841 × 10⁻³
		Mean	6.66037 × 10⁻³	7.8177 × 10⁻³
	100 non-dominated solutions were found, in which 58 were obtained by HBMO and 42 by NSGA-II.

HBMO: honey bees mating optimization; MHBMO: modified honey bees mating optimization; GD: generation distance; IGD: inverse generation distance.

The bold-faced values in Table 5 indicate that the values obtained by MHBMO are better than the values obtained by NSGA-II.

Discussion

The computation results of the first example show that MHBMO can find more non-dominated solutions than NSGA-II in 20 independent running. At the same time, in the GD and IGD performance indicators, MHBMO is smaller than the NSGA-II in the maximum, minimum, and mean values. It can be seen intuitively from Figures 5 and 6 that when the average satisfaction is larger, there is a large intersection area between the fuzzy makespan of jobs and the fuzzy due date. It is shown that the customer satisfaction evaluation method designed in this article can guarantee the consistent evaluation results with the customer satisfaction evaluation method based on intersection area. The calculation results of experiments show that MHBMO can find more non-dominated solutions than NSGA-II in 20 independent running. Most of the maximum, minimum, and mean values of GD obtained by MHBMO algorithm are smaller than NSGA-II. All of the maximum, and mean values of IGD obtained by MHBMO algorithm are smaller than NSGA-II. In summary, MHBMO proposed in this article revealed better performance than NSGA-II in solving multi-objective uncertain IPPS problems. This proposed method can effectively solve multi-objective uncertain IPPS.

Conclusion and future works

This article has conducted in-depth research on the multi-objective uncertain IPPS problem. Based on the fuzzy set theory, a multi-objective uncertain IPPS problem model is established, which considers uncertain processing time and uncertain due date. The objectives of the fuzzy objectives and the uncertainty of the metric scheduling scheme are taken into account comprehensively. The related fuzzy number operations were used to realize the fitness evaluation, non-dominated relationship judgment, and scheduling decoding. As the lack of multi-objective uncertain IPPS problem instances, instances of different sizes for multi-objective uncertain IPPS problem were designed. The designed instances were solved using the optimization method based on MHBMO and the optimization method based on NSGA-II. The experimental results show that the proposed method in this article can effectively solve the multi-objective uncertain IPPS problem and demonstrate better performance than NSGA-II.

With the development of fuzzy mathematics, some new fuzzy numbers are gradually proposed. It is an important research direction to consider the use of new fuzzy numbers to more accurately describe the uncertainty in IPPS. On the other hand, some novel multi-objective optimization algorithms with better non-dominated solution set construction method and diversity maintenance strategy can be studies to solve multi-objective uncertain IPPS.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research work was supported by the National Natural Science Foundation of China (grant nos 51905494, 51825502, and 51775517), MOE (Ministry of Education in China) Project of Humanities and Social Sciences (grant no. 19YJCZH185), the Doctoral Program of Zhengzhou University of Light Industry (grant no. 2014BSJJ023), and the Open topic of the Henan Provincial Key Laboratory of Intelligent Manufacturing of Mechanical Equipment (grant no. IM201808).

ORCID iDs

Xiaoyu Wen

Xinyu Li

References

Gao

Wen

. Application of an efficient modified particle swarm optimization algorithm for process planning. Int J Adv Manuf Tech 2013; 67: 1355–1369.

Gao

, et al. An effective multi-objective algorithm for energy efficient scheduling in a real-life welding shop. IEEE Trans Ind Inform 2018; 14(12): 5400–5409.

Gao

. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. Int J Prod Econ 2016; 174: 93–110.

Gao

. Application of game theory based hybrid algorithm for multi-objective integrated process planning and scheduling. Expert Syst Appl 2012; 39: 288–297.

Kumar

Rajotia

. Integration of scheduling with computer aided process planning. J Mater Process Tech 2003; 138(1–3): 297–300.

Wang

Liu

. Underactuated robotics: a review. Int J Adv Robot Syst 2019; 16(4): 1–29.

Shao

Wang

, et al. Product environmental footprints assessment for product life cycle. J Clean Prod 2019; 233: 446–460.

Liu

Zeng

, et al. Product carbon footprint across sustainable supply chain. J Clean Prod 2019; 241:1–20.

Gao

Pan

, et al. An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop. IEEE Trans Syst Man Cybernetics Syst 2019; 49(10): 1933–1944.

10.

Gao

Shao

. An active learning genetic algorithm for integrated process planning and scheduling. Expert Syst Appl 2012; 39: 6683–6691.

11.

Shao

Gao

, et al. Integration of process planning and scheduling—a modified genetic algorithm-based approach. Comput Oper Res 2009; 36(6): 2082–2096.

12.

Luo

Wen

, et al. A multi-objective genetic algorithm based on immune principle and external archive for multi-objective integrated process planning and scheduling. Int J Adv Manuf Tech 2017; 91(9–12): 3145–3158.

13.

Sang

Pan

, et al. Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion. Swarm Evol Comput 2019; 44: 64–73.

14.

Wang

Liu

Jin

. A multi-objective evolutionary algorithm guided by directed search for dynamic scheduling. Comput Oper Res 2017; 79: 279–290.

15.

Srinivasan

Bonvin

Visser

, et al. Dynamic optimization of batch processes: II. Role of measurements in handling uncertainty. Comput Chem Eng 2003; 27(1): 27–44.

16.

Lei

. Fuzzy job shop scheduling problem with availability constraints. Comput Ind Eng 2010; 58(4): 610–617.

17.

Gao

Pan

, et al. A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution. Appl Soft Comput 2019; 75: 728–749.

18.

Gao

, et al. A multi-objective approach to welding shop scheduling for makespan, noise pollution and energy consumption. J Clean Prod 2018; 196: 773–787.

19.

Sang

Pan

Duan

, et al. An effective discrete invasive weed optimization algorithm for lot-streaming flowshop scheduling problems. J Intell Manuf 2018; 29(6): 1337–1349.

20.

Sang

Duan

. An effective invasive weed optimization algorithm for scheduling semiconductor final testing problem. Swarm Evol Comput 2018; 38: 42–53.

21.

Wen

Gao

, et al. Honey bees mating optimization algorithm for process planning problem. J Intell Manuf 2014; 25: 459–472.

22.

Jin

Zhang

Shao

. An effective hybrid honey bee mating optimization algorithm for integrated process planning and scheduling problems. Int J Adv Manuf Tech 2015; 80(5–8): 1253–1264.

23.

Chu

You

Wassick

, et al. Integrated planning and scheduling under production uncertainties: bi-level model formulation and hybrid solution method. Comput Chem Eng 2015; 72: 255–272.

24.

Jin

Tang

Zhang

, et al. More MILP models for integrated process planning and scheduling. Int J Prod Res 2016; 54(14): 1–16.

25.

Rietz

Alves

Braga

, et al. An exact approach based on a new pseudo-polynomial network flow model for integrated planning and scheduling. Comput Oper Re 2016; 76: 183–194.

26.

Aguirre

Papageorgiou

. Medium-term optimization-based approach for the integration of production planning, scheduling and maintenance. Comput Chem Eng 2018; 116: 191–211.

27.

. Sustainable manufacturing and remanufacturing management. Coventry: Springer, 2018, pp. 13–16.

28.

Dai

Tang

, et al. Energy-aware integrated process planning and scheduling for job shops. Proc Inst Mech Eng B J Eng Manuf 2015; 229(S1): 13–26.

29.

Zhang

Tang

Peng

, et al. A method for minimizing the energy consumption of machining system: integration of process planning and scheduling. J Clean Prod 2016; 137: 1647–1662.

30.

Zhang

Wong

. An object-coding genetic algorithm for integrated process planning and scheduling. Eur J Oper Res 2015; 244(2): 434–444.

31.

Zhang

Wong

. Solving integrated process planning and scheduling problem with constructive meta-heuristics. Inform Sciences 2016; 340–341: 1–16.

32.

Zhang

, et al. Combining extended imperialist competitive algorithm with a genetic algorithm to solve the distributed integration of process planning and scheduling problem. Math Probl Eng 2017; 2017(5): 1–13.

33.

Ausaf

Gao

. Optimization of multi-objective integrated process planning and scheduling problem using a priority based optimization algorithm. Front Mech Eng 2015; 10(4): 392–404.

34.

Jin

Zhang

Shao

, et al. A multi-objective memetic algorithm for integrated process planning and scheduling. Int J Adv Manuf Tech 2015; 85(5): 1–16.

35.

Zhang

Ong

Nee

AYC

. A simulation-based genetic algorithm approach for remanufacturing process planning and scheduling. Appl Soft Comput 2015; 37: 521–532.

36.

Manupati

Putnik

Tiwari

, et al. Integration of process planning and scheduling using mobile-agent based approach in a networked manufacturing environment. Comput Ind Eng 2016; 94: 63–73.

37.

Milica

Najdan

Marko

, et al. Integration of process planning and scheduling using chaotic particle swarm optimization algorithm. Expert Syst Appl 2016; 64: 569–588.

38.

Elahe

. Integrated multi-objective process planning and flexible job shop scheduling considering precedence constraints. Prod Manuf Res 2018; 6(1): 61–89.

39.

Seker

Erol

Botsali

. A neuro-fuzzy model for a new hybrid integrated process planning and scheduling system. Expert Syst Appl 2013; 40(13): 5341–5351.

40.

Liu

Qiu

. Application of ant colony optimization algorithm in integrated process planning and scheduling. Int J Adv Manuf Tech 2016; 84(1–4): 393–404.

41.

Xia

Gao

. A hybrid genetic algorithm with variable neighborhood search for dynamic integrated process planning and scheduling. Comput Ind Eng 2016; 102: 99–112.

42.

Zhang

Chen

, et al. Integration of process planning and scheduling using a hybrid GA/PSO algorithm. Int J Adv Manuf Tech 2015; 78(1–4): 583–592.

43.

Wen

Gao

, et al. A multi-objective genetic algorithm for integrated process planning and scheduling with fuzzy processing time. In: Proceedings of the sixth international conference on advanced computational intelligence, Hangzhou, China, 19–21 October 2013, pp. 293–298. Piscataway, NJ: IEEE.

44.

Wang

Gao

, et al. Application of interval theory and genetic algorithm for uncertain integrated process planning and scheduling. In: Proceedings of the 2013 IEEE international conference on systems, man, and cybernetics, Manchester, UK, 13–16 October 2013, pp. 2796–2801. Piscataway, NJ: IEEE.

45.

Liu

Zhou

Yang

. Minimizing energy consumption and tardiness penalty for fuzzy flow shop scheduling with state-dependent setup time. J Clean Prod 2017; 147: 470–484.

46.

Yin

. A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date using differential evolution algorithm. Int J Adv Manuf Tech 2011; 56(9–12): 1125–1138.

47.

Zadeh

. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets Syst 1978; 100(Suppl 1): 3–28.

48.

Fang

Ross

Corne

. A promising genetic algorithm approach to job-shop scheduling, rescheduling, and open-shop scheduling problems. In: Proceedings of the fifth international conference on genetic algorithms, Urbana, USA, 17–21 July, 1993, pp. 375–382. Morgan Kaufmann.

49.

Zhang

Rao

, et al. A new hybrid GA/SA algorithm for the job shop scheduling problem. Lect Notes Comput Sci 2005; 3448: 246–259.

50.

Deb

Pratap

Agarwal

, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 2002; 6(2): 182–197.

Modified honey bees mating optimization algorithm for multi-objective uncertain integrated process planning and scheduling problem

Abstract

Keywords

Introduction

Literature review

Problem formulation

Fundamental theory of fuzzy sets

Mathematical model for multi-objective uncertain IPPS

Evaluation method of customer satisfaction in uncertain IPPS

Proposed MHBMO for multi-objective uncertain IPPS

The basic principle of HBMO

The framework of the proposed method

HBMO for uncertain process planning

MHBMO for uncertain job shop scheduling

Initial population and fitness evaluation

Improvement of broods by workers

MHBMO for uncertain job shop scheduling

Experiments and discussion

Experiment 1

Experiment 2

Discussion

Conclusion and future works

Footnotes

Declaration of conflicting interests

Funding

ORCID iDs

References