Sage Journals: Discover world-class research

Abstract

Cell formation is the fundamental step while designing a cellular manufacturing system. Integration of job sequencing with cell formation can attain lower make-spans. The traditional cell formation and scheduling problems consider performance indicators such as productivity, time and flexibility in cellular manufacturing system; however, energy consumption has not been given due attention. Therefore, this research addressed the minimization of total energy consumption by implementing an energy-efficient schedule at the cell formation stage of cellular manufacturing system. For this purpose, a two-phase approach is proposed; in phase I, formation of independent cells is being carried out by considering energy-efficient routings and genetic algorithm is used for improving search performance. In phase II, a formulation is being developed to compute the total energy of the system based on optimal job sequence with respect to minimum idle running of the machines in each independent cell. For the proposed approach, a code is being developed in MATLAB software. Different sample problems have been evaluated. The results showed that the proposed approach is effective in generating independent cells and sequences with minimum energy consumption and make-span.

Keywords

Cellular manufacturing system cell formation independent cell formation energy consumption scheduling make-span

Introduction

In today’s world, cellular manufacturing (CM) is used for the improvement of the systems to achieve fusion of flexibility and production efficiency.¹ Cell formation (CF) is the fundamental step in designing a cellular manufacturing system (CMS). It involves grouping of similar parts and corresponding machines into cells.²

Ideal situation in CF is achieving a cell which is independent.³ An independent cell allows assigned parts to complete their processing of machines available in a single cell and does not need other cells for their completion. The application of independent cells is found in industries where equipments and machines can be easily reconstructed and replaced by those having similar functions.

Such cells are suitable for producing small-in-size, light-in-weight, easy-to-assemble and medium-in-volume products.⁴ Such cells are best applicable to manufacturing systems including pharmaceutical, medical apparatus, food, electronic goods and precision tools.^5,6 Although there is an increase in capital investment by duplication of equipments and machinery, independent cells can lead to simpler and easier production scheduling. Also, this investment can be compensated by applying energy-saving strategies in independent cells. These energy-saving strategies not only compensate the investment but also aid in developing the energy-efficient manufacturing systems in this era of growing energy security concerns.

Energy consumption of industrial sector has increased more than double in the last 50 years and it is consuming half of the world’s energy.⁷ Such situation compels industries to incorporate energy-efficient and energy-saving strategies. Research on the energy consumption minimization has focused on three perspectives: the machine-level perspective, the product-level perspective and the manufacturing system–level perspective.⁸ The machine-level perspective involves designing of machines in such a way that machines consume minimum energy. The product-level perspective involves modeling a framework which designs products such that products consume minimum energy. The manufacturing-level perspective involves decisions such as scheduling; by applying these decisions, minimized energy consumption can be achieved. Minimizing idle times between processing of parts can assist in reducing energy consumption of the machines.

The next section provides the literature review. Section “Problem description” consists of the considered problem along with the assumptions. Section “Proposed approach” explains the approach suggested for solving the described problem. Section “Numerical problem” covers an illustrative example to demonstrate the proposed approach. Section “Results and discussion” presents the obtained results. Section “Conclusion” concludes the work with a summary and future scope of work.

Literature review

CMS has been known as the most recent technological improvements in job shop as well as batch production to achieve economic benefits as those achieved in mass production.⁹ CMS has three major designing steps: (1) CF, (2) machine layout and (3) cell layout. CF is the most important, primary and crucial issue.

Over the last few decades, extensive research studies have been carried out on CF. An efficient method for solving multi-objective CF problem is proposed by partially implementing Falkenauer’s grouping genetic algorithm (GGA). The main objectives in that study were minimization of cell load variation and intercellular flows.¹⁰ Machine part grouping problem is addressed with the considerations of machine flexibility as well as machine aggregation and disaggregation simultaneously. The main objectives in this study were minimization of total intercellular and intracellular movements.¹¹ A clustering approach is presented for generating machine cells and part families automatically. An optimal machine sequence, maximizing the overall flow of elements between the machines, is found out.¹² A Pareto-optimality-based multi-objective Tabu search (MOTS) algorithm is offered for the problem of machine-part grouping to incorporate objectives such as minimization of total cost, which consists of intracellular and intercellular transportation cost and machine investment cost, minimization of intracell loading unbalance and minimization of the intercell loading unbalance.¹³ A new methodology for CF consuming a syntactic recognition approach is proposed. Operational information of the part is utilized to select a suitable cell for a new part.¹⁴ The Tabu search meta-heuristic is presented for solving the problems in less computational time and dealing with the part family formation and cell grouping problems separately. The minimization of intercellular movements as an objective function is demonstrated.¹⁵ A method incorporating machine modification for solving CF problem is presented. It included the minimization of the sum of machine modification cost and intercell travel.¹⁶ Another study included a mathematical model to simultaneously solve CF, cell layout and sequence of operations to achieve the objective of minimizing transportation cost and make-span. Multi-objective genetic algorithm (MOGA) was presented to solve the problem.¹⁷ An approach for solving CF problem is presented with the consideration of many factors such as machine requirement, operation sequence, alternative processing routes, processing time, production volume, budget limitation and cost of machines. A GA-based model was presented to minimize the sum of dissimilarity and to maximize the total saving in the assignment of bottleneck machines.¹⁸ All these studies formed cells with intercellular movements, which accounted for intercellular travel cost and, in turn, affected make-span.

