Sage Journals: Discover world-class research

Abstract

Cell formation deals with grouping of machines and parts in manufacturing systems according to their compatibility. Manufacturing processes are surrounded with an abundance of complex constraints which should be considered carefully and represented clearly for obtaining high efficiency and productivity. Constraint programming is a new approach to combinatorial optimization and provides a rich language to represent complex constraints easily. However, the cell formation problems are well suited to be solved by constraint programming approach since the problem has many constraints such as part-machine requirements, availabilities in the system in terms of capacity, machine and worker abilities. In this study, the cell formation problem is modeled using machine, part processing and worker flexibilities via resource element–based representation. Resource elements define the processing requirements of parts and processing capabilities of machines and workers, which are resource-independent capability units. A total of 12 case problems are generated, and different search phases of constraint programming are defined for the solution procedure. The cell formation problem is modeled in both constraint programming and integer programming, and a comparative analysis of constraint programming and integer programming model solutions is done. The results indicate that both the models are effective and efficient in the solution of the cell formation problem.

Keywords

Cellular manufacturing group technology constraint programming flexibility resource elements

Introduction

Group technology (GT) is a common methodology for increasing productivity in manufacturing systems. Cell formation (CF) is a key step in GT, which consists of dividing a plant into a set of cells that process part families in such a way that the part flow among cells is minimized or eliminated.

There are three main strategies for machine-CFs in terms of the ordering in the formation process.¹ In the first strategy, machine cells are formed first and then the part families are determined. In the second strategy, part families are formed first and then the machine cells are determined, and the final strategy consists of forming part–machine cells concurrently. In the literature, forming part families and machine cells are usually considered as separate problems. However, this approach increases the solution time, and besides, solving one problem after the other creates restrictions in forming independent cells.²

Flexibility has been thoroughly examined for manufacturing system design.³ It is an important objective to be achieved in cell design in order to reflect real-world manufacturing systems.^4,5 Increasing flexibility makes it easy for companies to be able to survive and compete with others in such responsive and agile manufacturing environments. Different types of flexibilities have been identified for manufacturing systems throughout several studies.^6,7

Involvement of worker assignment in CF problems is important for reflecting the real components of a shop floor. Workers are one of the basic components of manufacturing cells, besides machines, parts and operating rules. The worker-related factors greatly affect the design, implementation and operation of cells.⁸ Keeping this in mind, this study not only considers flexibilities in machining operations and part processing but also considers worker capabilities. The machines in the system have different capabilities to perform different operations, and the processing requirements of the parts are predefined as a resource element (RE)–based sequence of operations that the parts will go through. Thus, the parts can be processed on alternative machines that can perform the operations required for their processing. In the same way, the workers have different capabilities to perform different operations of the parts on the eligible machines. In other words, each worker can operate different machines and thus can handle the processing of different parts. The processing requirements of parts and the capabilities of machines and workers are defined using REs which are defined as resource-independent capability units.⁹ Each RE comprises a set of machining operations which are mutually exclusive. The basic concept of utilizing REs is to define shared and unique capabilities of machine tools and workers. Hence, it is possible to consider overlapping capabilities of machines and workers while forming manufacturing cells via REs.² RE-based approach was also adopted by Liang and Fung¹⁰ to present a coordination mechanism in virtual cellular manufacturing systems (VCMSs) using multi-agent technology and the pheromone concept of ant colony optimization algorithm.

This study is unique in the CF literature for incorporating machine, part processing and worker flexibilities together using the knowledge of the capabilities of machines and workers, and the knowledge of processing requirements of parts. The assignment of parts, machines and workers to manufacturing cells is done concurrently on RE basis. Integer programming (IP) and constraint programming (CP) approaches are used to model the CF problem with the mentioned flexibilities. To the best knowledge of the authors, there is no study that employs CP to solve this flexible CF problem with the involvement of worker assignments.

The rest of this article is organized as follows: A literature review about the CF problem with worker assignments is presented in section “Literature review.” Brief information about CP is given in section “CP.” The proposed IP and CP models are presented in section “Development of the models.” A case problem and its solution results are given in section “Illustration of a case problem.” A comparative computational analysis of the proposed IP and CP models is presented in section “Comparative analysis of IP and CP models.” Finally, the conclusion and future research directions are given in section “Conclusion.”

Literature review

In this study, machine and worker flexibilities are defined in terms of RE capability. For each machine and worker, a list of REs they can perform is defined.^2,9,11 Similarly, for each part, the processing requirements are defined as a sequence of REs to be completed. Thus, a part can be processed through different machines being operated by different workers. Thus, in this section, the studies that consider the design approaches to the flexible CF problem with worker assignment are presented.

The main flexibilities in the CF problem can be considered as part–routing flexibility, operation flexibility, machine flexibility and worker flexibility. Part–routing flexibility enables the cellular system to process parts using different routes through machines or work cells. Askin et al.¹² defined routing flexibility as the ability to process parts completely in multiple cells. In such a system, the processing route can be changed in case of a machine breakdown or in order to form more efficient machine groups and part families. Operation flexibility is concerned with producing a part in different ways. Goyal¹³ defined operational flexibility in two dimensions: product flexibility (being able to produce different products on the same production line) and volume flexibility (being able to change total production volumes). In machine-flexible systems, machines have different capabilities. A list of capabilities is defined for a machine, which enables it to process different operations. Similarly, worker flexibility enables the system to accommodate workers with different skills. For instance, workers can perform different operations or operate a list of machines for which they have the required ability. Worker flexibility is addressed through different perspectives in the literature. Cesani and Steudel¹⁴ argued that it comprises the decisions about the number of workers required, the number of skills for which workers should be cross-trained, and the assignment of workers to machines. Yue et al.¹⁵ discussed that the level of multi-functionality, the pattern of skill overlaps and the distribution of skills can be accepted as worker flexibilities. According to Hamedi et al.,¹⁶ it is the system’s responsiveness to the variations in the supply and demand of workers.

There have been many studies on succeeding flexibility in cellular manufacturing (CM) systems. Askin et al.¹² developed a methodology for the design of flexible CM systems considering machine, routing, part volume and mix flexibilities. Mungwattana¹⁷ studied the design of CM systems considering routing flexibility. Aryanezhad et al.¹⁸ included routing, machine and worker flexibilities in their model for the dynamic CF problem. Chan et al.¹⁹ studied the machine–part grouping problem with the considerations of machine flexibility, alternative process plans for products, machine aggregations and machine breakdown issues. A genetic algorithm was employed to solve the problem. Worker flexibility is also studied by Murali et al.,²⁰ Hamedi et al.,¹⁶ and Nikoofarid and Aalaei²¹ in VCMSs. Goldengorin et al.⁵ proposed a flexible CF model based on the p-median problem to adapt real-life constraints such as capacities and operational sequences. Flexibility also has a positive impact in designing manufacturing cells under dynamic operating conditions. Flexibility may reduce the need for frequent reconfiguration and related cost in real-manufacturing systems. Several authors also presented some research on this issue. Bagheri and Bashiri²² considered a real-world case for the dynamic CF problem and proposed a hybrid solution approach using genetic and imperialist competitive algorithms. They presented a flexible model where the objective weights can be defined by the decision maker according to the desired strategy. Paydar and Saidi-Mehrabad²³ developed a bi-objective possibilistic optimization model under uncertain demands and capacities for the dynamic virtual CF problem in a multi-period production-planning environment. Multi-choice goal programming approach was applied to solve the model, and a real-industrial case was studied to validate the applicability of the proposed approach.

