International Journal of Computational Intelligence Systems

Volume 9, Issue 4, August 2016, Pages 765 - 777

Cell formation and task scheduling considering multi-functional resource and part movement using hybrid simulated annealing

Authors
Chunfeng Liu1, lcf_spring@163.com, Jufeng Wang2, *, wang_jufeng@163.com
*Corresponding author
Corresponding Author
Received 23 December 2015, Accepted 15 April 2016, Available Online 1 August 2016.
DOI
https://doi.org/10.1080/18756891.2016.1204123How to use a DOI?
Keywords
Cellular manufacturing system, Cell formation, Group scheduling, Simulated annealing, Operation sequence
Abstract

This paper designs a non-linear integer mathematical model for the cellular manufacturing system (CMS) with dual-resource constrained setting. The multi-functional machines and the multi-skilled workers need to be grouped and assigned to the cells. Moreover, each operation of the parts has different processing times if processed by different machines or workers. Each part with operation sequence is allowed to move from one machine to another for processing subsequent operation, which might reduce processing time although it will incur additional movement time. In order to solve the simultaneous and intertwined optimization problem, a hybrid simulated annealing (HSA) which embedding priority rule based heuristic algorithm is proposed to minimize the makespan. Computational experiments are conducted to show that the proposed HSA performs well with respect to accuracy and efficiency of solution than the traditional simulated annealing algorithm.

Copyright
© 2016. the authors. Co-published by Atlantis Press and Taylor & Francis
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

With the intense competitive market and rapid variation of customer needs, companies should adjust their production strategies in time. They need to produce shorter life-cycle products as well as mid-volume and mid-variety product mixes. In such environment, cellular manufacturing system (CMS) is becoming increasingly important for their advantages such as cutting down the costs, improving the quality of the products and strengthening the manufacturing flexibility1,2. An important problem of the CMS is cell formation (CF), i.e., the physical division of the facilities, where the machines (workers) are grouped into cells and parts are grouped into part families. Another significant problem is the group scheduling which involves decisions on task dispatching rules as well as task timetabling methods.

For the basic cell formation problem with machine assignment, Mahdavi et al.3 proposed a model for the CF based on cell utilization concept. The objective is to minimize the exceptional elements and number of voids in cells to achieve the higher performance of cell utilization. Tavakkoli-Moghaddam et al.4 discussed the CF problem in dynamic condition by using genetic algorithm, simulated annealing and tabu search. Arkat et al.5 formulated the CF problem as an integer linear programming model. They proposed three types of branch and bound algorithms to minimize the total number of intercellular movements. Paydar et al.6 modeled the CMS as a multiple departures single destination multiple travelling salesman problem, and proposed a simulated annealing algorithm to solve it. Nouri and Hong7 took into consideration number of voids in cells and a number of exceptional elements based on the operational time of parts which are required for processing in the machines. A bacteria foraging algorithm was applied to solve the CF problem. Hosseinabadi Farahani and Hosseini8 developed an ant colony optimization approach for the CF Problem to minimize grouping efficacy. In some articles9,10,11, mathematical models were designed for the the CF problem problems. The optimization softwares such as LINGO and CPLEX have been used to solve these models.

For the extensional cell formation problem with worker (and machine) assignment, Egilmez et al.12 designed three stochastic non-linear mathematical models of manpower allocation to manufacturing cells, and developed a four-phased hierarchical methodology to maximize the production rate. They considered normally distributed operation times and customer demand in all models. Süer et al.13 investigated manpower allocation problem in CMS, and examined three different sharing strategies (no operator sharing allowed, sharing allowed without restrictions, sharing allowed with restrictions). They concluded that the models with little or no restrictions yield a higher production rate than the model with no operator sharing allowed. Sakhaii et al.14 developed a model which is incorporated with dynamic cell formation, inter-cell layout, machine reliability, operator assignment, alternative process routings and production planning concepts. They adopted a robust optimization approach to minimize the costs of machine breakdown and relocation, operator training and hiring, inter-intra cell part trip, and shortage and inventory. Mahdavi et al.15 proposed an integrated dynamic CMS model considering multi-period production planning. The authors used LINGO package to minimize the sum of machine and human resource costs, reconfiguration cost, inter-cell material handling cost, inventory holding cost, and backorder cost. Bootaki et al.16 considered a robust design to configure cells in the dynamic cellular manufacturing system. A new method of percentage multi-choice goal programming is innovated to minimize the inter-cell movements and maximize the worker and machine utilization. Liu et al.17 proposed a discrete bacteria foraging algorithm for the assignment of workers and machines in the cell formation and task scheduling problem, in order to minimize the inter-cell material handling costs as well as the fixed and operating costs of workers and machines. Liu et al.18 considered worker assignment and production planning in the dynamic cell formation of fiber connector manufacturing industry. Due to the learning and forgetting effects of workers, the production rate of each workstation will often change, and the bottleneck workstation may transfer to another one in the next period. Reassigning multi-skilled workers may increase the production rate of bottleneck workstation. They suggested a hybrid bacteria foraging algorithm embedding two-phase based heuristic to minimize the backorder cost and holding cost of inventory.