Various methods exist for solving CF problems. Those methods can be categorized into (1) heuristics, (2) meta-heuristics, (3) hybrid meta-heuristics, (4) mathematical programming and (5) artificial intelligence procedures.^19–21 GA is categorized as a useful technique because of its ability to cope with the Non- deterministic Polynomial-time (NP) hard aspect and the feature of combinatorial optimization of CF problem.²² GA imitates the natural development process in such a way that the survived fittest between solution configurations is merged with a structured, however randomized, information swap to produce offspring. GA has been widely used in a variety of fields such as engineering, manufacturing, telecommunications and business.²³ GA can assist in finding multiple solutions by applying genetic operators such as cross over and mutation. Consequently, there is a possibility to reach the optimization point promptly. It has been found in the literature that GAs and its modified versions have been successfully used for solving the CF problems in the CMS. A GGA proposed by Brown and Sumichrast²⁴ incorporated characteristics of CF problem into a typical GA. Furthermore, for solving the CF problem, a hybrid GGA is proposed which joins a local search with a standard GGA to form machine-part cells.²⁵

In order to improve the efficiency of formed cells in terms of material handling cost, mutual independence between formed cells was being preferred. One such study included independent CF by taking into account multiple identical machines. This study presented a bi-objective mathematical model for minimizing work load imbalance in formed cells.²⁶ A heuristic algorithm consisting of two phases was proposed for designing a new CMS; CF and machine selection problems were addressed. The first phase incorporates formation of independent cells using cell aggregation procedure. In the second phase, under-utilized machines are eliminated by introducing intercell flows.²⁷ Furthermore, a method is proposed for the design of independent manufacturing cells in CM by considering alternative process routings and machine replication. The problem was solved using GA which determined machine cells, part families and process plan for each part simultaneously.²⁸ Several studies investigated production planning and scheduling problems in independent cells^29–32 while the research on forming independent manufacturing cells is rather rare. One way of forming independent cells is through duplication of the machines.

Apparently, the duplication of the machines results in increased machine investment cost and total CF cost for practical purposes. But ultimately, it can lead to significant decrease in the total production cost because of the accumulated intercellular material handling and setup cost. In response to the increased investment cost in the independent cells due to machine duplication, application of an energy-saving strategy will provide a remarkable means to construct an efficient manufacturing system. This will not only compensate machine investment but also give an energy-efficient solution in this era of globally increasing energy demand.

The survey on the electric energy consumption has exposed that up to 54% of electric energy was used in production processes, which was mostly on production machines.³³ This increased energy resulted in significant increase in the annual cost of industry. One of the low investment method to minimize energy consumption is energy-efficient scheduling. For a flexible flow shop, an energy-efficient model is proposed. For implementation of practicable schedule, an improved genetic-simulated annealing algorithm was proposed which provided a remarkable trade-off between make-span and energy consumption.⁸ An energy aware mathematical model integrating process planning and scheduling is proposed for job shops.³⁴ A mathematical model is presented for energy aware scheduling of flexible flow shop. Reference schedule was produced by an advanced planning and scheduling (APS) system which did not take energy saving into account, and that reference schedule was modified to consider energy saving without changing assignment of jobs and sequencing as used in reference schedule.³⁵

Another research included several dispatching rules to save energy by switching off non bottleneck machines when they remained idle for significant amount of time. Also, a multi-objective mathematical model was proposed to minimize energy consumption and completion time.³⁶ Moreover, a methodology is addressed for the assessment of energy consumption and material flows by considering multiple process plans for a part type. That research also considered objective of minimizing weighted sum of energy consumption, inventory holding cost and backorder cost on a flexible manufacturing system (FMS) considering multiple process plans.³⁷

In spite of knowing the growing needs toward energy reduction, so far up to our knowledge, there is no study in the literature focusing on CF with the objective of energy-efficient scheduling along with minimization of make-span, while there is a need to consider this low investment method for the minimization of energy consumption in the CF as well. To highlight this fact, the research articles on CF with time- and/or energy-related objectives have been shown in Table 1, which shows that so far no one has considered independent CF along with energy-efficient scheduling and minimum make-span. Thus, this study presents an efficient approach consisting of two phases for CF to minimize total energy consumption by minimizing idle running of machines. For this purpose, many real-time production features such as processing times, alternative processing routes, production quantity, machine’s make to part power and idle power are being considered.

Table 1.

Summary of literature on CF considering time and/or energy-related objective functions.

Article author	Scope of research			Objective functions
Article author	Cell formation	Independent cell formation	Scheduling	Energy related	Time related
Beaulieu et al.²⁷	✓	✓			✓
Moon and Gen²⁸	✓	✓			✓
Songore and Sangore¹⁵	✓				✓
Chan et al.¹¹	✓				✓
Yasuda et al.¹⁰	✓				✓
Lei and Wu¹³	✓				✓
Foulds et al.¹⁶	✓				✓
Wu et al.²	✓		✓		✓
Arkat et al.¹⁷	✓				✓
Karthikeyan⁴⁵	✓		✓		✓
Lian et al.²⁶	✓	✓			✓
Proposed research	✓	✓	✓	✓	✓

Problem description

In this section, the considered problem along with the assumptions is being presented. The solution with a new approach has been presented in the next section.

Processing data and production quantity are considered as the input parameters. CF is the grouping of part families and the corresponding machines into cells in order to achieve the desired objectives. For improving the efficiency of systems in this era of globally increasing energy demand and prices, minimization of the energy consumption of machines is regarded as an important performance measure. Therefore, in this study, two concepts (energy consumption of machines and make-span of parts) are considered simultaneously for forming the cells and finding the optimal sequence of assigned part families on the machines. Make-span is the total completion time of all products in the system. The main focus is the minimization of idle energy consumption by reducing the idle time between processing of parts.

The addressed problem incorporates the following features:

Parts are divided into several types and production quantity of each part type is known.

For each part type, only one processing route must be selected.

Same cell can comprise multiple identical machines.

For the same operation of a part type on different machines, the processing time may vary in different processing routes because of different rated horse powers of the machines.

Assumptions

In this study, the following assumptions are made in order to carry out the above problem:

For each operation, the processing time on different machine types is known and is deterministic.

Identical machines which belong to a particular machine type have similar operation and processing times.

Raw material of all part types is available at time = 0.

Production quantity of all part types is equal and known.

Preemption is restricted for processing each part type. It means, after starting of an operation, no interruption is allowed until it is finished.

