A cross-entropy-based approach for joint process plan selection and scheduling optimization

Abstract

The process plan selection and job shop scheduling are carried out separately and sequentially in many factories and the scheduling is always conducted after the process plan of each job has been determined. In fact, the activities for the determination of process plan and the scheduling plan are coupled with each other and actually complementary. Implementation of the two activities with an appropriate collaborative approach is essential to achieve greater performance and higher productivity for the manufacturing system. In this article, a novel cross-entropy-based approach for the joint process plan selection and scheduling optimization that can assist process planning and scheduling system to achieve optimal scheduling plan and determine the operations, machine for each operation and operation sequence for each job collaboratively was proposed. In order to facilitate the manipulation and improve the optimized performance of the approach, an efficient representation scheme and a generation method for samples were developed. Meanwhile, the updating mechanism for new introduced probability distribution parameters according to which the cross-entropy procedure generates samples was established. To verify the adaptability and performance of the proposed approach, experimental studies were conducted and comparisons were made between this approach and some previous methods. The experimental results indicate that the proposed approach is an alternative and acceptable method to solve the joint process plan selection and scheduling optimization problem.

Introduction

Manufacturing process planning (PP) and job shop scheduling are two pivotal planning steps which can greatly affect the performance of manufacturing systems. PP links product design and product manufacturing by specifying what resources are needed to produce a job and determining detailed instructions for transforming raw materials into the final product. ¹ The selection of process plan as the inevitable step of flexible PP mainly includes the determination of operations, machine for each operation and operation sequence. With the selected process plans of jobs as inputs, the main task of scheduling is to assign operations of all the jobs on available machines with precedence relations defined in the process plans satisfied to optimize some predefined objectives.^1,2 Therefore, the selection of process plan as an important task of PP and scheduling are coupled with each other and actually complementary.

A PP system should interface with a scheduling system to generate more appropriate process and scheduling plans. In doing so, the efficiency of manufacturing system as a whole is expected to be improved. ³ In recent years, numerous efforts have been made to the research and application of integrated process planning and scheduling (IPPS) system, especially for the important and challenging problem of joint process plan selection and scheduling optimization (JPPSSO).^4–7 The joint implementation mechanisms indicate that the IPPS can introduce significant improvement to the efficiency of the manufacturing facilities through elimination or reduction in scheduling conflicts, reduction in flow-time and work-in-process, improvement of production resources utilization and adaptation to irregular shop floor disturbances. ⁴ Therefore, it is ideal to integrate the PP and scheduling more tightly and implement the process plan selection and scheduling optimization jointly to increase the productivity and responsiveness of the manufacturing systems. ⁷

The JPPSSO problem that is always directly referred as IPPS in many other papers is very different from the PP and the scheduling problem. Because the objectives are different, meanwhile, the constraints and the solution space of JPPSSO are more complicated than the PP problem and the scheduling problem. ⁶ The previous approaches for the scheduling cannot be utilized to solve the JPPSSO problem; therefore, several approaches have been developed to facilitate the optimization of the integrated problem. Some earlier work of IPPS had been summarized by Phanden et al. ⁸ The algorithm-based and agent-based methods are the two main optimization approaches for IPPS.

Due to their advantages in solving combinatorial optimization problems, meta-heuristic algorithms, mainly including the simulated annealing (SA), ⁹ genetic algorithm (GA), ¹⁰ object-coding GA, ¹¹ particle swarm optimization (PSO),^12,13 imperialist competitive algorithm (ICA), ¹ tabu search (TS) ¹⁴ and evolutionary algorithm (EA)-based approach,^2,5,6,15,16 have been utilized for the IPPS problem in the past few years. Meanwhile, the pattern search, GA, and SA have also been employed for the integrated problem considering energy consumption. ¹⁷ The hybrid approaches of graph-based ant colony (AC), ¹⁸ simulation-based GA, ¹⁹ combination of GA with TS, ⁷ game theory, ²⁰ active leaning ²¹ and PSO ²² have also been established for the problem.

Agent-based approach is another important implementation method for the problem. Wong and colleagues^23–25 developed an online hybrid agent and an online multi-agent approach to integrate PP with scheduling/rescheduling. Leung et al. ²⁶ combined an AC algorithm in the agent-based system to facilitate the integration of PP and scheduling. Shukla et al. ²⁷ conceptualized a bidding-based multi-agent system for the IPPS problem. Li et al. ⁷ utilized job agent, machine agent and optimization agent to identify manufacturing operations, machine for each operation and scheduling plan simultaneously. Ueda et al. ²⁸ introduced a multi-agent learning-based approach for the IPPS. Hsieh and colleagues^29,30 developed an integrated system considering the integration of PP and scheduling-based multi-agent architecture. Shen et al. ³¹ gave a comprehensive review for the agent-based approaches for PP, scheduling and the integration of the two.

These studies excluded the generation of flexible process plans while conducting PP and mainly focus on the JPPSSO optimization. In this article, a novel cross-entropy (CE)-based approach has been developed to tackle the JPPSSO problem. The CE-based method^32,33 as an effective approach for the combinatorial optimization problems has not yet been employed for the JPPSSO or IPPS problem to our best knowledge. The contributions of the proposed CE-based approach in this article are summarized below:

• The CE has been employed to optimize many combinatorial problems with one decision variable (vector). However, in this article, the systematic mechanisms including probability distribution design and updating, sample encoding/decoding and generation have been developed for the optimization of JPPSSO problem with two sub-problems (decision vectors) should be considered cooperatively.