In comparison with the cell formation problem, there are only a few articles discussing group scheduling, which is also called parts scheduling sometimes. Taghavifard19 studied cellular manufacturing scheduling problem with sequence-dependent setup times, and used ant colony optimization and GA to solve it. Halat and Bashirzadeh20 discussed scheduling operations of manufacturing cells considering sequence-dependent family setup times and intercellular transportation times, and suggested a GA-based heuristic for this problem. Solimanpur and Elmi21 investigated group scheduling in buffer-constrained flow shop cells, and proposed a tabu search method to minimize the makespan. Elmi et al.22 addressed job shop cell scheduling problem with inter-cell movement and reentrant parts, and suggested a simulated annealing algorithm to minimize the makespan.

Due to the high complexity of CMS with dual-resource constrained setting, the cell formation and group scheduling issues are normally studied independently. So far, the problem of the CMS simultaneously involving multi-functional machines, multiskilled workers and operation sequence has not been fully investigated, especially for the objective of minimizing the makespan with the impact of part inter-cell and intra-cell movement on task scheduling. To the best of the authors’ knowledge, no related results have been available in the literature, which motivate the present study.

In this paper, we investigate the CMS with two related aspects. On one hand, the machines have multiple functions to process several different tasks, and the workers have multiple skills to operate every machine, but each machine must be operated by only one worker. So the machines and workers need to be grouped and assigned to the cells. On the other hand, each operation has different processing times if processed by different machines or workers. Each part with operation sequence is allowed to move from one machine to another for processing subsequent operation, which might reduce processing time although it will incur additional movement time. In order to solve the simultaneous and intertwined optimization problem, a hybrid simulated annealing (HSA) which embedding priority rule based heuristic algorithm (PRBHA) is proposed to minimize makespan.

The remainder of this paper is organized as follows: The mathematical model integrating cell formation and task scheduling is formulated in Section 2. The PRBHA is developed for high quality initial solution in Section 3. In Section 4, the HSA is proposed for further search to obtain a global optimum. The performance of proposed HSA and the traditional simulated annealing are compared through numerical experiments in Section 5. Finally, the paper closes with a general discussion of the proposed approach as well as a few remarks on future research directions in Section 6.

2. Problem statement and formulation

In this section the problem of cell formation and task scheduling is formulated as a non-linear 0-1 integer programming model. The objective is minimizing the makespan (i.e., maximum completion time of all parts). The main constraints are the multi-functional machines, multi-skilled workers, operation sequence, and part movement. The following assumptions are made for the considered cellular manufacturing system throughout the paper.

  1. 1.

    Machine and worker assumptions: The number of machines, the number of worker types, and the number of each worker type are known in advance. The number of all machines are equal to the number of all workers. Each machine can be operated by any one worker.

  2. 2.

    Task assumption: The number of parts and the number of operations of each part are known in advance. All parts should be finished in the planning horizon.

  3. 3.

    Processing assumption: Each operation of a part can be processed on several different machines. The processing of each operation is not allowed to be interrupted, which implies that each operation of a part is processed by only one machine that have the function to handle it. The processing time of each operation depends on the selected machine and assigned worker type.

  4. 4.

    Operation sequence assumption: There exists chain precedence relationship among operations of each part. However, there is no precedence constraint among different parts.

  5. 5.

    Cell size assumption: The maximum of the cell size in terms of the number of machines is specified in advance, for too many machines in a cell may generate cluttered flows in a cell due to many routes.

  6. 6.

    Part movement assumption: The parts are allowed to move among different machines in the same cell or different cells, and the time spent on movement is known in advance.

Notation
Indices
w

Index for worker type.

c

index for cell.

p

Index for part.

k

Index for operation.

t

Index for time.

m

Index for machine.

Input parameters
W

Number of worker types.

P

Number of parts.

Kp

Number of operations of part p (p = 1,2,⋯ ,P).

M

Number of machines.

Nw

Number of worker type w (w = 1,2,⋯ ,W).

C

Number of cells.

Bu

Upper bound of cell size (measured in the number of machines) which is assumed to be ⌜M/C⌝.

Tpkmw

Processing time of operation k of part p on machine m with worker type w (k = 1,2,⋯ ,Kp; m = 1,2,⋯ ,M).

Qpkm

1 if operation k of part p can be processed on machine m, and 0 otherwise.

Ypkmcm′c′

Movement time of part p whose operation k − 1 was processed on machine m in cell c and operation k will be processed on machine m′ in cell c′ (m,m′ = 1,2,⋯ ,M; c,c′ = 1,2,⋯ ,C). Ypkmcm′c′ = 0 when k = 1 or (m = m′ and c = c′).

θ

A sufficient large number which is greater than the makespan definitely.

Decision variables
Zmc

1 if machine m is assigned to cell c , and 0 otherwise.

Xmw

1 if machine m is operated by worker type w, and 0 otherwise.

Spktm

1 if operation k of part p starts to be processed on machine m at time point t, and 0 otherwise (t = 1,2,⋯ ,θ).

The proposed problem is formulated as the following non-linear 0-1 integer programming:

Min