Norman et al.²⁴ developed a model for worker assignment in manufacturing cells that considers both human and technical skills and their impact on system performance. The proposed model also enables changing the skill levels of workers by providing them with additional training. The test results of the study indicated that the model provides better worker assignments than the one that only considers technical skills. Bidanda et al.⁸ presented a review on the issues related to workers and stakeholders in a CM system. The study asserts the idea that all stakeholders must be included both in the design and in the implementation processes in order to achieve a successful impact on the shop floor. Slomp et al.²⁵ developed a multi-objective design procedure for designing virtual cells in dynamic manufacturing environments. The procedure consists of two stages. In the first stage, it performs the allocation of machines and jobs to the virtual cells. In the second stage, the workers are assigned to the virtual cells by considering factors such as ensuring balanced loads for workers, minimizing intercellular movements of workers and providing adequate levels of labor flexibility. Aryanezhad et al.¹⁸ developed a model to deal with the simultaneous dynamic CF and worker assignment problems. They addressed part–routing flexibility and machine flexibility and also promotion of workers from one skill level to another. Mahdavi et al.²⁶ presented an IP model for the dynamic CF problem considering multi-period production planning, dynamic system reconfiguration, duplicate machines, machine capacity, available time of workers and worker assignment. Mahdavi et al.²⁷ developed an IP model to solve the CF problem and minimize the number of voids and exceptional elements in a three-dimensional machine–part–worker incidence matrix. The proposed mathematical model captures the capability of workers in doing different jobs. Nikoofarid and Aalaeib²¹ presented a mathematical model for a production-planning problem in dynamic virtual cells by considering the demand and part mix variations, machine capacities and the availability of the workers. Another study in dynamic systems was proposed by Soolaki.²⁸ In Soolaki’s study, a mathematical model is developed first for the multi-period CF problem by considering available time of workers, worker skills and system reconfiguration, and later, an elitist multi-objective genetic algorithm is proposed for solving the mathematical model in order to find Pareto-optimal solutions. Hamedi et al.¹⁶ proposed a mathematical model with multiple objectives for virtual CF problem using the concept of REs. In this study, unique and shared capability boundaries of machine tools are represented using REs. By this way, forming independent cells becomes easier, and utilization of cells increases. Workers are included in the system as second important resources. Using the developed model, parts, machines and workers are grouped and assigned to the generated virtual cells at the same time. The proposed model is solved through a multi-objective tabu search algorithm to find optimum or near-to-optimum solutions. Their approach presented better results in machine utilization, flexibility and sensitivity to variable demands, when it was compared to machine-based approaches. Bashiri and Bagheri²⁹ developed a two-stage heuristic solution approach. In the first stage, a heuristic multivariate clustering technique is proposed to solve the CF problem, which minimizes the total intercellular part trips. The first stage provides a candidate solution for the second stage in which the worker-related issues are handled by the proposed mathematical model. Similar to Slomp et al.,²⁵ Süer et al.³⁰ considered the CF and worker assignment issues in separate stages. In the first stage, manpower allocation is done, which is subsequently followed by the cell loading stage. They proposed a mathematical model in a multi-period production-planning environment with the aim of maximizing production rate and minimizing total tardiness subject to total crew size. The study was repeated for three cases, respectively, where the operator sharing is allowed, not allowed and allowed with some restrictions. The results showed that when the operator sharing is allowed, the output rates become maximal. Saidi-Mehrabada et al.³¹ developed a mathematical model for dynamic systems, which integrates production planning and worker training by considering machine and worker time availability, operation sequence and multi-period planning horizon. The performance criterion for the study is to minimize machine maintenance and overhead, system reconfiguration, backorder and inventory holding costs and training and worker hiring costs. The interactional interest between workers is studied in the proposed bi-objective mathematical model of Mahdavi et al.³²ε-Constraint method is utilized to solve the proposed model. They reported that increasing the interactional interest level in worker groups increases the cooperation and coordination between workers and increases the system efficiency as well. The proposed method was applied to four randomly generated case problems using Lingo optimization software, and the results were reported as promising in small-scale problems. Also, in the study of Bootaki et al.,³³ a cubic CF problem is presented with two nonhomogeneous objective functions in order to minimize the intercellular movements and maximize a part quality index. Part quality index arises from the relationships among parts, machines and workers. For instance, in the worker–machine relationship, the expertise of workers with different machines has an effect on the quality of the parts produced. To solve the problem, a hybrid genetic algorithm augmented ε-constraint method was proposed. Learning effect and flexibility of workers were discussed by Sadeghi et al.³⁴ where a nonlinear mathematical model was proposed to solve the dynamic CF problem. Inter-/intracellular movements, machine relocation cost and worker-related costs such as hiring/firing/training were considered in the model.

The literature survey shows that the concept of worker involvement in CM has been studied by considering many different performance criteria such as minimizing cost, number of intercellular movements, dissimilarity among parts and total tardiness and maximizing the output, multi-functionality of workers and utilization. The main constraints in the studies have been stated as availability of workers and machines in terms of time and capability to perform the job. Using duplicate machines, allowance of operator sharing, addition/removal of machine types, machine processing capabilities and worker skills have been considered as the system flexibilities in the reviewed studies. It is also possible to categorize the studies as the ones that perform in a dynamic manufacturing environment and use multi-time periods for CF, and the ones that perform in a static environment.

Although CF and CP are extensively studied separately in the literature, very little research has been conducted on the CF problem using CP approach. Mak and Ma³⁵ studied on virtual cells and presented a model that contains a hybrid algorithm combining particle swarm optimization (PSO) and benefits of CP programming technique. By this way, CP can handle the hard constraints of complex problems for which PSO remains stagnated. Soto et al.³⁶ modeled the CF problem and used CP techniques to solve it. Different optimization models are developed, and two different CP-based solving engines are used. The results of the study were promising considering the runtime in that the global optimum is reached. Soto et al.³⁷ modeled the CF problem using an array-based clustering approach. The processing requirements of the parts are given through an incidence matrix, and the machine–part groups are generated using five different solvers: two CP-based solvers, two Boolean satisfiability (SAT)-based solvers and a hybrid CP + SAT solver. The results demonstrated the feasibility of using the proposed approach as well as the good performance of the proposed models. Indeed, the global optimum was reached for all instances in short computational time. Subhaa and Jawahar³⁸ proposed a study for the CF problem with the objective of minimizing the sum of scheduling, cross-flow, intercellular movement and machine duplication costs in the system. They used CP as a solution approach, and the optimal solution was found in reasonable computation time for the small- and medium-sized problems. However, the optimal solution could not be found for the large-sized problems due to the incapability of the solver.

After the literature review, it is observed that CP has not been used as a solution approach for the CF problem that considers the worker assignment under nonflexible and flexible manufacturing settings. In this study, we have shown that the problem can also be easily defined by making use of the benefits of the CP approach.

CP

CP can be an effective method for solving practical problems. In CP, a problem, which has constraints in its structure, can be represented as a constraint satisfaction problem (CSP), the way how the problem is modeled as a CSP can have a significant effect on the solution time or indeed whether it can realistically be solved or not.³⁹ The relations among the variables are represented by constraints, and there exists a corresponding domain for each variable. The problem is to assign a proper value to every variable such that all constraints are satisfied. The domain of the variable x, D_x, is a set of all possible values, which are numerical, Boolean or symbolic.

Two general approaches are used to solve a CSP, which are search and deduction. Both of these approaches aim to transform a hard problem into an easier one. Search works by guessing instantiations of all variables that satisfy all of the constraints. A good guess means a result, which is nearer to the goal. The simplest search algorithm for CSPs is backtracking, which traverses the search graph in a depth-first manner. Deduction in CSP framework is known as constraint propagation or consistency enforcing. In this approach, the problem is transformed into an equivalent but more explicit form.

Constraint propagation is an iterative algorithm which propagates the effects of domain alternations of a variable to any constraint that has an interaction with that variable. This process is repeated until all variable values are consistent with the constraints. If a domain becomes empty during these iterations, it means that there is no solution.

Domain reduction, which is also called consistency technique, modifies the domains of all variables in a constraint whenever a variable’s domain in that constraint is modified. The main consistency techniques are node consistency, arc consistency and path consistency. The CSP is usually represented as a constraint graph (network) where nodes correspond to variables, and edges are labeled as constraints.⁴⁰ That is why the basic consistency techniques derived their names from graph notions.