Proposed approach

This article focuses on the integration of CF and job sequencing to minimize the energy consumption with the minimum make-span. For this purpose, a new approach consisting of two phases is proposed to meet the desired objective. Phase I includes two steps; first step consists of the selection of routing with the minimum processing energy consumption of machines. Second step is the independent CF by taking into account multiple identical machines using GA. Phase II includes job sequencing with respect to minimum idle energy and calculation of the total energy consumption of the system. Figure 1 demonstrates both phases of the proposed approach.

Figure 1.

Flow diagram of proposed methodology.

Phase I: formation of independent manufacturing cells with routing selection based on the processing energy

Designing of CMS comprises three steps, CF, machine layout and cell layout. Among these, CF is the foremost and the fundamental step. The most critical issue in CF is achieving the independent manufacturing cells, because achieving independent cells is the ideal situation in a CMS. As described earlier, in an independent cell, part families do not require other cells to complete their processing. This eliminates the intercellular part movements and significantly increases the efficiency of the overall system. The first step in independent CF is routing selection.

Routing selection based on processing energy

In real manufacturing systems, there can be various routes for completely processing a part. Part may visit different machines with the different rated horse powers. Since each machine has different make to part power, therefore parts can have different times on different machines for the same operation. It means parts can have alternative processing routings for their manufacturing with varying make-span and energy consumption. The selection of a route from the available routes can be made random or based on some criteria.

In this research in order to evolve an energy-efficient approach, before making part families and assigning them to different cells, the processing routes are evaluated on the basis of processing energy consumption of the machines. This energy consumption is computed using processing times and make to part power of machines in a given route and this energy cannot be reduced in a specific route. It means in each route, the processing energy is fixed, and hence, extracting the route with the minimum processing energy consumption is an additional feature of the approach. If

n is the total number of part types, indexed by i;

m is the total number of machine types, indexed by j;

r is the total number of routings, indexed by l;

$x_{ij}$ is the processing time of part type i on machine j;

$P_{ij}$ is the make to part power of machine j while processing part type i;

$E_{il}$ is the energy consumed if part i follows route l.

Then processing energy consumption $E_{(il)}$ of the machines in manufacturing of all part types for all possible routes can be calculated using equation (1). Then processing routes with minimum processing energy consumption are sorted for each part type using equation (2) where $E_{(i)}$ is the minimum value of energy consumed by machine j for part i among all possible routes

E_{(il)} = \sum_{i = 1}^{n} \sum_{j = 1}^{m} x_{ij} \times P_{ij} \forall l = 1, \dots, r

(1)

E_{(i)} = MIN [E_{(il)}] \forall i = 1, \dots, n

(2)

After selecting route with minimum processing energy, the next step is independent CF. Independent CF and improvement of solution are done using GA.

Formation of independent manufacturing cells

Independent CF can be carried out by considering multiple identical machines. The presence of multiple identical machines abolishes the intercellular movements and makes sure that each formed cell is independent. Such independent cell can process parts from beginning to end without the assistance of other cells. Schematic representation of the proposed method is shown in Figure 2. Machine pool consists of different machine types, each with different machine quantities, as shown in Figure 2(d). This will serve as an input to CF. Based on the product type with selected routing as shown in Figure 2(c), the machines are moved from the pool of machines (where that particular machine type is in large quantity) to that cell where the product type requires them so that for processing on those machines the product type need not be moved to other cells. As shown in Figure 2(e), if product types 2, 4 and 5 are assigned to cell 1, then after reassigning machines based on processing routes of these product types, cell 1 will comprise M1, M1, M2, M3, M3 and M3. Created cell 1 is independent because it contains all those machines which are required for processing of product types 2, 4 and 5. Similarly, for processing of product types 1, 3 and 6, cell 2 is independent. The initial feasible solution is generated by GA. This is called as the initial feasible solution. In this research, GA is used to achieve a feasible solution.

Figure 2.

Schematic representation for independent cell formation by considering multiple identical machines: (a) description of each part type and quantity, (b) alternative process routing for each part type, (c) selected process routing for each part type, (d) machine type pool each with given machine quantity and (e) possible cells fulfilling independency criteria and assigned part types.

CF using GA

GA, introduced by Holland,³⁸ is an efficient meta-heuristic for finding the solution of combinatorial optimization problems.³⁹ Falkenauer⁴⁰ proposed GGA which is appropriate for solving the grouping problems than conventional GA regarding the encoding plan and genetic operators.

Encoding

GA deals with a variety of solutions rather than a particular solution. A chromosome represents an encoding plan of a feasible solution of the problem in sight. Particularly, for the CF problems, the chromosome corresponds to a possible division of the set of machines in a number of groups termed as cells. Encoding of such a grouping problem is identified as the group encoding plan. Group encoding plan aids in keeping the reliability of group structure and assisting the cross over operator.⁴¹

In this research, the chromosome is represented by two sections separated by the vertical lines. The first section represents the machines and its length is equal to the number of machine types. The second section represents the product types. In both sections, each gene takes its value from the natural number which belongs to {1,2,…, C} where C is the total number of cells.

For better understanding of encoding, consider an example of seven machines and six product types that need grouping into three cells. The encoded chromosome = [1 2 2 3 1 2 2 | 1 3 1 3 2 2] represents that the machines [1 5] and product types [1 3] are in cell 1; machines [2 3 6 7] and product type [5 6] are in cell 2 and machine [4] and product types [2 4] are in cell 3. This encoding design is represented in Figure 3 and is used for initialization of the initial population.

Figure 3.

Chromosome configuration.

Figure 4 shows the group chromosome configuration for the example mentioned above. Group chromosome configuration of this type is a way similar to encoding scheme configuration proposed by Goncalves Filho and José Tiberti.⁴² In this configuration, the ordering of cells organizes the genes for both sections. The machine types and product types that are assigned to each of the cell are illustrated clearly.

Figure 4.