Cmax=Maxp=1,2,P{m=1Mt=0θtSpKptm+w=1Wm=1Mt=0θSpKptmXmwTpKpmw}
s.t.
SpktmQpkm,p,k,t,m
c=1CZmc=1,m
w=1WXmw=1,m
m=1MXmw=Nw,w
m=1MZmcBu,c
t=0θm=1MSpktm=1,p,k
p=1Pk=1Kpw=1Wτ=tt+Tpkmw1SpkτmXmw1,m,t
t=0θm=1MtSpktmt=0θm=1MtSp,k1,t,mw=1Wt=0θm=1MSp,k1,t,mXmwTpkmw+t=0θm=1Mt=0θm=1Mc=1Cc=1CYpkmcmcSpktmSp,k1,t,mZmcZmc,p,k=2,3,,Kp
Zmc,Xmw,Spktm{0,1},m,w,c,p,k,t

The objective function (1) is to minimize the makespan Cmax, where m=1Mt=0θtSpKptm represents the start time of the last operation of part p, and w=1Wm=1Mt=0θSpKptmXmwTpKpmw represents the processing time of the last operation of part p. Constraint (2) guarantees that each operation of a part is processed on the machine that can process the operation. Constraint (3) ensures that each machine is assigned and only assigned to one cell. Constraints (4) and (5) imply that each machine is operated by one and only one worker. Constraint (6) shows that the number of machines in the same cell can not exceed the upper bound of cell size. Constraint (7) indicates that each operation k of part p must start once. Constraint (8) guarantees that a machine can at most process one operation at a time. Constraint (9) provides the precedence relationship between consecutive operations of part p. Constraint (10) ensures that the decision variables are binary variables.

3. Priority rule based heuristic algorithm

Heuristics have taken an important position in the search of solutions in many combinatory problems, as it is simple, easy to implement and can be embedded in more sophisticated heuristics or metaheuristics for determining initial feasible solutions that can be improved in further stages. We develop a priority rule based heuristic algorithm (PRBHA) consisting of several iterations.

Four task-sets associated with each iteration are defined. The unscheduled operations whose immediate predecessor has been scheduled are in the set H. The unscheduled operations whose immediate predecessor has been completed upon scheduling time point t are in the set Dˆ . The operations which are available for scheduling on selected machine with respect to precedence constraints but yet unscheduled are in the decision set D. The unscheduled operations of part p are in the set Vp. At each iteration, a prior task is selected according to the earliest finishing time first (EFT) rule and inserted inside a partial schedule on a selected machine. This priority rule method enables the eligible tasks to be processed as soon as possible, which gives rise to a compact schedule.

The variables used for the PRBHA are summarized as follows:

u

the counter of iteration

H

the set of unscheduled operations whose immediate predecessor has been scheduled

t

the scheduling time point

Dˆ

the set of unscheduled operations whose immediate predecessor has been completed upon scheduling time point t

D

the decision task-set upon scheduling time point t

f1

the flag variable which is equal to 1 when Dˆ is not empty and 0 otherwise

f2

the flag variable which is equal to 1 when D is not empty and 0 otherwise

Vp

the set of unscheduled operations of part p

Im

the start idle time of machine m

Iˆ

the set of start idle times of all machines

ϖpk

the set of machines that can process the operation k of part p

ωpk

the machine that process the operation k of part p

εm

the cell to which the machine m is assigned

Wm

the worker type that operates the machine m

kp

the operation k of part p (let kp** denote the prior task; p* and k* indicate the selected prior part and prior operation, respectively)

FTpk

the finish time of the operation k of part p

STpk

the start time of the operation k of part p

We give a pseudo-code description of the priority rule based heuristic algorithm ( Algorithm 1) which consists of N iterations (N is the sum number of operations of all parts, i.e., N = K1 + K2 + ⋯ + KP).

In Step 1, some variables u,FTp0,Im,Vpm and Wm are initialized. Assuming that each part p has a dummy operation k = 0 with 0 unit of processing time at the beginning of the part. So let FTp0 = 0, ∀p. In Step 2, each job is scheduled at each iteration until u = N . In Step 〈1〉, Iˆ is computed to represent the set of Im . In Step ♣1, the scheduling time point t is determined by the minimum start idle time of machines. Step ♣2 computes the set Dˆ which denotes the unscheduled operations whose immediate preceding operation has been completed at the time point t. Step ♡2 computes the set {m*} which denotes the machines that are idle at the time point t. The decision task-set D is computed in the Step ♠1, which shows the eligible operations that can be scheduled on machine m* upon the time point t. In Step ◊2, the EFT rule is used to determine a prior task processed on machine m*, i.e., the task in D with minimum finish time is selected as the prior task kp** . The start idle time of machine m* is updated in Step ◊3. The start and finish times of kp** are recorded in Steps ◊4 and ◊5, respectively. The machine ωp*k* that processes kp** is recorded in Step ◊6. In Step ◊8, the makespan is computed and the procedure is terminated if the counter of iteration u is equal to N. The sets Vp* and Dˆ are updated in Step ◊9. In Step ˜1 , the scheduling time point t is postponed to the next minimum start idle time if f1 = 0 or f2 = 0, because there is no operation which can be scheduled at the time point t.

4. Hybrid simulated annealing algorithm

Simulated annealing (SA) is a stochastic neighborhood search technique which was introduced by Kirkpatrick et al.23. It is derived from the similarity between the process of annealing of solids and the method of solving combinatorial optimization problems.