CP has two main contributions to the combinatorial optimization problems that can also be defined as CSPs:

It is a new approach, which is orthogonal and complementary to standard operation research methods.

It is a new language in which the constraints can be defined in an easier way, and different search procedures can be developed.

CP has been considered as a powerful tool to solve combinatorial problems such as vehicle routing,⁴¹ employee scheduling,⁴² production scheduling⁴³ and manufacturing CF.^35–38 It provides a rich language to represent complex constraints, and solution time can be decreased by applying different search procedures.

Development of the models

The present CF problem is formulated and solved using the proposed IP and CP models. The following assumptions are made in the development of the models:

REs are used to define the processing requirements of parts and the processing capabilities of machines and workers.

Machines and workers can be duplicated at an additional cost. If a machine or a worker is assigned to a cell, then its duplicate cannot be assigned to the same cell.

Intercellular movements between cells are not allowed.

Upper limits and lower limits for the number of machines, parts and workers assigned to a cell are predetermined.

A total of 12 case problems are generated and solved by both of the proposed models and then the results are compared and discussed.

The proposed IP model

The following notation is given for the formulation of the proposed IP model.

Indices.

I	Index for parts (i = 1, 2, …, P)
j	Index for machines (j = 1, 2, …, M)
k	Index for cells (k = 1, 2, …, C)
r	Index for REs (r = 1, 2, …, R)
w	Index for workers (w = 1, 2, …, W)

Parameters.

Lom	Minimum number of machines that should be assigned to a cell
Upm	Maximum number of machines that can be assigned to a cell
Loi	Minimum number of parts that should be assigned to a cell
Upi	Maximum number of parts that can be assigned to a cell
Low	Minimum number of workers that should be assigned to a cell
OpPart_ir	Is 1 if part i requires RE r, 0 otherwise
OpMach_jr	Is 1 if machine j is capable of RE r, 0 otherwise
OpWorker_wr	Is 1 if worker w is capable of RE r, 0 otherwise
MacCost_j	Cost of assigning machine j to a cell
WrkrCost_w	Cost of employing an extra worker w for a cell
MacDupCost	Machine duplication cost
WrkrDupCost	Worker duplication cost
MCapacity_j	Total capacity of machine j
WCapacity_w	Total capacity of worker w
PTimes_ir	Processing time for part i to perform RE r
PQuan_i	Total demand for part i

Decision variables.

X_ik	Is 1 if part i is assigned to cell k, 0 otherwise
Y_jk	Is 1 if machine j is assigned to cell k, 0 otherwise
Z_wk	Is 1 if worker w is assigned to cell k, 0 otherwise

Objective function

M i n i m i z e M a c D u p C o s t + W r k r D u p C o s t

(1)

where

M a c D u p C o s t = \sum_{k = 1}^{C} \sum_{j = 1}^{M} Y_{j k} * M a c C o s t_{j} \sum_{j = 1}^{M} M a c C o s t_{j}

(1a)

W r k r D u p C o s t = \sum_{k = 1}^{C} \sum_{w = 1}^{W} Z_{w k} * W r k r C o s t_{w} - \sum_{w = 1}^{W} W r k r C o s t_{w}

(1b)

The objective function aims to minimize total cost, which is the sum of the machine duplication cost MacDupCost and the worker duplication cost WrkrDupCost. Initially, the system has M number of machines, but it is possible to buy as many machines as required if it is necessary, provided that a duplicate of a machine is not assigned to the same cell. The function $\sum_{j = 1}^{M} M a c C o s t_{j}$ calculates the cost of initially available M machines. When the allocation of these machines to cells is completed, Y_jk becomes 1 for all values of k such that a duplicate of machine j is assigned to a cell where machine j itself has not been assigned to. Thus, in order to calculate the machine duplication cost in the system, the total cost for the initial number of machines is subtracted from the total cost for the final number of machines including the duplications. It is also possible to add new workers in the system in order to satisfy the worker requirements in any cell, which results in worker duplication cost, and it is calculated in the same manner as the machine duplication cost.

Constraints

\sum_{j = 1}^{M} Y_{j k} ⩾ L o m \forall k

(2)

\sum_{j = 1}^{M} Y_{j k} ⩽ U p m \forall k

(3)

\sum_{k = 1}^{C} Y_{j k} ⩾ 1 \forall j

(4)

\sum_{k = 1}^{C} Z_{w k} ⩾ 1 \forall w

(5)

\sum_{k = 1}^{C} X_{i k} = 1 \forall i

(6)

\sum_{i = 1}^{P} X_{i k} ⩾ L o i \forall k

(7)

\sum_{i = 1}^{P} X_{i k} ⩽ U p i \forall k

(8)

\sum_{w = 1}^{W} Z_{w k} ⩾ L o w \forall k

(9)

\sum_{j = 1}^{M} Y_{j k} * O p M a c h_{j r} ⩾ X_{i k} * O p P a r t_{i r} \forall k, i, r

(10)

\sum_{w = 1}^{W} Z_{w k} * O p W r k r_{w r} ⩾ X_{i k} * O p P a r t_{i r} \forall k, i, r

(11)

\sum_{j = 1}^{M} Y_{j k} * M C a p a c i t y_{j} - \sum_{i = 1}^{P} \sum_{r = 1}^{R} X_{i k} * O p P a r t_{i r} * P T i m e s_{i r} * P Q u a n_{i} ⩾ 0 \forall k

(12)

\sum_{j = 1}^{M} Y_{j k} * O p M a c h_{j r} * M C a p a c i t y_{j} - \sum_{i = 1}^{P} X_{i k} * O p P a r t_{i r} * P T i m e s_{i r} * P Q u a n_{i} ⩾ 0 \forall k, r

(13)

\sum_{w = 1}^{W} Z_{w k} * W C a p a c i t y_{w} - \sum_{i = 1}^{P} \sum_{r = 1}^{R} X_{i k} * O p P a r t_{i r} * P T i m e s_{i r} * P Q u a_{i} ⩾ 0 \forall k

(14)

\sum_{w = 1}^{W} Z_{w k} * O p W r k r_{w r} * W C a p a c i t y_{w} - \sum_{i = 1}^{P} X_{i k} * O p P a r t_{i r} * P T i m e s_{i r} * P Q u a_{i} ⩾ 0 \forall k, r

(15)

Constraints (2) and (3) represent the lower and upper limits for the number of machines assigned to a cell (which are Lom and Upm, respectively). Constraint (4) provides that a machine can be assigned to more than one cell since it is possible to duplicate the machine for another cell. Similarly, constraint (5) assumes that a worker can be assigned to more than one cell since it is possible to employ a similar worker for another cell. Constraint (6) enforces the requirement that each part should be assigned to only one cell. Constraints (7) and (8) set the lower and upper limits for the number of parts assigned to a cell (which are Loi and Upi, respectively). Constraint (9) states the lower limit for the number of workers that should be assigned to a cell. Constraint (10) assures that a part can only be assigned to a cell if already a machine with the required capability (in terms of RE) to process the part is assigned to the same cell. Similarly, constraint (11) states that a part can only be assigned to a cell if already a worker with the required capability (in terms of RE) to process the part is assigned to the same cell. Each machine has a capacity for working in a single run or shift. The total demand of each part and their processing times are predefined in the system. Using these data, constraint (12) ensures that the total machine capacity in each cell is enough for the total processing time requirement of each cell. However, even though the total potential capacity seems enough, in some cases, there may still be capacity lacks for some REs in a cell.² Constraint (13) ensures that there is enough capacity in the cell for the required REs that correspond to the processing requirements of the assigned parts. Therefore, constraints (12) and (13), when working together, ensure that the system has a certain capacity for the overall processing requirements of the parts that are assigned to a cell. These constraint functions were initially developed by Baykasoglu and Gindy² in order to control capacities where part’s processing requirements are not defined in terms of fixed machine routes. Constraints (14) and (15) work in a similar fashion to control worker capacities.

The proposed CP model