• This approach supports intelligent decision making for the selection of process plan for each job and optimal scheduling plans from the view of manufacturing system collaboratively.

• Experimental studies have been conducted and comparisons have been made between CE and some previous methods. The experimental results indicate that the algorithm is effective and it demonstrates potential applicability in practice.

Proposed CE-based approach for JPPSSO

Problem description

The JPPSSO discussed in this article is stated as follows: given a set of N jobs which are to be processed on M machines with alternative operation sequences and alternative machines for operations, determine an operation sequence and corresponding machine sequence for each job and a schedule in which operations on the same machines are processed so that it satisfies the precedence requirements and the corresponding objectives can be achieved.

The scheduling in the JPPSSO is often assumed as the job shop scheduling problem (JSP). The optimization objective of the joint problem in this article is to minimize makespan. The following assumptions are made: ³²

1. Job preemption is not allowed and each machine can handle only one job at a time;

2. All jobs are simultaneously available at time zero;

3. Different operations of one job cannot be processed simultaneously;

4. After a job is processed on a machine, it is immediately transported to the next machine;

5. Setup times for the operations on machines are independent of operation sequence and are included in the processing time.

The mixed integer programming model of JPPSSO problem the same as IPPS has been given by the previous work. ³² The JPPSSO that is more complicated than the JSP is a non-deterministic (NP)-hard problem, no polynomial time algorithm exists to find optimal solutions. Therefore, a CE-based meta-heuristic approach was developed to tackle the problem.

Flow chart of CE for JPPSSO

The CE algorithm which is known as efficient method for the combinatorial optimization problems was first proposed by Rubinstein. ³³ The application of CE-based approach is verified by its capability and simplicity to extract a subset solutions satisfying the predefined quality criterion from the large space of all samples (feasible solutions) generated randomly. The probability distribution according to which the CE procedure generates samples assures both their quality and diversity necessary for the further optimization iteration. ³⁴ The basic procedure of the proposed CE-based method for JPPSSO is described as follows:

Procedure of the proposed CE for JPPSSO
Step 1. Set the parameters (except the probability distribution parameter) of the algorithm.
Step 2. Select s process plans for each job. For the job has only $s\prime$ $(s\prime <s)$ different process plans, then copying exist process plans should be conducted to ensure each job has the same s plans passed on to scheduling.
Step 3. Construct the representation for samples.
Step 4. Design and introduce probability distribution based on the representation of samples.
Step 5. Generate the samples randomly based on the probability distribution.
Step 6. Decode and calculate the performance function values of all the samples.
Step 7. Is the termination criteria satisfied?
If yes, go to Step 10. Else, go to Step 8.
Step 8. Update probability distribution parameters.
Step 9. Regenerate samples randomly based on the updated probability distribution, and go to Step 6.
Step 10. Output the optimal sample (solution).

The process plan selection, sample representation, probability distribution designing, probability distribution parameter updating, sample generating and decoding are described in the following sections.

Process plans selection

Taking all the process plans for the joint optimization problem will seriously influence the computational efficiency when each job has large number of alternative process plans; even more, the advantage gained by increasing the number of alternative process plans for a scheduling system diminishes rapidly. ³² The experimental results obtained by modified GA, ⁵ hybrid Algorithm (HA) ⁶ and improved GA ³² also indicates the effectiveness by determining a number of optimal or near optimal process plans for each job before the joint optimization of process plan and scheduling plan. Therefore, the proposed CE-based approach tries to select s (near) optimal process plans based on their production time before joint optimization.

AND/OR network is a widely used^1,4,32 and also been utilized in this article to represent the flexible process plans. Based on the AND/OR flexible process plan network, the selection procedure parses and generates many process plans according to the initial selection method described by Qiao and Lv. ³² These parsed process plans are sorted based on their production time in a non-decreasing order, and then the first s process plans are transferred into the joint optimization procedure. The initial selection method mainly includes three steps: parse the OR-link and AND-link path in AND/OR network to construct linear process plan with each operation choosing the shortest production time (including the processing time and transportation time) among its alternatives, and then adjust positions of nodes in AND-link paths randomly but satisfying the constraints, select operations to adjust its machine among its alternatives randomly and associate the related processing time and transportation time accordingly. ³² For the job with few alternative process plans, all the process plans can be passed on to scheduling system. For each selected process plan, the detailed information including the operations, the machine for each operation and operation sequence has been determined.

Sample representation

CE algorithm takes every possible solution of a combinatorial optimization problem as a sample. The representation of samples that can match well with the discussed problem can facilitate the designing and manipulation of the algorithm. In this article, a representation structure consisting of process plan section and scheduling plan section, two parts, has been constructed to represent the sample for the JPPSSO problem. The position of 1 to N in the process plan section of a sample represents the job from 1 to N, in which the ith position represents the selected alternative process plan (from the s inputted process plans) for job i. The scheduling plan section consists of the permutation of integer number corresponding to the operations in the chosen process plans for all the jobs and the length is set to $L=\sum _{i=1}^N{u}_i$ , where u_i is the maximum operation number among all the alternative process plans of job i. The integer number opn between $[\sum _{i=1}^n{u}_i,\sum _{i=1}^{n+1}{u}_i]$ in the cell of scheduling plan section indicates the $\mathrm{opn}-\sum _{i=1}^n{u}_i,(1\le \mathrm{opn}\le \sum _{i=1}^n{u}_i)\mathrm{th}$ operation in the selected process plan of job n + 1.