The algorithm starts with a random trial solution as current solution. A neighborhood of current solution is then searched, by some neighborhood search structures. If the neighborhood is better than the current one, it is accepted as the new current solution. Otherwise, it is accepted by a certain probability. The principal advantage of SA is to escape from local optima by accepting some nonimproving solutions at each temperature level to reach a global optimum. In the beginning, the probability of accepting nonimproving solutions is high, but as the temperature drops, the probability of accepting non-improving solutions decreases.

Because the proposed cell formation and task scheduling problem is much complicated, a basic SA may not perform well to solve it. Therefore, we suggest a hybrid simulated annealing (HSA) which combines the PRBHA approach and three neighborhood strategies with traditional simulated annealing.

4.1. Initial solution

The PRBHA can generate feasible solution represented by the variables εm, Wm, ωpk, STpk and makespan Cmax. εm and Wm correspond to decision variables Zmc and Xmw, respectively. ωpk and STpk correspond to decision variable Spktm. The HSA employs the feasible solution as initial solution for further search.

4.2. Neighborhood generation strategy

Well-designed solution mutation(SM) operators are significant to the success of HSA. In this research, three different mutation strategies are developed as follows:

  1. 1.

    Machine-cell mutation(SM1):

    Randomly select a machine m1 in cell c1 and move it to different cell c2 if the number of machines in cell c2 does not reach the upper cell size limit, otherwise randomly select a machine m2 in cell c2 and then exchange machines m1 and m2 between cells c1 and c2.

  2. 2.

    Machine-worker mutation(SM2):

    Randomly select two machines operated by two different types of workers, and then exchange their workers.

  3. 3.

    part-operation-machine mutation(SM3):

    Randomly select an operation of a part, and then reassign it to other machine that can process the operation.

The objective function values (i.e., makespan Cmax) of the neighborhood solutions can be computed by the revised backward recursion algorithm (Algorithm 2).

1. Initialize: u = 0; FTp0 = 0,∀p; Im = 0,∀m; Vp = {1,2,…,Kp},∀p;
Randomly generate εm and Wm,∀m
2. WHILE (1) DO
 〈1〉. Iˆ={Im|m=1,2,,M}
 〈2〉. f1 = 0, f2 = 0
 〈3〉. H = {kp|p ∈ {p|Vp ≠ ∅, p = 1,2⋯P},kp = min{kp|kpVp}}
 〈4〉. WHILE (1) DO
  ♣1. t=min{τ|τIˆ}
  ♣2. Dˆ={kp|FTp,k1t,kpH}
  ♣3. IF (Dˆ) THEN
   ♡1. f1 = 1
   ♡2. {m*} : Im*t
   ♡3. FOR each m* from {m*} :
    ♠1. D={kp|kpDˆ,m*ϖpk}
    ♠2. IF (D ≠ 0)THEN
     ◊1. f2 = 1
     ◊2. Let αpk = max {t,FTp,k−1+Ypkωp,k−1Cωp,k−1m*Cm* },
        kp**:ftp*k*=min{ftpk|ftpk=αpk+Tpkm*Wm*,kpD}
     ◊3. Im* = max{t,FTp*,k*−1 +Yp*k*ωp*,k−1Cωp*,k−1m*Cm* } + Tp*k*m*Wm*
     ◊4. STp*k* = max{t,FTp*,k*−1 +Yp*k*ωp*,k−1Cωp*,k−1m*Cm* }
     ◊5. FTp*k* = Im*
     ◊6. ωp*k* = m*
     ◊7. u := u + 1
     ◊8. IF (u = N) THEN
       *1. Compute Cmax = max{FTpKp, p ∈ 1,2,⋯ ,P}
       *2. RETURN
     ◊9. Vp*=Vp*\{kp**},Dˆ=Dˆ\{kp**}
    ♠3. IF (Dˆ=) THEN BREAK
  ♣4. IF(f1 = 0 or f2 = 0) THEN
   ˜1. Iˆ:=Iˆ\{t}
   ˜2. clear Dˆ
  ♣. ELSE
   ¯1. Clear Dˆ , H, Iˆ
   ¯2. BREAK
Algorithm 1:

Priority Rule Based Heuristic Algorithm (PRBHA)

4.3. Cooling schedule

There are some parameters existing in the cooling schedule, which include initial temperature, final temperature, cool rate, and Markov chain length. They are determined through pretest after referring to some literature about SA.

  1. 1.

    Cooling rate:

    The temperature ħ should be gradually decreased from initial temperature ħ0 = 200 in order to reach slow cooling. The temperature is decreased by using the common equation ħ := αħ, where α is cooling rate and its value is set to 0.95.

    1. Initialize: FTp0 = 0; Im = 0; H = {1p|p = 1,2⋯P}; Yp1mcm′c′ = 0
    2.FOR g = 1 to N
       2.1. Randomly select kp from H
       2.2. STpk = max {Iωpk,FTp,k−1+Ypkωp,k−1Cωp,k−1ωpkCωpk}
       2.3. FTpk = STpk + TpkωpkWωpk
       2.4. Iωpk = FTpk, and update H
    3. Cmax = max{FTpKp|p = 1,2⋯P}
    Algorithm 2:

    Revised Backward Recursion Algorithm (RBRA)

  2. 2.

    Markov chain length(MCL):

    MCL is chosen in such a way that a thermal equilibrium can be attained for each temperature level. MCL is denoted by Lmax = 200.

  3. 3.

    Termination condition:

    Let xbest denote the best solution up to now. The HSA algorithm is stopped if xbest does not change after three consecutive temperature levels or the final temperature (ħf = 0.5) is reached.