The proposed CP model is developed in IBM ILOG optimization modeling language (OPL).⁴⁴ During the implementation of the CP model, some features of OPL are benefited such as using a special type of data structure, tuple, that clusters together closely related data. The data for OpPart, OpMach and OpWrkr (they are defined as 0–1 matrices indicating the required REs of the parts and the RE-based capabilities of machines and workers, respectively, for the IP model) are generated using tuple data structure for CP model. This data type gathers related information as attributes of the tuple. For example, OpWkr data contain the worker numbers (Ids) and a set for the RE-based capabilities of each worker, as attributes of the tuple data. When developing a large-scale optimization model, it is advantageous to use modeling issues involving sparsity, tuples of data and filtering in order to increase the efficiency of the model.

\begin{matrix} t u p l e W o r k e r C a p a b i l i t y { \\ i n t W o r k e r I D; / / w o r k e r i d; \\ i n t L i s t O p W r k r []; / / the set that shows the list of REs a worker is capable of doing \\ }; \\ {W o r k e r C a p a b i l i t y} O p W r k r = \dots; \end{matrix}

OpPart	Includes part IDs (PartId), a set of REs that each part requires to be processed (ListOpPart) and a set of processing times for the REs of each part (PTimes)
OpMach	Includes machine IDs (MacId) and a set of REs that each machine is capable of (ListOpMac)
OpWrkr	Includes worker IDs (WorkerId) and a set of REs that each worker is capable of (ListOpWrkr)

In the above example, “WorkerCapability” tuple contains two attributes, which are integer-type WorkerId indicating the worker, and integer array–type ListOpWrkr[ ] that lists the RE-based capabilities of the worker. Each attribute can from different data types. Consequently, a set of data possessing the WorkerCapability tuple structure can be created as OpWkr with the following sample problem data

\begin{matrix} O p W r k r = {< 1, [1, 2, 4] >, < 2, [5] >, \\ < 3, [2, 5] >, < 4, [1, 3] >} \end{matrix}

According to these data, for example, the first worker with WorkerId = 1 has capabilities to perform REs 1, 2 and 4. Similarly, the worker with WorkerId = 4 has capabilities to perform REs 1 and 3.

The additional indices and new variable definitions which are used in the development of the CP model are represented below:

Additional indices.

p	Index for the elements of OpMach data tuple, p ∈ OpMach
o	Index for the elements of OpPart data tuple, o ∈ OpPart
d	Index for the elements of OpWrkr data tuple, d ∈ OpWrkr

Decision variables.

X_i	Is k if part i is assigned to cell k, 0 otherwise, X_i ∈ {1, …, C}
Y_j	Is k if machine j is assigned to cell k, 0 otherwise, Y_j ∈ {1, …, C}
Z_w	Is k if worker w is assigned to cell k, 0 otherwise, Z_w ∈ {1, …, C}
DY _(k−1)*M+j	Is k if a duplicate of machine j is assigned to cell k, 0 otherwise
DZ _(k−1)*M+w	Is k if a duplicate of worker w is assigned to cell k, 0 otherwise

Objective function

M i n i m i z e M a c D u p C o s t + W r k r D u p C o s t

(16)

where

M a c D u p C o s t = \sum_{k = 1}^{C} \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k)

(16a)

W r k r D u p C o s t = \sum_{k = 1}^{C} \sum_{w = 1}^{W} (D Z_{((k - 1) * W + j)} = = k)

(16b)

Constraints

\sum_{j = 1}^{M} (Y_{j} = = k) + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k) ⩾ L o m \forall k

(17)

\sum_{j = 1}^{M} (Y_{j} = = k) + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k) ⩽ U p m \forall k

(18)

\sum_{k = 1}^{C} (Y_{j} = = k) = 1 \forall j

(19)

\sum_{k = 1}^{C} (Z_{w} = = k) = 1 \forall w

(20)

\sum_{k = 1}^{C} (D Y_{((k - 1) * M + j)} = = k) ⩽ 1 \forall j

(21)

\sum_{k = 1}^{C} (D Z_{((k - 1) * W + j)} = = k) ⩽ 1 \forall w

(22)

\sum_{k = 1}^{C} (X_{i} = = k) = 1 \forall i

(23)

\sum_{i = 1}^{P} (X_{i} = = k) ⩾ L o i \forall k

(24)

\sum_{i = 1}^{P} (X_{i} = = k) ⩽ U p i \forall k

(25)

\sum_{w = 1}^{W} (Z_{w} = = k) + \sum_{w = 1}^{W} (D Z_{((k - 1) * W + j)} = = k) ⩾ L o w \forall k

(26)

\begin{matrix} \sum_{j = 1}^{M} (Y_{j} = = k) * \sum_{p \in O p M a c h | p . M a c I d = = j} c a r d (p . L i s t O p M a c i n t e r r) \\ + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k) * \sum_{p \in O p M a c h | p . M a c I d = = j} c a r d (p . L i s t O p M a c i n t e r r) \\ ⩾ (X_{i} = = k) * \sum_{o \in O p P a r t | o . P a r t I d = = i} c a r d (o . L i s t O p P a r t i n t e r r) \forall k, i, r \end{matrix}

(27)

\begin{matrix} \sum_{w = 1}^{W} (Z_{w} = = k) * \sum_{d \in O p W r k r | d . W r k r I d = = w} c a r d (d . L i s t O p W r k r i n t e r r) \\ + \sum_{w = 1}^{W} (D Z_{((k - 1) * W + j)} = = k) * \sum_{d \in O p W r k r | d . W r k r I d = = w} c a r d (d . L i s t O p W r k r i n t e r r) \\ ⩾ (X_{i} = = k) * \sum_{o \in O p P a r t | o . P a r t I d = = i} c a r d (o . L i s t O p P a r t i n t e r r) \forall k, i, r \end{matrix}

(28)

\begin{matrix} \sum_{j = 1}^{M} (Y_{j} = = k) * M C a p a c i t y_{j} + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k) * M C a p a c i t y_{j} \\ - \sum_{i = 1}^{P} \sum_{r = 1}^{R} (X_{i} = = k) * \sum_{o \in O p P a r t | o . P a r t I d = = i} c a r d (o . L i s t O p P a r t i n t e r r) * \sum_{n = 1 | r = = i t e m (o . L i s t O p P a r t, n - 1)}^{c a r d (o . L i s t O p P a r t)} o . P T i m e s_{n} * P Q u a_{i} ⩾ 0 \forall k \end{matrix}

(29)

\begin{matrix} \sum_{j = 1}^{M} (Y_{j} = = k) * \sum_{p \in O p M a c h | p . M a c I d = = j} c a r d (p . L i s t O p M a c inter r) * M C a p a c i t y_{j} \\ + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k) * \sum_{p \in O p M a c h | p . M a c I d = = j} c a r d (p . L i s t O p M a c i n t e r r) * M C a p a c i t y_{j} \\ - \sum_{i = 1}^{P} (X_{i} = = k) * \sum_{o \in O p P a r t | o . P a r t I d = = i} c a r d (o . L i s t O p P a r t i n t e r r) * \sum_{n = 1 | r = = i t e m (o . L i s t O p P a r t, n - 1)}^{c a r d (o . L i s t O p P a r t)} o . P T i m e s_{n} * P Q u a_{i} ⩾ 0 \forall k, r \end{matrix}

(30)

\begin{matrix} \sum_{w = 1}^{W} (Z_{w} = = k) * W C a p a c i t y_{w} + \sum_{w = 1}^{W} (D Z_{((k - 1) * W + j)} = = k) * W C a p a c i t y_{w} \\ - \sum_{i = 1}^{P} \sum_{r = 1}^{R} (X_{i} = = k) * \sum_{o \in O p P a r t | o . P a r t I d = = i} c a r d (o . L i s t O p P a r t i n t e r r) * \sum_{n = 1 | r = = i t e m (o . L i s t O p P a r t, n - 1)}^{c a r d (o . L i s t O p P a r t)} o . P T i m e s_{n} * P Q u a_{i} ⩾ 0 \forall k \end{matrix}