Encoded and decoded chromosomes.

Creation of initial population

A number of chromosomes together are known as a “population.” At a particular time, a population is known as a “generation.” The initial population is created only one time having the known size of the population. This initial population can be created randomly or using some heuristic at the start of GA. After that, some chromosomes are picked out as parents which contribute toward generation of offspring using genetic operators, that is, mutation or cross over. A special procedure is adopted to create an initial population randomly in order to restrain the presence of empty cells. For achieving a defined population size, the following procedure is adopted for creation of each chromosome of the initial population:

1. For each cell, $C = [1, 2, 3, \dots, c]$ , perform random selection of a machine type from m, where m is the total number of machine types, and a product type from n, where n is the total number of product types, and assign them to each cell.

2. From the rest unassigned machines $[m - C]$ , a machine type and a cell are selected at random. Later on, the selected machine is allocated to the selected cell. Similarly, the remaining product types $[n - C]$ are assigned in the same way.

3. Iterate Step 2 until all the machine types and all the product types are assigned to the cells.

4. Both portions of the chromosomes will be formed by the results of Steps (1)–(3). In the next step, these chromosomes are written in the configuration as described in Figure 3 and putting it in the initial population.

Feasibility improvement

The chromosomes that are created at random or using genetic operators typically violate problem constraints of cell independence. Referring to the feasibility improvement method proposed by Lian et al.,²⁶ considering the desired objective, the following modified method is employed for transforming randomly created chromosomes into feasible ones. This method identifies any chromosome not satisfying independency of cells’ criteria. The following method is employed to make independent cells by correcting the chromosomes:

5. Alter the existing chromosomes’ structure into new one by decoding as shown in Figure 3.

6. Pick up a chromosome b randomly.

7. Pick up a product type i from the selected chromosome b and examine cell c in which the product type i exists. Processing route $E_{i}$ selected for the product type i is compared with the machines included in cell c. If the machine in cell c does not fulfill the production requirements of product type i, continue to Step 4; otherwise, jump to Step 5.

8. Identify the machines’ type intended to be included in cell c. For each of the needed machine type, other cells are tested and categorized a cell, designated by c′, that contains the highest number of identical machines of similar type; then choose a machine of same kind from cell c′ and relocate it to cell c.

9. Steps 3 and 4 are iterated until all product types in chromosome b make sure that each formed cell is independent.

10. In case all given chromosomes get corrected, then stop. Otherwise, jump to Step 2.

After forming feasible chromosomes with independent cells, the next step is to improve the chromosomes’ generation by cross over.

Cross over

Each generation has relatively smaller size than the complete search space, but some unvisited areas can be visited by applying genetic operators such as mutation and cross over to get improved results. Therefore, GA considered here mainly contributes to take advantage of genetic operators to improve results. In case of grouping problems, mutation operator does not have the ability to enhance the GA performance widely.⁴³ Hence, cross over operator is regarded here. The cross over operator works by joining the characteristics of two parent chromosomes for making offsprings.

For solving grouping problem, there exists many types of cross over, for example, single-point cross over, two-point cross over, cell swap cross over and cell-two-point cross over. In this article, cell-two-point cross over is preferred because it is a problem-specific genetic operator and it improves the performance of GA regarding computational efficiency and quality of solution.⁴⁴ For each portion of parent chromosome generation, a cross over point is selected randomly between 1 and (c-1) for beginning of cross over. Subsequently, in each portion, by substituting groups into the right of the cross over point, two new chromosomes are created.

For better understanding of cross over operator, example of seven machines and six product types needed to be grouped into three cells is shown. Consider two parent generations:

P1 = [3 2 2 1 3 2 2 | 1 2 3 1 2 2] = [4/2 3 6 7/1 5 | 1 4/2 5 6/3]

P2 = [1 1 3 2 1 3 2 | 1 3 1 3 2 3] = [1 2 5/4 7/3 6 |1 3/5/2 4 6]

Suppose the cross over point is 2 for both portions of the chromosome. As a result, two offspring are created as shown in Figure 5.

Figure 5.

Illustration of cross over operator.

These newly created chromosomes in Figure 5 may not hold some essential genes and may hold some unnecessary genes. For instance, in chromosome “A,” machines [1 5] and product type 3 are not present. It means offspring are not feasible because some machines and product types are absent and some exist more than once. Hence, a heuristics is developed for the generation of feasible child chromosomes.

First of all, remove the repeating machines and product types from the left portion of cross over point for each off spring chromosome. But after the removal procedure, a new problem occurs. There may be some cells with no machines and product types in it. Identify the absent machines and product types and search for a vacant cell at the left of cross over point. If an empty cell is found, then allocate the absent machines and product types to the empty cell. Search again and if still an empty cell is found, then randomly choose a machine or a product type from non-empty cells which are not yet swapped and reallocate it to empty cells. Iterate it until no empty cell is found.

After applying this procedure, empty cells will be eliminated and no repeating machines and product types exist and the offspring become feasible. This feasibility correction procedure of offspring is described in Figure 6.

Figure 6.

Feasibility correction of offspring.

Phase 2: job sequencing and the minimization of total energy of the system

Before presenting formulation for obtaining optimal job sequence and total energy of the system, some notations are described.

Problem formulation for phase II

In phase I after routing selection based on the processing energy, the independent cells are formed. Each independent cell consists of machines and part families. In phase II, part families are scheduled in all possible sequences on the machines available in each cell to find the energy-efficient schedule.

For finding an energy-efficient schedule, it is desired to reduce the idle run time of the machines in each individual cell. In return, this idle time reduction saves energy of the machines caused by idle running.

Part families can be scheduled in S_c! sequences. For example, if the part families P1 and P2 are assigned to cell 1, then these part families can be scheduled in 2! = 2 possible ways such that:

[P1, P2], [P1, P2] … [QP1, QP2]

[P2, P1], [P2, P1] … [QP2, QP1]