4.4. The pseudo-code of the HSA

The pseudo-code of the HSA is given as Algorithm 3. The main idea of optimization is that: If Cmax of neighborhood solution xl is less than Cmax of current solution xc, accept xl as current solution, otherwise accept xl as current solution by certain probability, which can escape from local optima to reach a global optimum.

5. Computational experiments

The following numerical experiments are conducted to evaluate the performance of the HSA compared to the traditional SA which randomly generates initial solution. The performance is evaluated by use of several impact factors including the number of parts (P), the number of machines (M), the number of worker types (W), the upper cell size limit (Bu), the processing time (Tpkmw), and the number of machines that can process the operation (β). The value range of these parameters are determined to ensure that they can reflect small-sized, middle-sized and large-sized instances.

To test the effects of varying P, M, W and Bu, four different values of P are used, including 25, 50, 75 and 100, four different values of M are used, including 10, 20, 30 and 40, and four different values of W and Bu are used, including 2, 4, 6 and 8. Moreover, to determine whether the range of Tpkmw and β may have any impact on the performance of the HSA, four different distributions of Tpkmw are used, including Tpkmw ∼ DU[5, 10], Tpkmw ∼ DU[5, 20], Tpkmw ∼ DU[5, 30] and Tpkmw ∼ DU[5, 40], and four different distributions of β are used, including β ∼ DU[1, 5], β ∼ DU[1, 6], β ∼ DU[1, 7] and β ∼ DU[1, 8], where DU[a, b] represents a discrete uniform distribution with an integer range from a to b.

Six sets of numerical experiments are conducted. In the first set, P is allowed to vary, given M = 20, W = 5, Bu = 2, Tpkmw ∼ DU[5,20] and β ∼ DU[1,4]. In the second set, M is allowed to vary, given P = 20, W = 5, Bu = 2, Tpkmw ∼ DU[5,20] and β ∼ DU[1,4]. In the third set, W is allowed to vary, given M = 20, P = 20, Bu = 2, Tpkmw ∼ DU[5,20] and β ∼ DU[1,4]. In the fourth set, Bu is allowed to vary, given M = 30, P = 30, W = 5, Tpkmw ∼ DU[5,20] and β ∼ DU[1,4]. In the fifth set, the distribution of Tpkmw is allowed to vary, given M = 20, P = 30, W = 5, Bu = 8 and β ∼ DU[1,4]. In the sixth set, the distribution of β is allowed to vary, given M = 20, P = 30, W = 5, Bu = 8 and Tpkmw ∼ DU[5,40]. Given Kp ∼ DU[20, 40], Ypkmcm′c′ = 2 if c = c′ and mm′ , and Ypkmcm′c′ = 20 if cc′ and mm′ in these experiments.

1. Initialize parameters:
 1.1. ħ0 = 200, ħf = 0.5,α = 0.95,Total = 0,Change = 0,Unchange = 0.
 1.2. Generate initial solution x0 and objective function value Cmax(x0) by Algorithm 1; Set xc = x0 and Cmax(xc) = Cmax(x0)
2. WHILE (ħ > ħf ) DO
 2.1. WHILE (Total < Lmax) DO
  2.1.1. Randomly generate a number r1 ∼ U[0,1]
   (U[0,1] represents an uniform distribution real interval [0,1])
   IF (r1 > 0.5)
    Randomly generate a number r2 ∼ U[0,1]
    IF (r2 > 0.5)
     Generate neighborhood xl by SM1
     Compute Cmax(xl) by Algorithm 2
    ELSE
     Generate neighborhood xl by SM2
     Compute Cmax(xl) by Algorithm 2
   ELSE
     Generate neighborhood xl by SM3
     Compute Cmax(xl) by Algorithm 2
  2.1.2. IF (Cmax(xl) ≤ Cmax(xc))
    xc = xl
    IF (Cmax(xc) ≤ Cmax(xbest))
      xbest = xc,Change := Change + 1,Unchange = 0
   ELSE
    Randomly generate a number r3 ∼ U[0,1]
    Let Δ = Cmax(xl) −Cmax(xc)
    IF (e−Δ/ħ > r3)
      xc = xl
  2.1.3. Total := Total + 1
 2.2. IF (Change = 0)
   Unchange := Unchange + 1
 2.3. IF (Unchange = 3)
   RETURN Cmax(xbest)
 2.4. ħ := α × ħ,Total = 0,Change = 0
3.RETURN Cmax(xbest)
Algorithm 3:

Hybrid Simulated Annealing (HSA)

The experiments have been performed on a Pentium-based Lenovo-compatible personal computer with 2.3 GHz clock-pulse and 4 GB RAM. The HSA and SA have been coded in C++, compiled with the Microsoft Visual C++ 9.0 compiler, and tested under Microsoft Windows 7 operating system.

The experimental results are presented in Tables 16. Let HSA-Cmax and SA-Cmax denote the objective function values of the problem using the HSA and SA, respectively. Each table entry represents the minimum, maximum and average of its associated 10 instances. For example, 10 random instances are generated when P = 25 in Table 1, and another 10 random instances are generated when P = 50. Let ΔCmax denote the declining percentage of average HSA-Cmax over average SA-Cmax. Let HSA-CPU and SA-CPU denote the mean CPU times of the HSA and SA without including input and output times, respectively. Let ΔCPU denote the declining percentage of HSA-CPU over SA-CPU.

