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 flexibility^1,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.³ 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.⁴ discussed the CF problem in dynamic condition by using genetic algorithm, simulated annealing and tabu search. Arkat et al.⁵ 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.⁶ modeled the CMS as a multiple departures single destination multiple travelling salesman problem, and proposed a simulated annealing algorithm to solve it. Nouri and Hong⁷ 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 Hosseini⁸ developed an ant colony optimization approach for the CF Problem to minimize grouping efficacy. In some articles^9,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.¹² 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.¹³ 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.¹⁴ 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.¹⁵ 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.¹⁶ 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.¹⁷ 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.¹⁸ 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. Taghavifard¹⁹ studied cellular manufacturing scheduling problem with sequence-dependent setup times, and used ant colony optimization and GA to solve it. Halat and Bashirzadeh²⁰ 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 Elmi²¹ investigated group scheduling in buffer-constrained flow shop cells, and proposed a tabu search method to minimize the makespan. Elmi et al.²² 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.

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

Min

The objective function (1) is to minimize the makespan C_max, where ∑m=1M∑t=0θtSpKptm represents the start time of the last operation of part p, and ∑w=1W∑m=1M∑t=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 V_p. 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:

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 = K₁ + K₂ + ⋯ + K_P).

In Step 1, some variables u,FT_p0,I_m,V_p,ε_m and W_m 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 FT_p0 = 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 I_m . 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 V_p* 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 f₁ = 0 or f₂ = 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.²³. 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.

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 (B_u), the processing time (T_pkmw), 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 B_u, 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 B_u are used, including 2, 4, 6 and 8. Moreover, to determine whether the range of T_pkmw and β may have any impact on the performance of the HSA, four different distributions of T_pkmw are used, including T_pkmw ∼ DU[5, 10], T_pkmw ∼ DU[5, 20], T_pkmw ∼ DU[5, 30] and T_pkmw ∼ 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, B_u = 2, T_pkmw ∼ DU[5,20] and β ∼ DU[1,4]. In the second set, M is allowed to vary, given P = 20, W = 5, B_u = 2, T_pkmw ∼ DU[5,20] and β ∼ DU[1,4]. In the third set, W is allowed to vary, given M = 20, P = 20, B_u = 2, T_pkmw ∼ DU[5,20] and β ∼ DU[1,4]. In the fourth set, B_u is allowed to vary, given M = 30, P = 30, W = 5, T_pkmw ∼ DU[5,20] and β ∼ DU[1,4]. In the fifth set, the distribution of T_pkmw is allowed to vary, given M = 20, P = 30, W = 5, B_u = 8 and β ∼ DU[1,4]. In the sixth set, the distribution of β is allowed to vary, given M = 20, P = 30, W = 5, B_u = 8 and T_pkmw ∼ DU[5,40]. Given K_p ∼ DU[20, 40], Y_pkmcm′c′ = 2 if c = c′ and m ≠ m′ , and Y_pkmcm′c′ = 20 if c ≠ c′ and m ≠ m′ in these experiments.

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 1∼6. Let HSA-C_max and SA-C_max 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 ΔC_max denote the declining percentage of average HSA-C_max over average SA-C_max. 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.

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 ΔC_max 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, B_u, T_pkmw 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.