(31)

\begin{matrix} \sum_{w = 1}^{W} (D Z_{((k - 1) * W + j)} = = k) * \sum_{d \in O p M a c h | d . M a c I d = = j} c a r d (d . L i s t O p W r k r i n t e r r) * W C a p a c i t y_{w} \\ - \sum_{i = 1}^{P} (X_{i} = = k) * \sum_{o \in O p P a r t | o . P a r t I d = = i} c a r d (o . L i s t O p P a r t i n t e r r) * \sum_{n = 1 | r = = i t e m (o . L i s t O p P a r t, n - 1)}^{c a r d (o . L i s t O p P a r t) :} o . P T i m e s_{n} * P Q u a_{i} ⩾ 0 \forall k, r \end{matrix}

(32)

I f (Y_{j} = = k) t h e n (D Y_{((k - 1) * M + j)} = = 0) \forall j, k

(33)

Constraint (17) states that the number of machines including duplicated machines assigned to cell k should be equal to or bigger than the lower limit Lom. If machine j is assigned to cell k, $(Y_{j} = = k)$ returns to 1 and 0 otherwise. Similarly, constraint (18) shows the upper limit Upm for the total number of machines that can be assigned to cell k. Constraints (19) and (20) state that each machine and worker should be assigned to only one cell. Constraints (21) and (22) state that duplicate of a machine and a worker can be assigned to a cell if necessary. Constraint (23) ensures that each part should be assigned to only one cell. Constraints (24) and (25) enforce the lower and upper limits for the number of parts that is assigned to a cell. Constraint (26) provides that a minimum number of workers are assigned to a cell. Constraint (27) states that a part can only be assigned to a cell if and only if there is a machine with the required capability (in terms of REs) to process the part is already assigned to the cell. In the second summation of the constraint (27), tuple Opmach and card(set) function appear. Each element p in tuple Opmach has a MacID and a set ListOpMac that keeps the information of the RE capabilities of the corresponding machine. The set expression card(set) returns to the cardinality of the set inside, thus card (p.ListOpMac inter r) returns to the number of elements in the set which is the intersection of $L i s t O p M a c$ and RE r. The only possible result of the given function can be 1 if r is in ListOpMac or 0, otherwise. Similarly, constraint (28) states that a part can only be assigned to a cell if and only if there is a worker with the required capability to process the part that is already assigned to the cell. In constraints (29)–(32), another set expression item (set, a) is used. This function returns to the value of the ath element in the given set. The counting starts at 0. The processing time of RE r required by part i, “ $o . P T i m e s_{n}$ ,” is needed in order to calculate the total processing time of the overall demand

\sum_{n = 1 | r = = i t e m (o . L i s t O p P a r t, n - 1)}^{c a r d (o . L i s t O p P a r t) :} o . P T i m e s_{n}

(33)

Starting from n = 1, item (o.ListOpPart, n − 1) function returns to the value of each element in set ListOpPart and controls if this value is equal to “r.” When “r” value is equal to n, it means that n states the correct position in the array PTimes, for the corresponding processing time value of RE r of part i. Constraints (29) and (30) satisfy the machine capacity requirements for processing the demanded parts, whose equivalent constraints are constraints (12) and (13) in the IP model. Similarly, constraints (31) and (32) satisfy the worker capacity requirements in correspondence to constraints (14) and (15) in the IP model. Finally, constraint (33) states that if a machine is assigned to a cell, the duplicate of that machine cannot be assigned to the same cell. This is a redundant constraint developed for constraining the solution space further during the search.

Symmetry breaking constraints

\sum_{i = 1}^{P} (X_{i} = = k) ⩽ \sum_{i = 1}^{P} (X_{i} = = k - 1) \forall k | k 〉 1

(34)

I f (\sum_{i = 1}^{P} (X_{i} = = k) = = \sum_{i = 1}^{P} (X_{i} = = k - 1)) t h e n \sum_{j = 1}^{M} (Y_{j} = = k) + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k) ⩽ \sum_{j = 1}^{M} (Y_{j} = = k - 1) + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k - 1) \forall k | k 〉 1

(35)

\begin{matrix} I f (\sum_{i = 1}^{P} (X_{i} = = k) = = \sum_{i = 1}^{P} (X_{i} = = k - 1)) && \\ (\sum_{j = 1}^{M} (Y_{j} = = k) + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k) = = \sum_{j = 1}^{M} (Y_{j} = = k - 1) + \sum_{j = 1}^{M} (D Y_{((k - 1) * M + j)} = = k - 1)) \\ t h e n \sum_{w = 1}^{W} (Z_{w} = = k) + \sum_{w = 1}^{W} (D Z_{((k - 1) * W + j)} = = k) \\ ⩽ \sum_{w = 1}^{W} (Z_{w} = = k - 1) + \sum_{w = 1}^{W} (D Z_{((k - 1) * W + j)} = = k - 1) \forall k | k 〉 1 \end{matrix}

(36)

Constraints (34)–(36) are symmetry breaking constraints that prevent the formation of equivalent solutions such as those given in Table 1. For example, two alternative possible optimal solutions can be as given in example 1.

Table 1.

Examples to symmetric solutions.

	Example 1		Example 2
	Cell 1	Cell 1	Cell 1	Cell 2
Solution 1	P1, P2	P3, P4, P5	P1, P2	P3, P4
	M1, M3	M2, M4	M1, M3	M2, M4
	W2	W1, W3	W2	W1, W3
Solution 2	P3, P4, P5	P1, P2	P3, P4	P1, P2
	M2, M4	M1, M3	M2, M4	M1, M3
	W1, W3	W2	W1, W3	W2

Two solutions in example 1 are same since the created cells are identical except their order of appearance. To prevent this symmetry, constraint (34) is developed to rank the number of part assignments to the cells in the descending order. By enforcing this constraint, the only possible solution acquiring this arrangement is the second solution. In this way, the unnecessary solution effort to find the first solution during the search process of CP solver is prevented.

Another symmetric solution may occur when the number of parts assigned to the cells is equal as in example 2 in Table 1. In this case, constraint (34) does not help to prevent the symmetry since the part numbers are already equal. For a situation like this, constraint (35) ranks the number of machine assignments to the cells in the descending order to prevent the formation of identical solutions such as in example 2. If the number of machine assignments to the cells is also equal, this time constraint (36) breaks the symmetry by ranking the number of workers assigned to the cells in the descending order. In this way, the only possible solution that can be obtained with the proposed symmetry breaking constraints is solution 2 for example 2.

Illustration of a case problem

The data for the case problem include 10 parts, 7 machines, 6 workers, 8 REs and 2 cells. All of the required problem data are given in Tables 2 –4. The objective is to minimize the sum of machine and worker duplication costs. The lower and upper limits for the number of machines assigned to a cell are taken as 2 and 5, respectively. The lower and upper limits for the number of parts assigned to a cell are considered as 3 and 7, respectively. At least one worker should be assigned to each cell. Parts require a set of REs to be processed, and machines and workers are only capable of processing a specified set of REs. Thus, a part should be processed on machines which have required REs, and eligible workers should be assigned to operate the machines for the required REs.

Table 2.

RE capabilities of workers.

Workers/REs	RE 1	RE 2	RE 3	RE 4	RE 5	RE 6	RE 7	RE 8	Worker cost	Worker capacity
W1			*		*				100	500
W2						*		*	200	600
W3	*		*				*		200	500
W4		*		*				*	150	400
W5				*	*				150	400
W6	*	*				*			400	500

RE: resource element.

represent availability of REs.

Table 3.

RE requirements of parts with processing times.

Parts/REs	RE 1	RE 2	RE 3	RE 5	RE 6	RE 8	Part demands
P1			*(2)	*(2)		*(3)	60
P2	*(3)	*(2)					120
P3			*(1)		*(1)	*(3)	50
P4	*(2)						180
P5	*(1)		*(1)				180
P6	*(3)			*(2)			140
P7	*(1)				*(2)		130
P8	*(2)						190
P9		*(1)					190
P10		*(2)					120