In S_c! sequences, part families are scheduled on the assigned and available machines in each cell. One sequence from each cell is selected which gives schedule with the minimum idle energy consumption. Then the total idle energy is calculated by adding the idle energies in individual cells. All chromosomes in the population are entered one by one in the developed MATLAB code and the above-mentioned procedures are repeated. After evaluating the given population, a chromosome is selected which gives the minimum energy consumption with the minimum make-span.

Make-span is the longest finishing time of parts among all finishing times in a selected sequence in all possible cells. These sequences are selected based on the minimum idle energy consumption of the machines. Since cells are independent, the machines can simultaneously process parts in all possible cells.

Two objective functions are given below in equations (3) and (4); the first is the minimization of total energy consumption $(E_{Total})$ and the second is the minimization of make-span T

Min f_{1} : E_{Total} = E_{Processing} + E_{idle}

(3)

Min f_{2} : T = \max [T_{C}]

(4)

$E_{Processing}$ is the energy consumed by the machines during the part processing. $E_{idle}$ is the energy consumption of the machines during the idle running.

Equation (5) shows the processing energy consumption of the machines for given part type quantity

E_{Processing} = \sum_{i = 1}^{n} [E_{i} \times Q_{i}]

(5)

Let $L_{c}$ represent a series with the part types belonging to cell c and “a” the difference between two consecutive part types (where different part types are named with integers 1, 2, 3,…, n) in that series. In these consecutive terms, predecessor will be subtracted from successor. For $S_{c}!$ sequences, if i is the leading part type of any pair in a particular sequence $L_{c}$ , then $I T_{i (i + a} j}$ shows the idle time between part type i and the next part type $i + a$ coming after part type i on machine type j in a given sequence.

Equation (6) is the idle energy of the system, that is, in all possible cells. This idle energy is calculated by multiplying the idle time between parts’ processing with idle power of the relevant machines. The term $U_{cij}$ is incorporated to allow this formula to work for the possible cells separately as each cell is independent. This equation shows the idle time of machine j between processing of the consecutive part types for single quantity. Since the idle time incorporated here is the idle time between parts’ processing which is entirely different from the total idle time. Unlike the total idle time, the idle time between parts’ processing for whole production quantity cannot be computed by simply multiplying the idle time between one pair of parts with total parts’ quantity. As the idle time between parts’ processing may vary in the upcoming consecutive part pairs. Therefore, the MATLAB code is generated for computing the idle time for given quantity of all part types belonging to the respective cell. A pseudo code for the complete computation process is attached in Appendix 2

E_{idle} = \sum_{c = 1}^{C} [\sum_{j = 1}^{m} (\sum_{i = 1}^{n} I T_{i (i + a) j} \times I P_{j} \times U_{cij})]

(6)

where

I T_{i (i + a) j} = S_{(i + a) j} - Z_{ij}

(7)

S_{(i + a) j =} Max [(Z_{(i + a) (j - 1)}), (Z_{ij})]

(8)

Z_{ij} = S_{ij} + x_{ij}

(9)

subject to

I T_{i (i + a) j} \geq 0

(10)

Equation (7) represents the idle time between processing of two consecutive part types in a particular sequence $L_{c}$ . Equation (8) shows the starting time of the next part type on machine j. Equation (9) shows the completion time of part type i. Finally, equation (10) reveals that the idle time cannot be negative. This formulation helps in finding the total energy consumption of the machines and the make-span.

The proposed approach incorporates many real-time production features such as processing times, alternative processing routes, production quantity, machine’s make to part power and idle power. All these parameters have not been considered simultaneously in past researches of CF. Also, the chosen approach makes use of lower capital investment method of minimizing energy consumption that is energy aware scheduling. Other methods of minimizing energy consumption include re-designing of equipment and/or re-designing of products which requires higher capital investment. Effectiveness of the proposed approach is being demonstrated with the help of numerical problems presented in the next section.

Numerical problem

Three problems, with problem size (product types × machine types) = 6 × 7, 12 × 12 and 20 × 15, are solved using MATLAB coding. For problem of 6 × 7 size, data are shown below. Table 2 represents six product types, each with different processing routings on seven machine types (each machine with a given machine quantity). Processing time in minutes and machine type is given for each product type. The numbers existing external to the parenthesis represents processing times. The roman letters within parenthesis show the associated machine types. The symbol “/” shows the absence of the associated operation. There exist 28 machines related to seven machine types. The categorization of machines and the associated horse power are given in Table 3. The type and quantity of each part type are given in Table 4. The number of formed cells is assumed and depends on the size of the problem. Considering the randomness of GA, 10 solutions, created by cross over operator, are evaluated to achieve efficient result. The initial population consists of four chromosomes and the rest are generated by applying the cross over operator and the feasibility correction procedure as described in section “CF using GA.”

Table 2.

Processing times and associated machine type of each operation.

Product type	Processing route	Operation 1 (min)	Operation 2 (min)	Operation 3 (min)	Operation 4 (min)	Operation 5 (min)
1	1	15 (VII)	10 (I)	20 (VI)	10 (IV)	/
1	2	13 (II)	12 (V)	15 (VII)	/	10 (I)
2	1	10 (III)	20 (VII)	10 (II)	15 (IV)	/
3	1	10 (I)	12 (IV)	11 (V)	/	/
	2	17 (VII)	18 (III)	/	/	/
	3	10 (II)	13 (V)	10 (I)	0	10 (VII)
4	1	19 (V)	14 (VII)	10 (I)	/	/
4	2	10 (VI)	14 (II)	/	/	/
5	1	13 (II)	18 (I)	/	15 (VI)	/
5	2	11 (VII)	10 (V)	12 (II)	/	10 (I)
6	1	10 (VI)	15 (VII)	10 (II)	/	/
6	2	12 (I)	/	13 (IV)	15 (VI)	11 (II)

Table 3.

Categorization and horse power of machine.