P HSA-Cmax
SA-Cmax
ΔCmax (%) HSA-CPU (s) SA-CPU (s) ΔCPU (%)
MIN MAX AVE MIN MAX AVE
25 1176 1319 1241.3 2141 2207 2186.2 43.22 52.00 97.14 46.47
50 1570 1803 1685.7 3253 3573 3428.6 50.83 151.57 344.60 56.02
75 2173 2307 2228.1 4000 4183 4140.5 46.19 242.93 512.88 52.63
100 2763 2899 2841.1 4912 5159 5081.3 44.09 424.58 737.42 42.42
Table 1:

Comparison between HSA and SA with different number of parts (P)

(M = 20, W = 5, Bu = 2, Tpkmw ∼ DU[5,20], β ∼ DU[1,4])

M HSA-Cmax
SA-Cmax
ΔCmax (%) HSA-CPU (s) SA-CPU (s) ΔCPU (%)
MIN MAX AVE MIN MAX AVE
10 1162 1426 1279.3 2247 2468 2349.4 45.55 37.22 81.97 54.59
20 1055 1181 1130.9 1786 1939 1895.9 40.35 34.22 79.51 56.96
30 1219 1332 1277.3 1957 2075 2004.9 36.29 42.68 75.76 43.66
40 1261 1314 1283.0 1860 1988 1932.1 33.60 49.60 92.74 46.52
Table 2:

Comparison between HSA and SA with different number of machines (M)

(P = 20, W = 5, Bu = 2, Tpkmw ∼ DU[5,20], β ∼ DU[1,4])

W HSA-Cmax
SA-Cmax
ΔCmax (%) HSA-CPU (s) SA-CPU (s) ΔCPU (%)
MIN MAX AVE MIN MAX AVE
2 1113 1204 1160.5 1955 2076 2026.0 42.72 40.91 88.94 54.00
4 1168 1274 1213.5 1891 2073 2010.1 39.63 38.63 73.02 47.10
6 1156 1264 1206.1 2113 2196 2167.3 44.35 43.84 96.87 54.74
8 1119 1212 1165.9 1949 2078 1984.4 41.25 39.34 90.41 56.49
Table 3:

Comparison between HSA and SA with different number of worker types (W)

(M = 20, P = 20, Bu = 2, Tpkmw ∼ DU[5,20], β ∼ DU[1,4])

Bu HSA-Cmax
SA-Cmax
ΔCmax (%) HSA-CPU (s) SA-CPU (s) ΔCPU (%)
MIN MAX AVE MIN MAX AVE
2 1263 1366 1312.7 2206 2355 2299.6 42.92 80.00 170.46 53.07
4 1250 1376 1296.8 2259 2428 2342.2 44.63 80.83 119.77 32.51
6 1084 1242 1161.7 2006 2101 2057.6 43.54 73.81 130.01 43.23
8 1086 1179 1134.1 1954 2091 2035.9 44.29 75.41 138.98 45.74
Table 4:

Comparison between HSA and SA with different upper cell size limit (Bu)

(M = 30, P = 30, W = 5, Tpkmw ∼ DU[5,20], β ∼ DU[1,4])

Tpkmw HSA-Cmax
SA-Cmax
ΔCmax (%) HSA-CPU (s) SA-CPU (s) ΔCPU (%)
MIN MAX AVE MIN MAX AVE
DU[5, 10] 785 939 864.3 1624 1714 1686.6 48.75 71.43 155.02 53.92
DU[5, 20] 1132 1260 1180.9 2300 2447 2357.5 49.91 76.09 155.57 51.09
DU[5, 30] 1321 1492 1428.9 2616 2840 2723.6 47.54 71.66 129.59 44.70
DU[5, 40] 1520 1768 1679.6 3379 3632 3564.2 52.88 78.18 142.34 45.08
Table 5:

Comparison between HSA and SA with different processing time (Tpkmw)

(M = 20, P = 30, W = 5,Bu = 8, β ∼ DU[1,4])

β HSA-Cmax
SA-Cmax
ΔCmax (%) HSA-CPU (s) SA-CPU (s) ΔCPU (%)
MIN MAX AVE MIN MAX AVE
DU[1, 5] 1494 1646 1565.1 3220 3309 3264.00 52.05 69.33 142.18 51.24
DU[1, 6] 1571 1873 1657.8 3391 3604 3479.8 52.36 74.02 150.46 50.80
DU[1, 7] 1434 1725 1590.5 3238 3432 3315.3 52.03 70.96 154.22 53.99
DU[1, 8] 1442 1622 1494.4 3270 3488 3383.6 55.83 66.48 135.37 50.89
Table 6:

Comparison between HSA and SA with different number of machines that can process the operation (β)

(M = 20, P = 30, W = 5, Bu = 8, TpkmwDU[5,40])

For example, when P = 25 in Table 1, we generate 10 random instances. The average objective function values using the HSA and SA are 1241.3 and 2186.2, respectively. The HSA is better than the SA by 43.22% in terms of the average objective function value. The mean CPU times of the HSA and SA are 52.00s and 97.14s, respectively. The HSA is faster than the SA by 46.47% in terms of the mean CPU time.