Figure 1 shows a feasible sample. In this example, the number of job N is equal to 3 and therefore the process plan section is made up of three elements. Assume the maximum operation number among the process plans for the three job is $u_1=4,u_2=4,u_3=3$ , respectively, then the scheduling plan section is made up of 11 elements. The process plan section in the sample indicates that Jobs 1, 2 and 3 select the first, third and second process plan from their s inputted process plans, respectively. The numbers 1–4, 5–8 and 9–11 in the scheduling plan section represent the first to fourth, first to fourth and the first to third operations in the selected process plan of jobs 1, 3 and 2, respectively.

Figure 1.

Instance of a sample.

Probability distribution designing and updating

The probability distribution according to which the CE procedure generates samples is closely related to the sample representation. Based on the sample structure, the process plan section and scheduling plan section in a sample can be represented by two random integer vectors $\mathbf{Y}=\{y_1,\dots ,y_i,\dots .y_N\}$ and $\mathbf{X}=\{x_1,\dots ,x_{\nu },\dots .x_L\}$ , respectively. The corresponding deterministic vectors are represented as y and x, respectively. The elements in Y are independent discrete variables in [1, s], and then a probability distribution parameters (matrix) ${\mathbf{p}}_{\alpha }=\{p_{\alpha ,\mathrm{ij}}|1\le i\le N,1\le j\le N\}$ is constructed to generate elements of Y, in which $p_{\alpha ,\mathrm{ij}}$ represents the probability of job i, $1\le i\le N$ selecting the jth, $1\le j\le s$ , process plan. The probability density function (PDF) with parameters ${\mathbf{p}}_{\alpha }$ is denoted by $f(·;{\mathbf{p}}_{\alpha })$ ; thus, the probability distribution of Y can be written as $\mathbf{Y}~f(Y;{\mathbf{p}}_{\alpha })$ . Similarly, the elements in X are discrete variables in [1, L], and the probability distribution of X is described as $\mathbf{X}~f(\mathbf{X};{\mathbf{p}}_{\beta })$ by introducing the probability distribution parameters ${\mathbf{p}}_{\beta }=\{p_{\beta ,\mu \nu }|1\le \mu \le L,1\le \nu \le L\}$ , in which $p_{\beta ,\mu \nu }$ is utilized to record the probability of the integer number ν at the position µ in the scheduling plan section of a sample.

The JPPSSO schemes represented by samples are determined by Y and X jointly, and then the optimization problem can be transformed into the following problem

$$S({\mathbf{x}}^{*},{\mathbf{y}}^{*})={\gamma }^{*}=\underset{y||x\in \chi }{min}S(\mathbf{x},\mathbf{y})$$

(1)

where χ is the space of all the combination for the JPPSSO problem, S is the real-value performance function (its value is the makespan) in χ, $y||x$ represents a scheme consisting of y and x and $\gamma *$ is the minimum of S.

For certain $\mathbf{p}{\prime }_{\alpha }$ , $\mathbf{p}{\prime }_{\beta }$ , equation (1) is associated with the problem of estimating the number

$$\ell (\gamma )=P_{{p\prime }_{\alpha },{p\prime }_{\beta }}(S(\mathbf{X},\mathbf{Y})\le \gamma )=E_{{\mathbf{p}\prime }_{\alpha },{\mathbf{p}\prime }_{\beta }}{I}_{\{S(\mathbf{X},\mathbf{Y})\le \gamma \}}$$

(2)

where $P_{{\mathbf{p}\prime }_{\alpha },{\mathbf{p}\prime }_{\beta }}$ is the probability measure under which the random vector X, Y has PDF $f(·;\mathbf{p}{\prime }_{\alpha })$ and $f(·;\mathbf{p}{\prime }_{\beta })$ , respectively, and $E_{{\mathbf{p}\prime }_{\alpha },{\mathbf{p}\prime }_{\beta }}$ denotes the expectation operator, $\{I_{\{S(\mathbf{X},\mathbf{Y})\le \gamma \}}\}$ (0 or 1) is defined as a collection of indicator function on χ for various levels γ, $\gamma \in \mathbb{R}$ .

For deterministic $\gamma =\gamma *$ , parameter ${\mathbf{p}}_{\alpha }^{*}$ , ${\mathbf{p}}_{\beta }^{*}$ can be estimated using the likelihood ratio estimator as

$${{\hat{\mathbf{p}}}_{\alpha }}^{*}=\underset{{\mathbf{p}}_{\alpha }}{\arg max}\frac{1}{Z}\sum _{z=0}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \}}\ln f({\mathbf{Y}}_z;{\mathbf{p}}_{\alpha })$$

(3)

$${\hat{\mathbf{p}}}_{\beta }^{*}=\underset{{\mathbf{p}}_{\beta }}{\arg max}\frac{1}{Z}\sum _{z=0}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \}}\ln f({\mathbf{X}}_z;{\mathbf{p}}_{\beta })$$

(4)

where Z is the sample size, ${\mathbf{Y}}_z$ , ${\mathbf{X}}_z$ , $z=1,\dots ,Z$ is part of the sample in ${\mathbf{Y}}_z\mathbf{|}\mathbf{|}{\mathbf{X}}_z$ . With a specific x and y, the PDF of x can be described as $f(\mathbf{x};{\mathbf{p}}_{\beta })={\Pi }_{\mu =1}^L\underset{\nu =1}{\overset{L}{\Pi }}{p}_{\beta ,\mu \nu }^{I_{\{x_{\mu }=\nu \}}}$ , therefore the logarithm of $f(\mathbf{x};{\mathbf{p}}_{\beta })$ can be described as