RE: resource element.

represent availability of REs.

Table 4.

RE capabilities of machines.

Machines/REs	RE 1	RE 2	RE 3	RE 4	RE 5	RE 6	RE 7	RE 8	Machine cost	Machine capacity
M1		*	*	*					200	600
M2	*					*			200	600
M3				*				*	300	700
M4			*	*			*		150	600
M5					*	*			200	500
M6	*				*			*	300	600
M7		*					*		150	400

RE: resource element.

represent availability of REs.

The IP model for the case problem contains 47 variables and 389 constraints, whereas the CP model contains 49 variables and 3993 constraints. With regard to constraints, their number is much larger in the CP model because the CP solver needs to generate more domain information about the variables from the compact formulation of the problem in order to perform an effective domain reduction. The optimum value of the objective function is 1100, which is found in 1.73 s via IP and 1.21 s via CP. The optimal solution is similar for both the models, except that in the IP solution, parts 2, 3, 5, 6 and 9 are assigned to cell 1, and parts 1, 4, 7, 8 and 10 are assigned to cell 2, whereas in the CP solution, part 4 is also assigned to cell 1, instead of being assigned to cell 2. In both the solutions, machines 1, 5 and 6 are assigned to cell 1, and machines 2, 3, 4 and 7 are assigned to cell 2. Workers 1, 2 and 6 are assigned to cell 1, and workers 3, 4 and 5 are assigned to cell 2. Additionally, a duplicate of machine 2 is assigned to cell 1, and a duplicate of machine 6 is assigned to cell 2 with a total cost of 500, whereas a duplicate of worker 3 is assigned to cell 1, and a duplicate of worker 6 is assigned to cell 2 with a total cost of 600, thus resulting in a total cost of 1100.

Comparative analysis of IP and CP models

A comparative analysis of the IP and CP models is made in this section using 12 test problems. The dataset for each test problem is generated by a specially developed Java application. Part demands and the capacities of workers and machines are uniformly distributed between the given upper and lower limits using the Java random number generator function (Oracle Java 8 Random Javadocs⁴⁵). The costs values are entered manually according to the capabilities and the capacities of the workers and machines. The part requirements and the capabilities of machines and workers are randomly assigned to 0 or 1. The developed Java application generates the data files of the IP and CP models. Datasets for the test problems can be obtained from the authors. The details about the test problems in terms of the number of parts, machines, workers, REs and cells are given in Table 5. The test problems are solved using both IP and CP models. All experiments are performed on an Intel Core i7,6500U 2.5-GHz central processing unit (CPU) machine running Windows 10 with 8 GB of main memory, using IBM CPLEX Optimization Studio V12.6.1.

Table 5.

Size characteristics of the test problems.

Test problem	Number of parts	Number of machines	Number of workers	Number of REs	Number of cells
1	4	4	4	4	2
2	7	5	4	5	2
3	10	7	6	8	2
4	15	7	6	10	3
5	22	10	6	11	3
6	25	10	7	11	3
7	30	12	7	12	3
8	35	15	9	12	3
9	40	18	10	12	3
10	50	20	12	15	3
11	75	25	15	15	3
12	100	30	18	15	3

RE: resource element.

The computational results which are shown in Table 6 present that both models are converged to the optimum solutions within <1 min for the entire test problems, except for test problem 10, which is only 67 s via CP. It can be noted that the CP model performs slightly worse than the IP model regarding the solution time. The allowance of duplicate machines and workers seems to have an adverse effect on the solution efficiency of the CP model. The efficiency of the CP model is dependent on intense constraint propagation and domain reduction issues. In this problem, the linkage between the variables that deal with the assignment of available machines and workers and the variables that deal with the assignment of duplicate machines and workers is not so strong, and thus, it may result in numerous possible configurations for the formation of work cells. The effectiveness of CP increases for highly constrained problems. The performance of the CP model increases when the total machine capacity is close to the total machining requirements, and the machines have more mutually exclusive RE capabilities. Also, the same argument is valid for the worker capacity. For example, in test 1, the rates of part requirements to the machine and worker capacities are 0.941 and 0.842, respectively, whereas in test 12 these values are 0.427 and 0.534, respectively.

Table 6.

Computational results of the IP and CP models.

Test problems	Solution time (s)		Optimal value	Number of constraints		Number of variables
Test problems	IP	CP	Optimal value	IP	CP	IP	CP
1	0.52	0.15	200	106	811	25	28
2	1.08	0.26	100	190	1582	33	34
3	1.73	1.21	1100	389	3993	47	49
4	1.39	18.01	800	1009	10,736	85	67
5	1.08	6.22	400	1577	19,149	115	86
6	1.61	15.06	400	1779	22,472	127	93
7	2.20	6.84	300	2302	31,340	148	106
8	0.86	7.35	200	2672	42,977	178	131
9	1.64	26.29	100	3041	54,915	205	152
10	0.84	67.02	200	4693	93,885	247	178
11	1.19	44.2	200	6976	167,099	346	235
12	1.22	54.13	200	9259	258,313	445	292

IP: integer programming; CP: constraint programming.

Additionally, the CP model is also resolved for the test problems using the “FailLimit” parameter to speed up the search. This parameter stops the search when the number of fails during the search reaches a certain number. In OPL, this parameter is expressed using the “cp.param.FailLimit” command. The computational results with different FailLimit values for each test problem are presented in Table 7. Accordingly, the solution times are reduced in most of the tests when the FailLimit parameter is used.

Table 7.

Computational results of the CP model with FailLimit parameter.

Case problems	Optimal value	Solution time (s)
Case problems	Optimal value	FailLimit (50,000)	FailLimit (100,000)
1	200	0.15	0.15
2	100	0.25	0.25
3	1100	1.09	1.23
4	800	4.82	9.54
5	400	7.58	7.84
6	400	9.7	16.95
7	300	7.31	7.56
8	200	7.92	8.01
9	100	23.54^a	36.6
10	200	24.76	36.96
11	200	42.7	45.12
12	200	59.68	59.71

Optimum solution is not found.

Search phases

It is possible to change the default search type while executing the CP model. The user can define search phases to guide the search by ordering the search moves and the values to be tested. This also refers to the terms “variable ordering” and “value ordering” in CP. Variable ordering guides the search in a way that it has some specifications to decide which variables are chosen for instantiation. Value ordering deals with the ordering of possible values to be assigned to the chosen variable. In this study, two different search phases are defined in the OPL language:

Phase 1.

execute {

var f = cp.factory;

varmultiPhaseVar = new Array(f.selectLargest(f.impactofLastBranch()),f.selectRandomVar());

varmultiPhaseValue = new Array(f.selectLargest(f.valueImpact()),f.selectRandomValue());

var phase1 = f.searchPhase(multiPhaseVar,multiPhaseValue); }

In phase1, the variables with the largest impact value on the last branch are selected, which equals to the domain reduction achieved with the last instantiation on the evaluated variables. The range of the result is between 0 and 1.0. If it is close to 0, it means a little domain reduction is achieved on the evaluated variable by the last assignment. If the result is close to 1, the domain is reduced significantly. Then, a variable is randomly selected from this set. The value to be assigned to the selected variable is done randomly by selecting a value from the set of values with largest value impact.

Phase 2.

execute {

var f = cp.factory;

varmultiPhaseVar = new Array(f.selectLargest(f.impactofLastBranch()),f.selectLargest(f.valueImpact));

varmultiPhaseValue = new Array(f.selectLargest(f.valueImpact()),f.selectLargest(f.valueSuccessRate));

var phase1 = f.searchPhase(multiPhaseVar,multiPhaseValue); }

In phase 2, the variable selection is done in a similar way as in phase 1. The ordering of the values is done according to the largest value impact and then to the largest success rate.