Machine type	I	II	III	IV	V	VI	VII
Machine	M1–M4	M5–M7	M8–M11	M12–M16	M17–M18	M19–M22	M23–M28
Make to part power per minute (hp/min)	12	7	4	6	12	6	8
Idle power (hp/min)	0.4	0.3	0.2	0.3	0.4	0.3	0.3

Table 4.

Type and quantity of each product type.

Product type	1	2	3	4	5	6
Production quantity	650	650	650	650	650	650

Results and discussion

To solve the problems using the proposed approach, the code was developed in MATLAB 7.12 and run on a PC with 1.80-GHz processor operating system MS Windows 7. In any case, if the number of cells is known, the developed MATLAB code can be used to obtain the objective function values.

For the above-mentioned numerical problem size of 6 × 7, the objective function values are provided in Table 5 for 10 solutions where each solution corresponds to a chromosome. Among these 10 solutions, one solution with the minimum energy consumption and the make-span value is selected. Tables 6 and 7 show the objective function values of 10 solutions with problem size of 12 × 12 and 20 × 15, respectively. Visual interpretations of Tables 5 –7 for the objective function values of total energy consumption and make-span are shown in Figures 7 –9 for problem size of 6 × 7, 12 × 12 and 20 × 15, respectively.

Table 5.

Objective function values of different solutions for problem size of 6 × 7.

Objective	Solution 1	Solution 2	Solution 3	Solution 4	Solution 5	Solution 6	Solution 7	Solution 8	Solution 9	Solution 10
$E_{Total}$ (hp min)	1,232,768	1,202,979	1,180,377	1,173,298	1,169,474	1,221,938	1,173,242	1,169,208	1,180,377	1,226,294
T (min)	52,650	52,650	22,789	22,791	22,789	52,650	22,770	22,791	22,789	45,525

Note: Bold values represent least values of objectives functions among all solutions.

Table 6.

Objective function values of different solutions for problem size of 12 × 12.

Objective	Solution 1	Solution 2	Solution 3	Solution 4	Solution 5	Solution 6	Solution 7	Solution 8	Solution 9	Solution 10
$E_{Total}$ (hp min)	1,499,552	2,235,257	1,471,634	2,267,470	1,490,510	1,446,614	2,267,470	1,471,058	1,474,724	2,047,179
T (min)	23,200	23,200	22,025	19,644	23,200	24,641	19,644	22,025	22,025	23,610

Note: Bold values represent least values of objectives functions among all solutions.

Table 7.

Objective function values of different solutions for problem size of 20 × 15.

Objective	Solution 1	Solution 2	Solution 3	Solution 4	Solution 5	Solution 6	Solution 7	Solution 8	Solution 9	Solution 10
$E_{Total}$ (hp min)	1,304,283	1,291,524	1,305,328	1,325,846	1,312,473	1,290,282	1,317,345	1,321,629	1,309,429	1,292,979
T (min)	21,051	17,150	15,920	15,970	17,160	21,051	22,731	23,010	24,672	21,051

Figure 7.

Comparison of $E_{Total}$ and make-span values for all 10 solutions for problem size of 6 × 7.

Figure 8.

Comparison of $E_{Total}$ and make-span values for all 10 solutions for problem size of 12 × 12.

Figure 9.

Comparison of $E_{Total}$ and make-span values for all 10 solutions for problem size of 20 × 15.

From Table 5, it is clear that solution 8 gives least value for total energy consumption, that is, 1,169,208 hp min and solution 7 gives least value for make-span, that is, 22,791 min. Detailed information of this selected solution can be found in Table 8. It shows if machines 1, 5, 7, 2 and 6 with product type 6 are in cell 1; machines 2, 3, 6, 1, 4 and 7 with product types 1, 3 and 5 are in cell 2 and machines 4, 2, 3, 7 and 6 with product types 2 and 4 are in cell 3 and product types in cell 2 are scheduled on the available machines in the sequence 5, 1, 3 and product types in cell 3 are scheduled on the available machines in the sequence 2, 4, then the objective of the minimum energy consumption can be achieved but for minimized make-span, solution 7 is preferred.

Table 8.

Detailed information of different solutions for problem size of 6 × 7.

Solution no.	Chromosome	Cells	Machine types in independent cells	Product types in independent cells	Selected sequence of assigned product types	Idle energy of the system in selected sequences (hp min)	Processing energy in selected processing routing (hp min)	Total energy in all cells (hp min)	Make-span (min)
1	1 2 2 3 1 2 2 \| 1 3 1 3 2 2	1	1 5 4 6 7 3	1 3	1 3	67,318	1,165,450	1,232,768	52,650
		2	2 3 6 7 1	5 6	6 5
		3	4 2 3 7 6	2 4	2 4
2	3 2 2 1 3 2 2 \| 1 2 3 1 2 2	1	4 1 6 7 2	1 4	1 4	37,529	1,165,450	1,202,979	52,650
		2	2 3 6 7 4 1	2 5 6	6 5 2
		3	1 5 3 7	3	3
3	1 1 3 2 1 3 2 \| 1 3 1 3 2 3	1	1 2 5 4 6 7 3	1 3	1 6	14,927	1,165,450	1,180,377	22,789
		2	4 7 1 2 6	5	3 5
		3	3 6 2 4 7	2 4 6	6 4 2
4	1 2 2 1 3 2 1 \| 2 3 2 1 2 3	1	1 4 7 2 6	4	4	7848	1,165,450	1,173,298	22,791
		2	2 3 6 1 4 7	1 3 5	5 1 3
		3	5 2 3 4 7 6	2 6	2 6
5	2 2 3 1 2 3 2 \| 1 3 2 3 2 3	1	4 1 6 7	1	1	4024	1,165,450	1,169,474	22,789
		2	1 2 5 7 3 6	3 5	5 3
		3	3 6 2 4 7	2 4 6	6 4 2