$$\ln f(\mathbf{x};{\mathbf{p}}_{\beta })=\sum _{\mu =1}^L\sum _{\nu =1}^L{I}_{\{x_{\mu }=\nu \}}\ln p_{\beta ,\mu \nu }$$

With the extra condition that the row of ${\mathbf{p}}_{\beta }$ needs to add up to 1, the maximization problem can be obtained using Lagrange multipliers ${\omega }_1,\dots ,{\omega }_L$

$$\begin{array}{c}\multicolumn{1}{c}{\underset{p_{\beta }}{max}\underset{{\omega }_1,\dots ,{\omega }_L}{min}}\\ \multicolumn{1}{c}{[E_{{\mathbf{p}}_{\beta },{\mathbf{p}}_{\alpha }}{I}_{\{S(\mathbf{x},\mathbf{y})\le \gamma \}}\ln f(\mathbf{x};{\mathbf{p}}_{\beta })+\sum _{\mu =1}^L{\omega }_{\mu }(\sum _{\nu =1}^L{p}_{\beta ,\mu \nu }-1)]}\end{array}$$

On this basis, the corresponding estimator ${\hat{p}}_{\beta ,\mu \nu }$ , $\mu =1,\dots ,L,\nu =1,\dots ,L$ , ${\hat{p}}_{\alpha ,\mathrm{ij}}$ of $p_{\alpha ,\mathrm{ij}}$ , $i=1,\dots ,N,j=1,\dots ,s$ are

$${\hat{p}}_{\beta ,\mu \nu }=\frac{\sum _{z=1}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \}}{I}_{\{{\mathbf{X}}_{z\mu }=\nu \}}}{\sum _{z=1}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \}}}$$

(5)

$${\hat{p}}_{\alpha ,\mathrm{ij}}=\frac{\sum _{z=1}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \mathbf{\}}}{I}_{\{Y_{\mathrm{z}i}=j\}}}{\sum _{z=1}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \}}}$$

(6)

where $\sum _{z=1}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \}}$ is the number of samples with makespan less than γ, and $\sum _{z=1}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \}}{I}_{\{{\mathbf{X}}_{z\mu }=\nu \}}$ is the number of samples with makespan less than γ taking into account those samples that have the number ν located at the position µ. $\sum _{z=1}^Z{I}_{\{S({\mathbf{X}}_z,{\mathbf{Y}}_z)\le \gamma \}}{I}_{\{{\mathbf{Y}}_{\mathrm{z}i}=j\}}$ is the number of samples with makespan less than γ considering those samples that have job i choosing the jth process plan from the s available alternatives.

In order to smooth out the parameter ${\mathbf{p}}_{\alpha }$ and ${\mathbf{p}}_{\beta }$ in each iteration, the smooth parameter η is introduced and the smoothed updating expressions are defined as follows

$${\hat{\mathbf{p}}}_{\beta t}=\eta {\hat{\mathbf{p}}}_{\beta t}+(1-\eta ){\hat{\mathbf{p}}}_{\beta t-1}$$

(7)

$${\hat{\mathbf{p}}}_{\alpha t}=\eta {\hat{\mathbf{p}}}_{\alpha 6}+(1-\eta ){\hat{\mathbf{p}}}_{\alpha t-1}$$

(8)

where ${\hat{\mathbf{p}}}_{\beta t}$ and ${\hat{\mathbf{p}}}_{\alpha t}$ obtained by equations (5) and (6) at the tth iteration are the estimators of ${\mathbf{p}}_{\beta t}$ and ${\mathbf{p}}_{\alpha t}$ , respectively; while ${\hat{\mathbf{p}}}_{\beta t-1}$ and ${\hat{\mathbf{p}}}_{\alpha t-1}$ are the estimators of ${\mathbf{p}}_{\beta t-1}$ and ${\mathbf{p}}_{\alpha t-1}$ at the (t − 1)th iteration, respectively.

Sample generating

The following two algorithms will introduce the procedure of generating random samples, which consist of Y and X, based on the two probability distribution parameters ${\mathbf{p}}_{\alpha }$ and ${\mathbf{p}}_{\beta }$ .The algorithm of generating $\mathbf{Y}=\{y_1,\dots ,y_i,\dots .y_N\}$ based on ${\mathbf{p}}_{\alpha }$ is stated as follows.

Procedure of generating Y
Step 1. Set i = 1, normalize ${\mathbf{p}}_{\alpha }$ and make sure the sum of elements in each row equals to 1.
Step 2. Generate a double number r, $r\in [0,1]$ randomly, and get the least t with $\sum _{j=1}^t{p}_{\alpha ,\mathrm{ij}}\ge r$ , then $y_i=t$ .
Step 3. If $i<N$ , $i=i+1$ , return to Step 2; otherwise, set $\mathbf{Y}=\{y_1,\dots ,y_i,\dots .y_N\}$ and terminate.

The composition technique used to generate trajectory proposed by Rubinstein and Kroese, ³³ which prove that the method can speed up substantially the generation while affecting very little the accuracy of the CE algorithm, is modified to generate X as follows:

Procedure of generating X
Step 1. Set µ = 1.
Step 2. Normalize the µth row of ${\mathbf{p}}_{\beta }$ and assure the sum of elements in the row equals to 1.
Step 3. Divide the columns with non-zero elements in the µth row into three groups, denoted $\Omega (\psi ),\psi =1,2,3$ so that each $p_{\beta ,\mu \nu }$ with $\nu \in \Omega (1)$ is $p_{\beta ,\mu \nu }<1/L$ , each $p_{\beta ,\mu \nu }$ with $\nu \in \Omega (2)$ is $1/L\le p_{\beta ,\mu \nu }\le 2/L$ , and each $p_{\beta ,\mu \nu }$ with $\nu \in \Omega (3)$ is $1\ge p_{\beta ,\mu \nu }>2/L$ . Associate the ordered elements in $\Omega (1)$ with $\{1,\dots ,{\tau }_1\}$ ; $\Omega (2)$ with
$\{{\tau }_1+1,\dots ,{\tau }_1+{\tau }_2\}$ , $\Omega (3)$ with $\{{\tau }_1+{\tau }_2+1,\dots ,L-\mu \}$ . Calculate ${\delta }_{\psi }=\sum _{\nu \in \Omega (\psi )}{p}_{\beta ,\mu \nu }$ , $\psi =1,2,3$ , and ${\delta }_1+{\delta }_2+{\delta }_3=1$ , for $\nu \notin \Omega (\psi ),\psi =1,2,3$ , $p_{\beta ,\mu \nu }=0$ .
Step 4. Reduce the difference between the probabilities for $\Omega (1)$ and $\Omega (2)$ by making them equal within each group, while the elements in $\Omega (3)$ remain untouched.
Step 5. Define a new discrete PDF ϕ on {1, 2, 3} with $\phi (\psi )={\delta }_{\psi }$ , $\psi =1,2,3$ .
Step 6. Define two new discrete PDFs $h_1(\sigma )$ , $h_2(\sigma )$ , which are uniformly distributed on $\{1,\dots ,{\tau }_1\}$ and $\{{\tau }_1+1,\dots ,{\tau }_1+{\tau }_2\}$ , respectively. Meanwhile, define a new $L-\mu -{\tau }_1-{\tau }_2$ point discrete PDF $h_3(\sigma )$ , on ${\mathrm{es}}_{\mathrm{ik}}$ that is associated with the original probabilities of the numbers in $\Omega (3)$ .
Step 7. Generate a random x with the outcomes 1, 2, 3 from ${\mathrm{as}}_{\mathrm{ik}}$ . Given $x=\psi$ , then generate a random variable r, $r\in [1,L-\mu ]$ from the corresponding PDF $h_x(\sigma )$ . Let $x_{\mu }$ be the column number ν of ${\mathbf{p}}_{\beta }$ that is matched to r.
Step 8. If $\mu <L$ , set $\mu =\mu +1$ , $p_{\beta ,\mu \prime x_{\mu }}=0,\mu \le \mu \prime \le L$ , return to Step 2; otherwise, set $\mathbf{X}=\{x_1,\dots ,x_{\mu },\dots .x_L\}$ , terminate.

Sample decoding

A sample can be scheduled only if the constraints have already been satisfied. In a sample, the operation precedence restriction is neglected at the generating stage and feasibility is ensured by the following decoding procedure. In the decoding process, a fixed alternative process plan for each job is given; therefore, the detailed information (operation, machine and the processing time) for each cell in the scheduling plan section based on the selected process plans has also been determined. If the number of operations (denoted by $q_i$ ) in the chosen process plans of job i, $i\in [1,N]$ is less than $u_i$ , then the detailed information of $(q_i+1)\mathrm{th}$ to $u_i\mathrm{th}$ operation in the selected process plan are filled with 0. The notations used to explain the procedure are described below.

• $o_{\mathrm{ik}}$  kth operation of job i;

• ${\mathrm{es}}_{\mathrm{ik}}$  earliest starting time of $o_{\mathrm{ik}}$ ;

• ${\mathrm{pt}}_{\mathrm{ik}}$  processing time of $o_{\mathrm{ik}}$ ;

• ${\mathrm{ec}}_{\mathrm{ik}}$  earliest completion time of $o_{\mathrm{ik}}$ ;

• ${\mathrm{as}}_{\mathrm{ik}}$  allowed starting time of $o_{\mathrm{ik}}$ .