The results obtained are given in Table 8 when the search phases are implemented. It is seen that the use of search phase with FailLimit parameter decreases the time spent in the search for most of the tests. The results show that the adopted search phases 1 and 2 lead the search in a good manner and find the optimal solution in <1 min for all of the tests this time. Although the impact of using search phases is not so prominent in our problem due to already short computation times, it should be noted that the variable and value ordering strategies can have profound effect on the efficiency of search for an optimum when coupled with constraint propagation and domain reduction.

Table 8.

Solution times of tests with search phases in CP approach using fail limit.

	Test1	Test 2	Test 3	Test 4	Test 5	Test 6	Test 7	Test 8	Test 9	Test 10	Test 11	Test 12
No phase no limit	0.15	0.26	1.21	18.01	6.22	15.06	6.84	7.35	26.29	67.3	44.2	54.4
Phase 1	0.12	0.26	1.20	6.90	5.93	6.68	6.76	7.70	35.03	43.26	41.35	54.12
Phase 2	0.14	0.25	1.14	7.20	6.01	7.87	6.72	7.38	35.57	42.89	42.12	54.7
FailLimit	–	–	20,000	75,000	30,000	30,000	20,000	10,000	150,000	150,000	150,000	150,000

Conclusion

This article proposes IP and CP models for the CF problem that considers machine, part processing and worker flexibilities simultaneously. The flexibilities make it possible to process a part on alternative machines with alternative workers as long as these machines and workers have the required capabilities. The assignment of parts, machines and workers to manufacturing cells is done concurrently on the RE basis while trying not to exceed the workforce and machine capacities.

CP provides an advantage of flexible and easy modeling in formulating many constraints encountered in production environments. This study is the first attempt that uses CP in modeling the CF problem with the mentioned flexibilities and worker assignment considerations. CP searches the solution space in a tree-search-based manner using the consistency and constraint propagation techniques. The advantages of CP over IP are that CP represents the problem more explicitly than the IP model, and it is possible to devise different variable and value ordering strategies for a more efficient search of CP.

In order to evaluate the performance of IP and CP models, 12 test problems are generated and solved using both models. According to the computational results, all test problems are solved within <1 min. However, CP model gives higher computational times than the IP model. This can be attributed to the fact that the constraints involve a large number of variables including the decision of assigning a duplicate machine or a worker to each cell. Constraint propagation may be less successful when CP requires the labeling of a large number of variables.

This study also proposes problem-specific symmetry breaking constraints to eliminate the formation of alternative optimal solutions and redundant constraints to increase constraint propagation in order to achieve relatively comparable solution times to the IP model. The computational results show that the proposed CP model is promising for the solution of the CF problem. It can also be asserted that CP can be much more effective when the number of machines and workers is limited, and they have mutually exclusive capabilities.

Developing CP-IP hybrid models and benefiting the advantages of both approaches can be considered as a future study for the solution of the present CF problem. Moreover, the model can also be extended by considering several other practical constraints such as cell utilization, machine reliability, load balancing and so on. It is also possible to take into account learning curve and skill development of workers which effects processing times. The present model can also be converted into a dynamic model by integrating it with multi-period production planning.

Some of the other limitations of this article and proposed approach are as follows: Operation sequences of parts are not taken into account in this study. Operation sequence–based similarities can be taken into account in future models. Flexibility of manufacturing cells is becoming an important design criterion as manufacturing systems are facing increasing dynamism. Flexibility-related design criteria are not taken into account in this article. Several flexibility-related criteria such as routing flexibility and operation flexibility can be taken into consideration. All data are considered as crisp in the present approach. However, in real-life setting, several uncertainties can exist. Therefore, fuzzy and/or stochastic extension of the proposed model can be developed. Moreover, real-life application of the proposed model can be very useful.

Footnotes

Declaration of conflicting interests

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

Funding

The author(s) received no financial support for the research, authorship and/or publication of this article.

References

Moon

. Forming part-machine families for cellular manufacturing: a neural-network approach. Int J Adv Manuf Tech 1990; 5(4): 278–291.

Baykasoglu

Gindy

NNZ

. MOCACEF 1.0: multiple objective capability based approach to form part-machine groups for cellular manufacturing applications. Int J Prod Res 2000; 38(5): 1133–1161.

Baykasoglu

. Quantifying machine flexibility. Int J Prod Res 2009; 47(15): 4109–4123.

Dahel

Smith

. Designing Flexibility into cellular manufacturing systems. Int J Prod Res 1993; 31(4): 933–945.

Goldengorin

Krushinsky

Slomp

. Flexible PMP approach for large-size cell formation. Oper Res 2012; 60(5): 1157–1166.

Browne

Dubois

Rathmill

et al . Classification of flexible manufacturing systems. FMS Mag 1984; 2: 114–117.

Sethi

. Flexibility in manufacturing: a survey. Int J Flex Manuf Sys 1990; 2(4): 289–328.

Bidanda

Ariyawongrat

Needy

et al . Human related issues in manufacturing cell design, implementation, and operation: a review and survey. Comput Ind Eng 2005; 48(3): 507–523.

Gindy

NNZ

Ratchev

Case

. Component grouping for cell formation using resource elements. Int J Prod Res 1996; 34(3): 727–752.

10.

Liang

Fung

RYK

. Coordination mechanism in real-time scheduling of virtual cellular manufacturing systems. Proc IMechE, Part B: J Engineering Manufacture 2016; 230(3): 534–547.

11.

Baykasoglu

. Uretim Ortamlarinin Fraktal Resmi: Kaynak Elemanlari Bakis Acisi [Fractal picture of manufacturing environments: resource elements view]. Otomasyon 2001; 2: 134–140 (in Turkish).

12.

Askin

Selim

Vakharia

. A methodology for designing flexible cellular manufacturing systems. IIE Trans 1997; 29: 599–610.

13.

Goyal

. Managing operational flexibility under demand uncertainty. PhD Dissertation, University of Pennsylvania, Philadelphia, PA, 2005.

14.

Cesani

Steudel

. A study of labor assignment flexibility in cellular manufacturing systems. Comput Ind Eng 2005; 48(3): 571–591.

15.

Yue

Slomp

Molleman

et al . Worker flexibility in a parallel dual resource constrained job shop. Int J Prod Res 2008; 46(2): 451–467.

16.

Hamedi

Esmaeilian

Ismail

et al . Capability-based virtual cellular manufacturing systems formation in dual-resource constrained settings using Tabu Search. Comput Ind Eng 2012; 62(4): 953–971.

17.

Mungwattana

. Design of cellular manufacturing systems for dynamic and uncertain production requirements with presence of routing flexibility. PhD Dissertation, Virginia Polytechnic Institute and State University, Blacksburg, VA, 2000.

18.

Aryanezhad

Delioo

Mirzapour Al-e-hashem

SMJ

. Dynamic cell formation and the worker assignment problem: a new model. Int J Adv Manuf Tech 2009; 41(3): 329–342.

19.

Chan

FTS

Lau

Chan

PLY

. A holistic approach to manufacturing cell formation: incorporation of machine flexibility and machine aggregation. Proc IMechE, Part B: J Engineering Manufacture 2004; 218(10): 1279–1296.

20.

Murali

Puri

Prabhakaran

. Artificial neural networks based predictive model for worker assignment into virtual cells. Int J Eng Sci Tech 2010; 2(1): 163–174.

21.

Nikoofarid

Aalaei

. Production planning and worker assignment in a dynamic virtual cellular manufacturing system. Int J Manag Sci Eng Manag 2012; 7(2): 89–95.

22.

Bagheri

Bashiri

. A hybrid genetic and imperialist competitive algorithm approach to dynamic cellular manufacturing system. Proc IMechE, Part B: J Engineering Manufacture 2014; 228(3): 458–470.

23.

Paydar

Saidi-Mehrabad

. Revised multi-choice goal programming for integrated supply chain design and dynamic virtual cell formation with fuzzy parameters. Int J Comp Integ M 2015; 28(3): 251–265.

24.