6	3 1 1 2 3 1 2 \| 1 1 3 1 2 2	1	2 3 6 1 4 7	1 2 4	4 1 2	56,488	1,165,450	1,221,938	52,650
		2	4 7 1 2 6	5 6	6 5
		3	1 5 3 7	3	3
7	1 2 2 1 3 2 2 \| 1 3 1 1 2 3	1	1 4 6 7 3 2	1 3 4	3 1 4	7792	1,165,450	1,173,242	22,770
		2	2 3 6 7 1	5	5
		3	5 2 3 4 7 6	2 6	2 6
8	1 2 2 3 1 2 1 \| 2 3 2 3 2 1	1	1 5 7 2 6	6	6	3758	1,165,450	1,169,208	22,791
		2	2 3 6 1 4 7	1 3 5	5 1 3
		3	4 2 3 7 6	2 4	2 4
9	1 1 3 2 2 3 2 \|1 3 1 3 2 3	1	1 2 4 6 7 3	1 3	1 3	14,927	1,165,450	1,180,377	22,789
		2	4 5 7 1 2 6	5	5
		3	3 6 2 4 7	2 4 6	6 4 2
10	2 2 1 3 2 2 3 \|1 1 3 2 2 1	1	3 1 4 6 7 2	1 2 6	6 1 2	60,844	1,165,450	1,226,294	45,525
		2	1 2 5 6	4 5	5 4
		3	4 7 3	3	3

The results of the problem size of 12 × 12 and 20 × 15 are presented in Tables 5 and 6, respectively. It shows that, same like the results of problem size of 6 × 7, these two cases also do not give minimum value of the total energy consumption and the minimum value of make-span for the same solution simultaneously. Since the make-span is the longest time among the selected sequences in all possible cells. Therefore, the reason for not obtaining the minimum energy consumption and the minimum make-span in same solution is because of the variation in completion times in selected sequences of all possible cells.

As shown in Figure 8, for problem size of 12 × 12, solutions 6, 8 and 9 give lower values for the total energy consumption and solutions 4 and 7 give the least value for the make-span. Likewise in Figure 9, for problem size of 20 × 15, solution 6 gives least for the total energy consumption and solution 3 gives the least value for the make-span.

From experimentation, it can be concluded that the least energy and the least make-span values cannot be obtained in the same solution. However, by making a trade-off between these two objective functions, there can be a solution with lower energy consumption and shorter make-span.

The proposed method will provide assistance in making decision, but it is up to the manager to decide. For example, in case of 6 × 7 problem, solution 5 can be selected as it gives second values for both objective functions: total energy consumption and make-span. In the case of 12 × 12 problem, solution 8 can be opted because it gives second values for make-span as well as energy consumption. Similarly, in 20 × 15 problem, solution 2 can be opted as it provides second lowest value for energy consumption and third lowest value for make-span.

Conclusion

The production features included in this research are processing times, alternative processing routes, production quantity, machine’s make to part power and idle power. For achieving the objective, an approach consisting of two phases was developed. Phase I incorporated formation of the independent cells with routing selection based on the minimum processing energy of machines. GA was utilized to find assistance in visiting unvisited search areas to obtain better results. Phase II incorporated the job sequencing and the calculation of the total energy of the system. A MATLAB code was developed for the evaluation of the objective function values: the total energy consumption and the make-span for alternate solutions. Different numerical problems were solved using the proposed approach. The results obtained from these numerical problems illustrated that the proposed approach is effective in generating independent cells and energy-efficient sequences. Also, it evaluates minimum energy consumption and minimum make-span for various alternate solutions.

Further empirical investigation is required to see the possibility of obtaining minimum energy consumption along with minimum make-span in a single solution for generated cells and sequences. In future, the research could also be extended by including more performance indicators, for instance, queue size, work in process and waiting time. It would be more realistic to develop model for stochastic demand.

Footnotes

Appendix 1

Appendix 2 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

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.

Chu

C-H

Wang

et al . Genetic algorithms for integrating cell formation with machine layout and scheduling. Comput Ind Eng 2007; 53(2): 277–289.

Selim

Aal

RMA

Mahdi

AI.

Formation of machine groups and part families: a modified SLC method and comparative study. Integrated Manuf Syst 2003; 14(2): 123–137.

Uyanik

Cell formation: a real life application. Ankara: Middle East Technical University, 2005.

Egilmez

Süer

Huang

Stochastic cellular manufacturing system design subject to maximum acceptable risk level. Comput Ind Eng 2012; 63(4): 842–854.

Nouri

Hong

TS.

Development of bacteria foraging optimization algorithm for cell formation in cellular manufacturing system considering cell load variations. J Manuf Syst 2013; 32(1): 20–31.

Liu

Dong

Lohse

et al . An investigation into minimising total energy consumption and total weighted tardiness in job shops. J Clean Prod 2014; 65: 87–96.

Dai

Tang

Giret

et al . Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robot Cim: Int Manuf 2013; 29(5): 418–429.

Chu

C-H

Tsai

A comparison of three array-based clustering techniques for manufacturing cell formation. Int J Prod Res 1990; 28(8): 1417–1433.

10.

Yasuda

Yin

A grouping genetic algorithm for the multi-objective cell formation problem. Int J Prod Res 2005; 43(4): 829–853.

11.

Chan

Lau

Chan

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.

12.

Giri

Srinivas

Mouli

An optimal design approach for a cellular manufacturing system. Proc IMechE, Part B: J Engineering Manufacture 2007; 221(6): 1101–1106.

13.

Lei

Tabu search-based approach to multi-objective machine-part cell formation. Int J Prod Res 2005; 43(24): 5241–5252.

14.

Rao

Srinivas

et al . Recognition of machine cells in a group technology layout using self-organizing neural networks. Proc IMechE, Part B: J Engineering Manufacture 2001; 215(6): 897–901.

15.

Songore

Cellular manufacturing systems design using Tabu search. Proc IMechE, Part B: J Engineering Manufacture 2000; 214(2): 169–172.