Sample decoding
Step 1. Construct an operation set with the first operations in the chosen process plan for all the jobs as $A:=\{o_{i1}|i\in [1,N]\}$ based on the sample and set ${\mathrm{ac}}_{i1}=0,{\mathrm{es}}_{i1}=0,i\in [1,N]$ .
Step 2. Determine $o_{\mathrm{ik}}$ with its number in the left-most position of X among all the positions corresponding to the operations in A and obtain the machine m on which $o_{\mathrm{ik}}$ performed.
Step 3. Scheduling $o_{\mathrm{ik}}$
Step 3.1. Compute the allowable starting time of $o_{\mathrm{ik}}$ as $a{s}_{\mathrm{ik}}=e{c}_{i(k-1)}+\mathrm{tp}(m\prime ,m)$ , where ${\mathrm{ec}}_{i(k-1)}$ is the completion time of the pre-operation of $o_{\mathrm{ik}}$ from the same job, and $m\prime$ is the machine on which $o_{(k-1)}$ manufactured.
Step 3.2. Check if there exists idle area $[i\_s,i\_\mathrm{e}]$ for $o_{\mathrm{ik}}$ in turn, if there is $max({\mathrm{as}}_{\mathrm{ik}},i\_s)+{\mathrm{pt}}_{{}_{\mathrm{ik}}})\le i\_e$ , then set ${\mathrm{es}}_{\mathrm{ik}}=max({\mathrm{as}}_{\mathrm{ik}},i\_s)$ , ${\mathrm{ec}}_{\mathrm{ik}}={\mathrm{es}}_{\mathrm{ik}}+p_{\mathrm{ik}}$ ; otherwise, ${\mathrm{es}}_{\mathrm{ik}}=max({\mathrm{as}}_{\mathrm{ik}},t_m(o_{i_1{k}_1}))$ ( $o_{i_1{k}_1}$ is the pre-operation of $o_{\mathrm{ik}}$ performed on the same machine m, and $t_m(o_{i_1{k}_1})$ is the available time of machine m equals to the completion time of $o_{i_1{k}_1}$ ). If ${\mathrm{as}}_{\mathrm{ik}}\ge t_m(o_{i_1{k}_1})$ , set ${\mathrm{ec}}_{\mathrm{ik}}={\mathrm{as}}_{\mathrm{ik}}+{\mathrm{pt}}_{\mathrm{ik}}$ , $t_m={\mathrm{ec}}_{\mathrm{ik}}$ (the available time of m) and add a new idle area $[i\_s,i\_\mathrm{e}]=[t_m(o_{i_1{k}_1}),{\mathrm{as}}_{\mathrm{ik}}]$ for m; otherwise, set ${\mathrm{ec}}_{\mathrm{ik}}=t_m(o_{i_1{k}_1})+p_{\mathrm{ik}}$ , $t_m={\mathrm{ec}}_{\mathrm{ik}}$ .
Step 4. Update $A:=A/\{o_{\mathrm{ik}}\}$ . Check $o_{\mathrm{ik}}$ , if it has valid (with non-zero detailed information) succeed operation $o_{i(k+1)}$ in the selected process plans, set $A:=A\cup \{o_{i(k+1)}\}$ .
Step 5. Check A, if $A=\varnothing$ , terminate; otherwise, return to Step 2.

Experimental studies and discussions

The proposed CE algorithm procedure is coded in JAVA and implemented on a Dell Precision T7400. To illustrate the effectiveness and performance of the proposed approach, four sets of experiments are carried out. The smooth parameter η is found empirically that a value η between $0.3\le \eta \le 0.9$ gives good results; the quantile parameter ρ is suggested to take a larger ρ say, $\rho =\ln L/L$ ; the sample size Z is suggested to take as $N=\mathrm{cL}(5\le c\le 10)$ ; termination parameter d is set to 5–10 in general. ³² In this article, the parameters set as $\rho =0.1,Z=500,d=5$ for the instance in Experiments 1–3; the parameters in Experiment 4 are set as $\rho =0.1,Z=9\times L,d=8$ based on initial test. The parameter η with a wide value range is important for the experimental result according to our experience. In order to determine a more reasonable value among its range $[0.3,0.9]$ , some comparative experiments based on the problems in experiment 3 will be conducted and analyzed, and the $\eta =0.8$ is finally selected as the preferred value in this article for all the problems.

The best solution (with minimized makespan) obtained at each run was taken. For computational comparisons, each test-bed problem was repeated five times. The computational times are the mean times of all five independent runs recorded. In this article, The Gantt chart is utilized to illustrate the scheduling results. In the Gantt chart, the notations out of the parentheses in each block represent the operation of a job and the notations in the parentheses indicate the completion time of the operation. The selected process plan of each job can also been determined easily based on the notations in each block and the precedence relations of the blocks.

Experiment 1

In this Experiment, three problems are taken from the literature to compare the performance of the proposed CE with that of other approaches. The data of problem 1 is constructed with six jobs and eight machines designed by Shao et al. ⁴ Each job has nine operations in its process plan network. Problem 2 is constructed with 10 jobs and nine machines. ³⁶ The data of problem 3 are constructed with six jobs and five machines. ⁵ The parameter s of CE is set to 4 for problems 1 and 2 based on some initial test. All the process plans of each job are passed on to the joint optimization for problem 3. The makespan values for these problems obtained by the proposed CE and methods in the literature are listed in Table 1. The values with bold type are used to emphasize the better computational results our proposed CE-based method achieved. Figures 2–4 illustrate the Gantt chart of the three problems in Experiment 1. The results indicate that the proposed CE-based method can obtain better result.

Table 1.

Computational results of Experiment 1.

Pb	n × m	Re	Approach	Makespan	CPU time (s)
1	6 × 8	4	MGA	162	_
		4	HIA	250	_
			CE	155	10.6
2	10 × 9	35	GA	6456	_
		23	oHAN	6574	_
		33	IGA	5268	_
			CE	5210	18.1
3	6 × 5	18	EA	92	_
		18	No integration	102	_
			CE	91	8.4

Pb: problem; Re: reference; n and: the total number of job and machine, respectively; –: data are not given in the Re; CE: cross-entropy; GA: genetic algorithm; EA: evolutionary algorithm; MGA: Modified Genetic Algorithm HIA: Hierarchical Approach oHAN: Online Hybrid Agent-based Negotiation IGA: Improved Genetic Algorithm.

Figure 2.

Gantt chart of problem 1 with CE (makespan = 155).

Figure 3.

Gantt chart of problem 1 with CE (makespan = 5210).

Figure 4.

Gantt chart of problem 3 with CE (makespan = 91).

Experiment 2

The data of Experiment 2 which is constructed with six jobs and six machines by Saygin and Kilic, ³⁷ job-related information and alternative machines for each operation of the jobs are given in Table 2. The number s for Experiment 2 is set to 8 based on some initial experiments.