From the obtained results, we can see that ΔCmax reaches 33.60%∼55.83% and ΔCPU reaches 32.51% ∼56.96% . That is to say, the HSA can get higher quality solution within less CPU time than the SA regardless of the variation of six impact factors P, M, W, Bu, Tpkmw and β. The reason lies in that the PRBHA algorithm plays an important role in generating good initial solution of the HSA to avoid the blind search of SA at the beginning while exploring the solution space.

6. Conclusions

This paper investigates a novel optimization model of cellular manufacturing system (CMS) under dual-resource constrained setting along with a hybrid simulated annealing (HSA) embedding priority rule based heuristic algorithm (PRBHA). The advantage of the proposed model is simultaneously integrating cell formation and task scheduling by assuming multi-functional resource and inter-intra cell part trip. Other features are operation sequence and maximal cell size limit. Considering part trip might reduce processing time although it will incur additional movement time, the objective of the problem is minimizing the makespan. The PRBHA schedules a prior task on a prior machine operated by a prior worker according to the priority rule at each iteration, which helps to generate a high quality initial solution for further search. Experimental results show that the quality of solutions obtained by the HSA is better than the SA in terms of accuracy and efficiency no matter what variation of some important parameters.

The major contribution of this paper includes two aspects: (1) There is a trade-off among no movement, intra-cell movement and inter-cell movement for parts in the proposed problem. The intertwined issue as well as multi-functional machines and multi-skilled workers are incorporated into the non-linear 0-1 integer programming model for optimization. (2) Operation sequence may hinder some immediate successors to start in time even if there are machines available in cells. However, the PRBHA is suggested to generate a compact schedule. The mechanism is that at each iteration, a prior task is selected according to the EFT rule and inserted inside a partial schedule, which enables the eligible tasks to be processed as soon as possible. The PRBHA helps the HSA to improve the solution quality.

An important research direction that may be pursued in the future is to extend chain precedence constraints of operations to arbitrary precedence constraints of parts and operations. The other potential interest is to develop more efficient priority rules combined in the heuristics, embed them in some population based evolutionary algorithms, and compare the performance of these metaheuristics.

Acknowledgment

This research was supported by the Zhejiang Provincial Natural Science Foundation of China (Grant No. LY14G020014), Humanities and Social Sciences Youth Foundation of the Ministry of Education (Grant No. 14YJC630089), Zhejiang Provincial Key Research Base of Humanities and Social Sciences in Hangzhou Dianzi University (Grant No. ZD05-201601), and the Research Center of Information Technology & Economic and Social Development (Key Research Institute of Philosophy and Social Sciences of Zhejiang Province). The authors are grateful for the financial supports.

References