Norman

Tharmmaphornphilas

Needy

et al . Worker assignment in cellular manufacturing considering technical and human skills. Int J Prod Res 2002; 40(6): 1479–1492.

25.

Slomp

Chowdary

Suresh

. Design of virtual manufacturing cells: a mathematical programming approach. Robot Cim: Int Manuf 2005; 21(3): 273–288.

26.

Mahdavi

Alaei

Paydar

et al . Designing a mathematical model for dynamic cellular manufacturing systems considering production planning and worker assignment. Comput Math Appl 2010; 60(4): 1014–1025.

27.

Mahdavi

Alaei

Paydar

et al . A new mathematical model for integrating all incidence matrices in multi-dimensional cellular manufacturing system. J Manuf Syst 2012; 31(2): 214–223.

28.

Soolaki

. A multi-objective integrated cellular manufacturing systems design with production planning, worker assignment and dynamic system reconfiguration. Int J Ind Syst Eng 2012; 12(3): 280–300.

29.

Bashiri

Bagheri

. A two stage heuristic solution approach for resource assignment during a cell formation problem. Int J Eng Trans C: Asp 2013; 26(9): 943–954.

30.

Süer

Kamat

Mese

et al . Minimizing total tardiness subject to manpower restriction in labor-intensive manufacturing cells. Math Comput Model 2013; 57(3–4): 741–753.

31.

Saidi-Mehrabada

Paydara

Aalaeib

. Production planning and worker training in dynamic manufacturing systems. J Manuf Syst 2013; 32(2): 308–314.

32.

Mahdavi

Bootaki

Paydar

. Manufacturing cell configuration considering worker interest concept applying a bi-objective programming approach. Int J Ind Eng Prod Res 2014; 25(1): 41–53.

33.

Bootaki

Mahdavi

Paydar

. A hybrid GA-AUGMECON method to solve a cubic cell formation problem considering different worker skills. Comput Ind Eng 2014; 75: 31–40.

34.

Sadeghi

Forghani

Seidi

. Integrated dynamic cell formation with operator assignment and inter-cell layout problems: a mathematical model. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(9): 1658–1669.

35.

Mak

. Production scheduling for virtual cellular manufacturing systems with workforce constraints using a hybrid algorithm. In: Proceedings of the 6th international conference on natural computation (ICNC), Yantai, China, 10–12 August 2010, vol. 8, pp.4445–4449. New York: IEEE.

36.

Soto

Kjellerstrand

Duran

et al . Solving manufacturing cell design problems using constraint programming. In: Jiang

Ding

Ali

et al . (eds) Advanced research in applied artificial intelligence, vol. 7345. Berlin: Springer, 2012, pp.400–406.

37.

Soto

Kjellerstrand

Duran

et al . Cell formation in group technology using constraint programming and Boolean satisfiability. Expert Syst Appl 2012; 39(13): 11423–11427.

38.

Subhaa

Jawahar

. ILOG CPLEX OPL modelling for machine cell formation. Int J Eng Tech 2013; 5: 3734–3741.

39.

Smith

. Is scheduling a solved problem? In: Kendall

(ed.) Multidisciplinary scheduling: theory and applications. New York: Springer, 2005, pp.3–17.

40.

Montanary

. Networks of constraints: fundamental properties and applications to picture processing. Inform Sciences 1974; 7: 95–132.

41.

Rousseau

Gendreau

. Using constraint-based operators to solve the vehicle routing problem with time windows. J Heuristics 2002; 8(1): 43–58.

42.

Demassey

Pesant

Rousseau

. Constraint programming based column generation for employee timetabling. In: Barták

Milano

(eds) Integration of AI and OR techniques in constraint programming for combinatorial optimization, vol. 3524 (Problems lecture notes in computer science). Berlin: Springer, 2005, pp.140–154.

43.

Mak

Cui

. Integrated multi-period production scheduling and cell formation for virtual cellular manufacturing systems. Eng Lett 2011; 2011; 19(4): 316–324.

44.

IBM ILOG OPL language user’s manual, version 6.3. Armonk, NY: IBM Corp., 2009.

45.

Oracle Java 8 Random Javadocs, 2016, https://docs.oracle.com/javase/8/docs/api/java/util/Random.html#nextInt-int

Workers/REs	RE 1	RE 2	RE 3	RE 4	RE 5	RE 6	RE 7	RE 8	Worker cost	Worker capacity
W1			*		*				100	500
W2						*		*	200	600
W3	*		*				*		200	500
W4		*		*				*	150	400
W5				*	*				150	400
W6	*	*				*			400	500

Machines/REs	RE 1	RE 2	RE 3	RE 4	RE 5	RE 6	RE 7	RE 8	Machine cost	Machine capacity
M1		*	*	*					200	600
M2	*					*			200	600
M3				*				*	300	700
M4			*	*			*		150	600
M5					*	*			200	500
M6	*				*			*	300	600
M7		*					*		150	400

Test problem	Number of parts	Number of machines	Number of workers	Number of REs	Number of cells
1	4	4	4	4	2
2	7	5	4	5	2
3	10	7	6	8	2
4	15	7	6	10	3
5	22	10	6	11	3
6	25	10	7	11	3
7	30	12	7	12	3
8	35	15	9	12	3
9	40	18	10	12	3
10	50	20	12	15	3
11	75	25	15	15	3
12	100	30	18	15	3

Workers/REs	RE 1	RE 2	RE 3	RE 4	RE 5	RE 6	RE 7	RE 8	Worker cost	Worker capacity
W1			*		*				100	500
W2						*		*	200	600
W3	*		*				*		200	500
W4		*		*				*	150	400
W5				*	*				150	400
W6	*	*				*			400	500

Machines/REs	RE 1	RE 2	RE 3	RE 4	RE 5	RE 6	RE 7	RE 8	Machine cost	Machine capacity
M1		*	*	*					200	600
M2	*					*			200	600
M3				*				*	300	700
M4			*	*			*		150	600
M5					*	*			200	500
M6	*				*			*	300	600
M7		*					*		150	400

Test problem	Number of parts	Number of machines	Number of workers	Number of REs	Number of cells
1	4	4	4	4	2
2	7	5	4	5	2
3	10	7	6	8	2
4	15	7	6	10	3
5	22	10	6	11	3
6	25	10	7	11	3
7	30	12	7	12	3
8	35	15	9	12	3
9	40	18	10	12	3
10	50	20	12	15	3
11	75	25	15	15	3
12	100	30	18	15	3

Manufacturing cell formation with flexible processing capabilities and worker assignment: Comparison of constraint programming and integer programming approaches

Abstract

Keywords

Introduction

Literature review

CP

Development of the models

The proposed IP model

Objective function

Constraints

The proposed CP model

Objective function

Constraints

Symmetry breaking constraints

Illustration of a case problem

Comparative analysis of IP and CP models

Search phases

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

Workers/REs	RE 1	RE 2	RE 3	RE 4	RE 5	RE 6	RE 7	RE 8	Worker cost	Worker capacity
W1			*		*				100	500
W2						*		*	200	600
W3	*		*				*		200	500
W4		*		*				*	150	400
W5				*	*				150	400
W6	*	*				*			400	500

Machines/REs	RE 1	RE 2	RE 3	RE 4	RE 5	RE 6	RE 7	RE 8	Machine cost	Machine capacity
M1		*	*	*					200	600
M2	*					*			200	600
M3				*				*	300	700
M4			*	*			*		150	600
M5					*	*			200	500
M6	*				*			*	300	600
M7		*					*		150	400

Test problem	Number of parts	Number of machines	Number of workers	Number of REs	Number of cells
1	4	4	4	4	2
2	7	5	4	5	2
3	10	7	6	8	2
4	15	7	6	10	3
5	22	10	6	11	3
6	25	10	7	11	3
7	30	12	7	12	3
8	35	15	9	12	3
9	40	18	10	12	3
10	50	20	12	15	3
11	75	25	15	15	3
12	100	30	18	15	3