Table 2.

Job-related information and alternative machines for each operation of Experiment 2.

Job	Process plan	Operation	Alternative machine(processing time)
1	1	1	1 (8) or 2 (12)
		2	3 (17) or 4 (11)
		3	3 (4) or 6 (6)
	2	1	3 (14) or 4 (18)
		2	5 (4)
		3	3 (6) or 4 (5)
2	1	1	4 (6)
		2	6 (4)
		3	1 (6) or 2 (10)
		4	5 (4) or 6 (6)
	2	1	4 (6)
		2	5 (3) or 6 (4)
		3	1 (9)
		4	6 (4)
3	1	1	3 (8) or 4 (10)
		2	5 (6)
		3	3 (4) or 4 (5)
	2	1	1 (4)
		2	4 (6)
		3	5 (6) or 6 (8)
		4	4 (6) or 3 (4)
4	1	1	1 (12) or 2 (18)
		2	6 (4)
		3	1 (4)
	2	1	3 (8) or 4 (12)
		2	2 (19)
		3	3 (6) or 4 (8)
		4	5 (4) or 6 (5)
5	1	1	1 (8)
		2	3 (10) or 4 (12)
		3	1 (6)
		4	5 (9) or 6 (9)
6	1	1	3 (7) or 4 (7)
		2	1 (9)
		3	2 (10)
		4	6 (6) or 5 (6)

For the purpose comparison, an experiment for the separate implementation situation with which only one shortest process plan for each job has been passed on to CE, named as SPPCE here, has also been conducted. The shortest process plan in this experiment is the one with minimal production time from s process plans. Figures 5 and 6 illustrate the Gantt chart of Experiment 2 based on CE and SPPCE. The experimental results indicate that the joint implementation of process plan selection and scheduling optimization is superior to the situation with separate implementation. Meanwhile, the CE method can obtain different solutions with the same makespan (39) among five runs which indicates that the joint implementation of the problem has more alternatives and adjusting flexibility to react to the dynamic shop floor conditions to maintain the optimized result.

Figure 5.

Gantt chart of Experiment 2 based on CE.

Figure 6.

Gantt chart of Experiment 2 based on SPPCE.

Experiment 3

The benchmark problem set used for Experiment 3 have been reported by Jain et al. ³⁸ These problems involved 18 jobs, the jobs 1–3, 7–9 and 13–15 are with eight process plans, jobs 4, 5, 10, 11, 16 and 17 are with seven process plans and the other jobs are with six process plans. Shao et al. ⁴ constructed six problems with the 18 jobs. For the purpose of consistency, the job with process plans less than 8, the non-enough process plans are a copy of the last process plan for each job. Therefore, the number s for Experiments 3 is set to 8. The values set in bold type in Table 3 are utilized to emphasize the better computational results from our proposed approach. Table 3 shows the experimental results and Figure 7 illustrates the Gantt chart of the solution found for the problem 6. It can be seen that the CE outperforms the EA on all six problems and outperforms the ICA on two problems and two problems are with the same result. CE, EA and no integration methods perform no significant difference which is outperformed by ICA.

Table 3.

Computational result of Experiment 3.

Pb	Jobs	Makespan (CPU time/s)
		CE	EA a	No integration a	ICA a
1	8	499 (3.34)	520 (3.28)	615 (3.42)	499 (2.98)
2	10	607 (3.27)	621 (3.38)	831 (3.72)	586 (3.26)
3	12	697 (3.54)	724 (3.67)	934 (3.91))	679 (2.73)
4	14	801 (3.73)	809 (3.69)	1004 (4.14)	803 (2.50)
5	16	900 (4.01)	921 (3.73)	1189 (4.39)	900 (2.49)
6	18	958 (4.58)	994 (4.09)	1249 (4.69)	976 (3.87)

Pb: problem; CE: cross-entropy; EA: evolutionary algorithm; ICA: imperialist competitive algorithm.

a

Results obtained by the approaches are adopted from Lian et al. ¹

Figure 7.

Gantt chart of problem 6 in Experiment 3 (makespan = 958).

Figures 8 and 9 illustrate the convergence of matrix ${\mathbf{p}}_{\alpha }$ (with 12 jobs and each job with eight process plans and its dimension is 12 × 8) and ${\mathbf{p}}_{\beta }$ (dimension is 48 × 48), respectively, for the problem 3. It can be seen from Figures 8 and 9 that the two matrix parameters can converge to the optimal values simultaneously with only 53 iterations. Meanwhile, it can be observed obviously from Figure 8(d) that row vector elements of ${\mathbf{p}}_{\alpha }$ converge to near (0, 0, 0, 1, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0), (0, 0, 0, 1, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0) and (1, 0, 0, 0, 0, 0, 0, 0), respectively; it means that 4, 2, 2, 1, 1, 4, 2, 2, 1, 1, 1, 1 process plan has the most opportunities been selected for the 12 jobs in the problem by CE iteration, and it can be seen as the optimal selected process for the 12 jobs for this time computation. However, not all the elements in ${\mathbf{p}}_{\beta }$ converge to near 1 or 0 for the final iteration in Figure 9(d); it still can been observed that some elements rise apparently for each row and it means that the corresponding operation number has the most opportunities been selected to for the position.

Figure 8.

Convergence of matrix ${\mathbf{p}}_{\alpha }$ for the problem 3 in Experiment 3: (a) 0 iteration, (b) 10 iterations, (c) 30 iterations and (d) 52 iterations (final).