1.Z Zhang, Complexity of cellular manufacturing systems based on entropy models, Journal of Mechanical Science and Technology, Vol. 24, No. 11, 2010, pp. 2275-2280. http://dx.doi.org/10.1007/s12206-010-0805-6
2.V. R Ghezavati, S. J Sadjadi, and M Dehghan Nayeri, Integrating strategic and tactical decisions to robust deigning of cellular manufacturing under uncertainty: Fixed suppliers in supply chain, International Journal of Computational Intelligence Systems, Vol. 4, No. 5, 2011, pp. 837-854. http://dx.doi.org/10.1080/18756891.2011.9727835
3.I Mahdavi, B Javadi, K Fallah-Alipour, and J Slomp, Designing a new mathematical model for cellular manufacturing system based on cell utilization, Applied Mathematics and Computation, Vol. 190, No. 1, 2007, pp. 662-670. http://dx.doi.org/10.1016/j.amc.2007.01.060
4.R Tavakkoli-Moghaddam, M. B Aryanezhad, N Safaei, and A Azaron, Solving a dynamic cell formation problem using metaheuristics, Applied Mathematics and Computation, Vol. 170, No. 2, 2005, pp. 761-780. http://dx.doi.org/10.1016/j.amc.2004.12.021
5.J Arkat, H Abdollahzadeh, and H Ghahve, A new branch and bound algorithm for cell formation problem, Applied Mathematical Modelling, Vol. 36, No. 10, 2012, pp. 5091-5100. http://dx.doi.org/10.1016/j.apm.2011.12.047
6.M. M Paydar, I Mahdavi, I Sharafuddin, and M Solimanpur, Applying simulated annealing for designing cellular manufacturing systems using MDmTSP, Computers & Industrial Engineering, Vol. 59, No. 4, 2010, pp. 929-936. http://dx.doi.org/10.1016/j.cie.2010.09.003
7.H Nouri and T. S Hong, A bacteria foraging algorithm based cell formation considering operation time, Journal of Manufacturing Systems, Vol. 31, No. 3, 2012, pp. 326-336. http://dx.doi.org/10.1016/j.jmsy.2012.03.001
8.M Hosseinabadi Farahani and L Hosseini, An ant colony optimization approach for the machineCpart cell formation problem, International Journal of Computational Intelligence Systems, Vol. 4, No. 4, 2011, pp. 486-496. http://dx.doi.org/10.2991/ijcis.2011.4.4.8
9.P Renna and M Ambrico, Design and reconfiguration models for dynamic cellular manufacturing to handle market changes, International Journal of Computer Integrated Manufacturing, Vol. 28, No. 2, 2015, pp. 170-186. http://dx.doi.org/10.1080/0951192x.2013.874590
10.S. A kioon, A. A Bulgak, and T Bektas, Integrated cellular manufacturing systems design with production planning and dynamic system reconfiguration, European Journal of Operational Research, Vol. 192, No. 2, 2009, pp. 414-428. http://dx.doi.org/10.1016/j.ejor.2007.09.023
11.H Rafiei, M Rabbani, B Nazaridoust, and S. S Ramiyani, Multi-objective cell formation problem considering work-in-process minimization, The International Journal of Advanced Manufacturing Technology, Vol. 76, No. 9–12, 2015, pp. 1947-1955. http://dx.doi.org/10.1007/s00170-014-6419-x
12.G Egilmez, B Erenay, and G. A Süer, Stochastic skill-based manpower allocation in a cellular manufacturing system, Journal of Manufacturing Systems, Vol. 33, No. 4, 2014, pp. 578-588. http://dx.doi.org/10.1016/j.jmsy.2014.05.005
13.G. A Süer, K Kamat, E Mese, and J Huang, Minimizing total tardiness subject to manpower restriction in labor-intensive manufacturing cells, Mathematical and Computer Modelling, Vol. 57, No. 3-4, 2013, pp. 741-753. http://dx.doi.org/10.1016/j.mcm.2012.08.013
14.M Sakhaii, R Tavakkoli-Moghaddam, M Bagheri, and B Vatani, A robust optimization approach for an integrated dynamic cellular manufacturing system and production planning with unreliable machines, Applied Mathematical Modelling, Vol. 40, 2015, pp. 169-191. http://dx.doi.org/10.1016/j.apm.2015.05.005
15.I Mahdavi, A Aalaei, M. M Paydar, and M Solimanpur, Designing a mathematical model for dynamic cellular manufacturing systems considering production planning and worker assignment, Computers and Mathematics with Applications, Vol. 60, No. 4, 2010, pp. 1014-1025. http://dx.doi.org/10.1016/j.camwa.2010.03.044
16.B Bootaki, I Mahdavi, and M. M Paydar, New bi-objective robust design-based utilisation towards dynamic cell formation problem with fuzzy random demands, International Journal of Computer Integrated Manufacturing, Vol. 28, No. 6, 2015, pp. 577-592. http://dx.doi.org/10.1080/0951192x.2014.880949
17.C Liu, J Wang, J. Y.-T Leung, and K Li, Solving cell formation and task scheduling in cellular manufacturing system by discrete bacteria foraging algorithm, International Journal of Production Research, Vol. 54, No. 3, 2016, pp. 923-944. http://dx.doi.org/10.1080/00207543.2015.1113328
18.C Liu, J Wang, and J. Y.-T Leung, Worker assignment and production planning with learning and forgetting in manufacturing cells by hybrid bacteria foraging algorithm, Computers & Industrial Engineering, Vol. 96, 2016, pp. 162-179. http://dx.doi.org/10.1016/j.cie.2016.03.020
19.M. T Taghavifard, Scheduling cellular manufacturing systems using ACO and GA, International Journal of Applied Metaheuristic Computing, Vol. 3, No. 1, 2012, pp. 48-64. http://dx.doi.org/10.4018/jamc.2012010105
20.K Halat and R Bashirzadeh, Concurrent scheduling of manufacturing cells considering sequence-dependent family setup times and intercellular transportation times, The International Journal of Advanced Manufacturing Technology, Vol. 77, No. 9–12, 2015, pp. 1907-1915. http://dx.doi.org/10.1007/s00170-014-6511-2
21.M Solimanpur and A Elmi, A tabu search approach for group scheduling in buffer-constrained flow shop cells, International Journal of Computer Integrated Manufacturing, Vol. 24, No. 3, 2011, pp. 257-268. http://dx.doi.org/10.1080/0951192x.2011.552527
22.A Elmi, M Solimanpur, S Topaloglu, and A Elmi, A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts, Computers & Industrial Engineering, Vol. 61, No. 1, 2011, pp. 171-178. http://dx.doi.org/10.1016/j.cie.2011.03.007
23.S Kirkpatrick, C. D Gelatt, and M. P Vecchi, Optimization by simulated annealing, Science, Vol. 220, No. 4598, 1983, pp. 671-680. http://dx.doi.org/10.1126/science.220.4598.671
Journal
International Journal of Computational Intelligence Systems
Volume-Issue
9 - 4
Pages
765 - 777
Publication Date
2016/08/01
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
https://doi.org/10.1080/18756891.2016.1204123How to use a DOI?
Copyright
© 2016. the authors. Co-published by Atlantis Press and Taylor & Francis
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

TY  - JOUR
AU  - Chunfeng Liu
AU  - Jufeng Wang
PY  - 2016
DA  - 2016/08/01
TI  - Cell formation and task scheduling considering multi-functional resource and part movement using hybrid simulated annealing
JO  - International Journal of Computational Intelligence Systems
SP  - 765
EP  - 777
VL  - 9
IS  - 4
SN  - 1875-6883
UR  - https://doi.org/10.1080/18756891.2016.1204123
DO  - https://doi.org/10.1080/18756891.2016.1204123
ID  - Liu2016
ER  -