16.

Foulds

French

Wilson

JM.

The sustainable cell formation problem: manufacturing cell creation with machine modification costs. Comput Oper Res 2006; 33(4): 1010–1032.

17.

Arkat

Farahani

Ahmadizar

Multi-objective genetic algorithm for cell formation problem considering cellular layout and operations scheduling. Int J Comput Integ M 2012; 25(7): 625–635.

18.

Solimanpur

Foroughi

A new approach to the cell formation problem with alternative processing routes and operation sequence. Int J Prod Res 2011; 49(19): 5833–5849.

19.

Liu

Yin

Yasuda

et al . A heuristic algorithm for cell formation problems with consideration of multiple production factors. Int J Adv Manuf Tech 2010; 46(9–12): 1201–1213.

20.

Lin

S-W

Ying

K-C

Lee

Z-J.

Part-machine cell formation in group technology using a simulated annealing-based meta-heuristic. Int J Prod Res 2010; 48(12): 3579–3591.

21.

Papaioannou

Wilson

JM.

The evolution of cell formation problem methodologies based on recent studies (1997–2008): review and directions for future research. Eur J Oper Res 2010; 206(3): 509–521.

22.

Onwubolu

Mutingi

A genetic algorithm approach to cellular manufacturing systems. Comput Ind Eng 2001; 39(1): 125–144.

23.

Mahdavi

Paydar

Solimanpur

et al . Genetic algorithm approach for solving a cell formation problem in cellular manufacturing. Expert Syst Appl 2009; 36(3): 6598–6604.

24.

Brown

Sumichrast

RT.

CF-GGA: a grouping genetic algorithm for the cell formation problem. Int J Prod Res 2001; 39(16): 3651–3669.

25.

James

Brown

Keeling

KB.

A hybrid grouping genetic algorithm for the cell formation problem. Comput Oper Res 2007; 34(7): 2059–2079.

26.

Lian

Liu

et al . Formation of independent manufacturing cells with the consideration of multiple identical machines. Int J Prod Res 2014; 52(5): 1363–1400.

27.

Beaulieu

Gharbi

Ait-Kadi

An algorithm for the cell formation and the machine selection problems in the design of a cellular manufacturing system. Int J Prod Res 1997; 35(7): 1857–1874.

28.

Moon

Gen

A genetic algorithm-based approach for design of independent manufacturing cells. Int J Prod Econ 1999; 60: 421–426.

29.

Süer

Arikan

Babayiğit

Bi-objective cell loading problem with non-zero setup times with fuzzy aspiration levels in labour intensive manufacturing cells. Int J Prod Res 2008; 46(2): 371–404.

30.

Süer

Subramanian

Huang

Heuristic procedures and mathematical models for cell loading and scheduling in a shoe manufacturing company. Comput Ind Eng 2009; 56(2): 462–475.

31.

Süer

Cosner

Patten

Models for cell loading and product sequencing in labor-intensive cells. Comput Ind Eng 2009; 56(1): 97–105.

32.

Süer

Vazquez

Cortes

A hybrid approach of genetic algorithms and local optimizers in cell loading. Comput Ind Eng 2005; 48(3): 625–641.

33.

Wang

Optimization of machining processes from the perspective of energy consumption: a case study. J Manuf Syst 2012; 31(4): 420–428.

34.

Dai

Tang

et al . Energy-aware integrated process planning and scheduling for job shops. Proc IMechE, Part B: J Engineering Manufacture. Epub ahead of print 29 October 2014. DOI: 10.1177/0954405414553069.

35.

Bruzzone

Anghinolfi

Paolucci

et al . Energy-aware scheduling for improving manufacturing process sustainability: a mathematical model for flexible flow shops. CIRP Ann: Manuf Techn 2012; 61(1): 459–462.

36.

Mouzon

Yildirim

Twomey

Operational methods for minimization of energy consumption of manufacturing equipment. Int J Prod Res 2007; 45(18–19): 4247–4271.

37.

Choi

Y-C

Xirouchakis

A production planning in highly automated manufacturing system considering multiple process plans with different energy requirements. Int J Adv Manuf Tech 2014; 70(5–8): 853–867.

38.

Holland

JH.

Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press, 1975.

39.

Golberg

DE.

Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley, 1989.

40.

Falkenauer

Genetic algorithms and grouping problems. Chichester: John Wiley & Sons, Inc., 1998.

41.

De Lit

Falkenauer

Delchambre

. Grouping genetic algorithms: an efficient method to solve the cell formation problem. Math Comput Simulat 2000; 51(3): 257–271.

42.

Goncalves Filho

José Tiberti

. A group genetic algorithm for the machine cell formation problem. Int J Prod Econ 2006; 102(1): 1–21.

43.

Salehi

Tavakkoli-Moghaddam

A genetic algorithm-based grouping method for a cell formation problem with the efficacy measure. Int J Ind Syst Eng 2010; 6(3): 340–359.

44.

Joines

King

Culbreth

CT.

Moving beyond the parts incidence matrix: alternative routings and operations for the cell formation problem. Int J Eng Des Autom 1996.

45.

Karthikeyan

Saravanan

Ganesh

. GT machine cell formation problem in scheduling for cellular manufacturing system using meta-heuristic method. Procedia Eng 2012; 38: 2537–2547.

Integration of cell formation and job sequencing to minimize energy consumption with minimum make-span

Abstract

Keywords

Introduction

Literature review

Problem description

Assumptions

Proposed approach

Phase I: formation of independent manufacturing cells with routing selection based on the processing energy

Routing selection based on processing energy

Formation of independent manufacturing cells

CF using GA

Encoding

Creation of initial population

Feasibility improvement

Cross over

Phase 2: job sequencing and the minimization of total energy of the system

Problem formulation for phase II

Numerical problem

Results and discussion

Conclusion

Footnotes

Appendix 1

Appendix 2

Declaration of conflicting interests

Funding

References