Figure 9.

Convergence of matrix ${\mathbf{p}}_{\beta }$ for the problem 3 in Experiment 3: (a) 0 iteration, (b) 10 iterations, (c) 30 iterations and (d) 52 iterations (final).

In order to determine a more reasonable value among its range for the pivotal parameter η, comparative experiments based on the above six problems have been conducted with 0.1 as spacing step among its range [0.3, 0.9]. The experiments result are shown in Figure 10; it shows that as the smooth parameter η increases, mean makespans for major problems go downward and then upward. The valley point usually appears at around η = 0.8. The reason for the downward trend is clear that the decreased ration of previous matrix parameters reduces the probability of zero or one components in the matrix at the first few iterations, and then increases the probability to generate sample with better solutions. However, the following upward trend is mainly because that low ration of inherited matrix parameters may prematurely guide some components in the matrix to be zero or one which will cause the algorithm converges to a local optimum early. It can be seen that the balance of sample generation parameter from previous iteration and currently updated matrix is vital for CE in this problem, and the smooth parameter η is set to 0.8 in this article based on the above test.

Figure 10.

Mean makespans for the problems in Experiment 3 with different η.

Experiment 4

Experiment 4 is adopted from the benchmark reported by Kim.³⁹ In this experiment, 24 test-bed problems based on 18 jobs with various combinations of flexibility levels and 15 machines are constructed. The number of operations of these problems varies from 79 to 300. The number s for Experiment 4 is set to 8. The best result for makespan obtained by the CE-based approach, ICA, ¹ Symbiotic Evolutionary Algorithm (SEA), ² HA ⁶ and Active Learning Genetic Algorithm (ALGA) ²¹ are listed in Table 4.

Table 4.

Computational results of Experiment 4.

No.	SEA a	HA a	ALGA a	ICA	CE
1	428	427	427	427	427
2	343	343	343	343	343
3	347	345	344	345	344
4	306	306	306	306	306
5	319	322	321	319	315
6	438	429	429	435	429
7	372	372	372	372	372
8	343	343	343	343	343
9	428	427	427	427	427
10	443	430	427	440	427
11	369	369	369	367	365
12	328	327	327	327	322
13	452	436	436	457	433
14	381	380	380	390	398
15	434	427	427	432	427
16	454	446	446	466	448
17	431	423	423	443	424
18	379	377	377	384	375
19	490	476	474	490	480
20	447	432	438	440	430
21	477	446	447	466	442
22	534	518	513	529	512
23	498	470	470	495	471
24	587	544	548	577	528

ICA: imperialist competitive algorithm; CE: cross-entropy.

a

Results obtained by the approaches are adopted from Qiao and Lv. ³² The values with bold type are used to emphasize the better computational results (or equal to the reported best results) our proposed CE based method achieved.

It can be observed from Table 4 that the CE outperforms the ICA on 17 problems and 6 problems are with the same result. Compared to the best results obtained by SEA, HA, ALGA and ICA, the same or better solutions have been found by CE for 19 out of the 24 test-bed problems. Figure 11 shows the comparison result of CPU time for SEA, ICA and CE, in which the data of ICA and SEA are adopted from Lian et al. ¹ and Kim et al. ² (HA and ALGA with no CPU time provided). It can be seen that no algorithm has significant advantage for the 24 problem from the CPU time view. Figure 12 illustrates the Gantt chart of the solution found for the problem 24.

Figure 11.

Comparison of CPU time for different algorithms.

Figure 12.

Gantt chart of problem 24 in Experiment 4 (makespan = 528).

Conclusion

In order to achieve greater performance and higher productivity of a manufacturing system, the novel CE method has been developed with new introduced probability distribution and updating approach, parallel sample encoding/decoding and generation mechanism for the JPPSSO problem with two sub-problems. The proposed CE-based approach can facilitate the joint implementation of process plan selection and scheduling optimization. The result of JPPSSO based on CE can give aid to the schedule planners to determine the optimal scheduling plans and assist the PP system to determine the final process plan (including the determination of operations, machine for each operation and operations sequence) for each job that will be passed on to the production systems from some alternative process plans simultaneously. Experimental studies have been conducted and comparisons have been made among CE and other developed methods to indicate the superiority and adaptability of the proposed approach. The experimental results show that the proposed CE method has advantage in the makespan objective for the test problems with reasonable CPU time, which provides an alternative and acceptable method in the research of JPPSSO.

The outstanding performance of the CE in makespan is mainly due to the following two factors. First of all, the reasonably introduced two probability matrices and the related sample generation mechanism enable whole solution space can be covered. Then the smoothed updating mechanism can reduce the probability that some of component in the two matrices to be zero or one at the first few interactions, and then help the iteration procedure avoid premature and increase the probability to generate sample with better solutions. However, the CE method has no significant advantage in CPU time comparing to other algorithms. The reason is that the generation of operation-based scheduling plan section in a sample according to the new introduced probability matrix consumes much CPU time.

The further research direction can be conducted from the following aspects:

• To design more efficient method to express and generate samples especially for larger scale problems and conduct experiment with different parameter levels to determine their reasonable values.

• The proposed algorithm should be studied continually for its practical application in manufacturing system by considering uncertainties, such as new job arrival, machine breakdown and so on.

• The mean flow time, resource utilization and so on multi-objectives should also been investigated.

• Furthermore, CE can be extended to cope with the JPPSSO requirements of other scenarios, for instance, assembly operations, integration of electronic product testing process and scheduling.