Using Multiobjective Genetic Algorithm and Multicriteria Analysis for the Production Scheduling of a Brazilian Garment Company

1. Introduction

The Brazilian garment industry has been forced to review its production processes due to the competition against Asiatic countries like China. These countries subsidize the production in order to generate employment, which reduces the production cost. This competition has changed the way a product is made and the kind of production. The industry has focused on customized products rather than the ones large-scale produced. This transformation has been called “mass customization” [1].

In this scenario the Brazilian garment industry has been forced to recreate its production process to provide a huge diversity of good quality and cheaper products. These must be made in shorter periods and under demand. These features require the use of chronoanalysis to analyze the production load balance. Since the production time becomes crucial, the task

Tasks: set of operations taken on the same production phase.

allocation must regard the distinct production centers

Production centers: internal or external production cell composed by a set of individuals which are able to execute specific tasks.

. Most of a product lead time – processing time from the beginning to the end of the process – is spent waiting for resources. In the worse case, it can reach 80% of the total time [2]. So the production load balance is critical to acquire a good performance.

It is hard to accomplish production load balance among distinct production centers. This balance must regards the available resources and respect the objectives of the production. Lindem [3] argues that these scheduling problems are NP-Complete since the search space is a factorial of the number of variables. These problems may be solved by using exact methods. However due to time constraints, heuristics must be used in order to find good quality solutions within a reasonable time.

Nowadays the ERP (Enterprise Resource Planning) systems used by the Brazilian garment industry do not consider the finite source of resources and the constraints of the real production environment [3]. Task scheduling is done manually through simple heuristics techniques like FIFO (First In First Out) and SPT (Shortest Processing Time). Although those techniques can generate feasible solutions, these ones usually have poor quality.

In real optimization problems, as the problem addressed in this work, is generally desirable to optimize more than one performance objective at the same time. These objectives are generally conflicting, i.e., when one objective is optimized, the others become worse. The goal of multiobjective combinatorial optimization (MOCO) [4] [5] is to optimize simultaneously more than one objective. MOCO problems have a set of optimal solutions (instead of a single optimum) in the sense that no other solutions are superior to them when all objectives are taken into account. They are known as Pareto optimal or efficient solutions.

Solving MOCO problems is quite different from single-objective case, where an optimal solution is searched. The difficulty is not only due to the combinatorial complexity as in single-objective case, but also due to the research of all elements of the efficient set, whose cardinality grows with the number of objectives.

In the literature, some authors have proposed exact methods for solving specific MOCO problems, which are generally valid to bi-objective problems but cannot be adapted easily to a higher number of objectives. Also, the exact methods are inefficient to solve large-scale NP-hard MOCO problems. As in the single-objective case, the use of heuristic/metaheuristic techniques seems to be the most promising approach to MOCO problems because of their efficiency, generality and relative simplicity of implementation [5] [6] [7]. Genetic algorithms are the most commonly used metaheuristic in the literature to solve these problems [8].

The objective of this work is to develop a method to carry out the production scheduling of a Brazilian garment company, placed at Espírito Santo state, in real time, which must regularly balance the product demands with the available resources. This is done in order to: reduce the total production time; prioritize the use of internal production centers of the company rather than the use of external production centers; and reduce the downtime of the internal production centers.

With this purpose, initially a mixed integer programming model was developed for the problem. Then, we implemented a multiobjective genetic algorithm (MGA) based on the NSGA-II [4] model, which generates a set of sub-optimal solutions to the addressed problem. After we used the multicriteria method Weighted Sum Model – WSM [9] to select one of the solutions obtained by the MGA to be applied to the production scheduling. The mixed integer programming model, the MGA developed and its automatic combination with the multicriteria method WSM are original contributions of this work.

2. Addressed problem

The production planning process of the Brazilian garment industry may be split into many phases from demand provision to tasks scheduling at each machine. Tubino [2] says that the production planning is defined by the demand from the Planning Master of Production (PMP). This demand is sent to the Material Requirements Planning (MRP) that calculates the material required. Then it becomes available to the Issuance of Production Orders and Sequencing. These steps are depicted at Figure 1.

Figure 1.

Production planning.

This work approaches the scheduling phase where a set of tasks has to be distributed among production centers. As said before, production center is an internal or external production cell composed by a set of specialized individuals. Each task may be done by a set of production centers and each production center is able to execute many tasks. The objectives of this work are: i) to minimize the total production time (makespan – time from the beginning of the first task to the end of the last task); ii) to maximize the use of internal production centers – the use of internal production centers does not imply cost overhead

Except when the company has to pay overtime.

since employees' salary are already at the payroll of the company; iii) to minimize the internal production centers downtime.

These three objectives have been chosen in order to meet the needs of the analyzed company. Some couple of them are conflicting, i.e., when one has an improvement the other tends to get worse. Others objectives are not conflicting, but the optimization of one does not guarantee the optimization of the other. As an example of conflicting objectives, we have the objectives “to minimize the total production time” and “to maximize the use of internal production centers”: for minimizing the total production time it is necessary to make the best use of the available production centers, regardless of whether they are internal or external. The objectives “to minimize the total production time” and “to minimize the internal production centers downtime” are not conflicting: by decreasing the downtime of the production centers, the total production time also tends to decrease. However, if tasks are allocated to an internal production center, which together have an execution time shorter than the total production time, it is possible to arrange them in different ways without changing the total production time. The objective “to minimize the internal production centers downtime” requires the best arrangement of the tasks within each internal production center.

In order to better describe the addressed problem, Figure 2 depicts the steps toward the production of a short. The production process is composed by a set of production stages. Each stage has a set of operations to be performed. In this work, this set is called task. In this example, there are 6 production stages (scratch, cut, sewing, embroidery, laundry and finishing). The sewing task lasts 12.54 minutes and is composed by d operations. There are h production centers qualified to perform the sewing task.

Figure 2.

Example of a production process.

The execution time of a task is the sum of the execution time of its operations. This time is used during the scheduling, which hides the complexity of the operation distribution inside a stage. So it can be seen as a classical task scheduling where each production center is a machine and the operations set of each production stage is a task.

During the scheduling process the following constraints must be respected: i) for each product exists an execution order of tasks, i.e., there is a precedence order among tasks; ii) each task can only be executed in production centers that are qualified to it, i.e. production centers are specialized; iii) employees stop working regularly for lunch and eventually for others reasons like training or health care; iv) depending on the workload it is possible to work overtime; v) the time spent to go from one to another production center must be considered.

The addressed problem is similar to the flexible job shop problem, in which there is a set of work centers that groups identical machines operating concurrently; inside a work center, a task may be executed by any of the machines available [10]. Figure 3 depicts an example of adapting the flexible job shop to the addressed problem. In this figure, three products are made: Product 1 requires tasks T ₁₁, T ₁₂, T ₁₃, T ₁₄, T ₁₅ and T ₁₆; Product 2 requires tasks T ₂₁, T ₂₂, T ₂₃, T ₂₅ and T ₂₆; Product 3 requires tasks T ₃₁, T ₃₂, T ₃₃, T ₃₄ and T ₃₆. All tasks are distributed among production centers C ₁, C ₂, C ₃, C ₄ and C ₅.

In Figure 3 the problem is divided into 2 subproblems: A and B. At subproblem A the tasks are distributed among the production centers that can execute them. At this step is important to prioritize internal production centers in order to take profit of the company processing power that is already available. At subproblem B the tasks must be scheduled respecting the precedence order of tasks.

Figure 3.

Task distribution among the production centers.

Figure 4(1) depicts an example of scheduling for the tasks listed in Figure 3. Note that the precedence relation among tasks is respected, that is, a task T _ij , where i means the product to be made and j the production stage, can be started only after all tasks T _ik (k < j) have been finished. The Figure 4(2) shows the downtime (gray arrows) in the production centers. For instance, task T ₁₃ at production center C ₅ waits for the task T ₁₂ at C ₃ before starts executing. Figure 4(3) shows that the tasks T ₂₅ and T ₃₁ at production center C ₁ and T ₃₈ at C ₅ (black boxes) were ready but had to be frozen because of the unavailability of the production centers C ₁ and C ₅.

Figure 4.

Example of tasks scheduling.

The addressed problem is similar to some works found in the literature, like Senthilkumar and Narayanan [11], Santosa, Budiman and Wiratino [12], Abdelmaguid [13], Dayou, Pu and Ji [14], Chang and Chyu [15] and Franco [16]. However, these works do not consider real-time tasks sequencing or are not applied to real problems.

It is important to note that the chronoanalysis method used here is not the focus of this work. However, in this work, the production time includes tolerance, rhythm and others variables from the chronoanalysis.

2.1. Mathematical modeling

For this modeling was created a sequencing unit (SU) which defines a time-slice of work. Each production center has distinct sequencing units, in which tasks are scheduled all day long. Figure 5 depicts a set of sequencing units that describes the behavior of a particular production center. The overtime work is treated as a distinct sequencing unit, since they have particular features like cost.

Figure 5.

Sequencing units organization.

This model defines a variable N that indicates the total number of tasks, including an additional task that is required for the initialization of the sequencing units.

Below is presented the mixed integer programming model for the addressed problem. The parameters of the problem are presented, followed by the interval indexes, the decision variables and finally by the equations for the three objective functions together with their constraints.

Parameters

NCP – Number of production centers.

NSU – Number of sequencing units.

NJ – Number of tasks to be scheduled.

N – Total number of tasks (N = NJ + 1). The last one is the fictitious task that was added to the model as the initial task of every sequencing unit.

M – Large enough value.

WL _i – Workload of task i.

CP _s – Production center of the sequencing unit s.

Minimum _s – Starting time of the sequencing unit s.

Time _s – Amount of time available at sequencing unit s.

CPJ _i – Set of production centers that can execute the task i.

CI – Set of internal production centers.

PRE _i – Set of tasks that are a precondition for the execution of task i.

$$OffSe{t}_{c_k{c}_l}$$ – Time for going from production center c _k to c _l .

Indexes

i, j – Indexes of tasks. i, j ∈ [1, N].

c – Index of production centers. c ∈ [1, NCP].

s – Indexes of sequencing units. s ∈ [1, NSU].

Decision variables

Start _i – Non-negative linear variable that represents the starting time of task i.

End _i – Non-negative linear variable that represents the ending time of task i.

WLS _si – Non-negative linear variable that represents the workload of task i at the sequencing unit s.

StartS _si – Non-negative linear variable that represents the starting time of task i at sequencing unit s.

DT _sij – Non-negative linear variable that represents the downtime between tasks i and j in the sequencing unit s.

Y _sij – Non-negative linear variable that represents the flow i, j of the sequencing unit s.

MkSpan – Non-negative linear variable that represents the time between the end of the last finished task and the start of the first task.

IntTime – Non-negative linear variable that represents the amount of execution time of tasks in the internal production centers.

DownTime – Non-negative linear variable that represents the amount of internal production centers downtime.

$Z_{ci}=\{\begin{array}{l}1 \text{ if task}i\text{is allocated to production center}c.\\ 0 \text{ otherwise}\end{array}$

$$U_{si}=\{\begin{array}{l}\text{1 if task }i\text{ is allocated to sequencing unit }s\text{.}\\ 0 \text{otherwise}\end{array}$$

$$X_{sij}=\{\begin{array}{l}1 \text{ if the sequence }i,j\text{ happens in the sequencing unit }s.\\ 0 \text{otherwise}\end{array}$$

Model

$$O.F.1= \begin{array}{cc}Min& MkSpan\end{array}$$ E1

$$O.F.2=\begin{array}{cc}Max& IntTime\end{array}$$ E2

$$O.F.3=\begin{array}{cc}Min& DownTime\end{array}$$ E3

Subject to:

$$\begin{array}{cc}MkSpan\ge En{d}_i& \forall i/i\ne N\end{array}$$ E4

$$IntTime={\displaystyle \sum _{s/C{P}_s\in CI}{\displaystyle \sum _{i/i\ne N}WL{S}_{si}}}$$ E5

$$DownTime={\displaystyle \sum _{s/C{P}_s\in CI}{\displaystyle \sum _i{\displaystyle \sum _{j/j\ne N}D{T}_{sij}}}}$$ E6

$$D{T}_{sij}\ge Start{S}_{sj}-(Start{S}_{si}+WL{S}_{si})-M\times (1-X_{sij})$$ E7

$$\begin{array}{cc}{\displaystyle \sum _{i/C{P}_s\in CP{J}_i}^{}{Y}_{sij}}-{\displaystyle \sum _{i/i\ne N,C{P}_s\in CP{J}_i}^{}{Y}_{sji}=U_{sj}}& \forall \end{array}s,\forall j/j\ne N\begin{array}{cc}and& C{P}_s\in CP{J}_j\end{array}$$ E8

$$\begin{array}{cc}{Y}_{sij}\le M\times X_{sij}& \forall \end{array}s,\forall i/C{P}_s\in CP{J}_i,\forall j/j\ne N\begin{array}{cc}and& C{P}_s\in CP{J}_j\end{array}$$ E9

$$\begin{array}{cc}{U}_{sN}=1& \forall s\end{array}$$ E10

$$\begin{array}{cc}{\displaystyle \sum _{c/c\in CP{J}_i}{Z}_{ci}}=1& \forall \end{array}i/i\ne N$$ E11

$$\begin{array}{cc}{\displaystyle \sum _{s/C{P}_s\in CP{J}_i}{U}_{si}}\ge 1& \forall \end{array}i$$ E12

$$\begin{array}{cc}{U}_{si}\le Z_{ci}& \forall \end{array}i,\forall s/C{P}_s\in CP{J}_i,c=C{P}_s$$ E13

$$\begin{array}{cc}{\displaystyle \sum _{i/C{P}_s\in CP{J}_i}{X}_{sij}=U_{sj}}& \forall \end{array}s,\forall j/j\ne N\begin{array}{cc}and& C{P}_s\in CP{J}_j\end{array}$$ E14

$$\begin{array}{cc}{\displaystyle \sum _{j/j\ne N,C{P}_s\in CP{J}_j}{X}_{sij}\le U_{si}}& \forall \end{array}s,\forall i/i\ne N\begin{array}{cc}& \end{array}$$ E15

$$\begin{array}{cc}Start{S}_{si}\ge Minimu{m}_s\times U_{si}& \forall \end{array}s/C{P}_s\in CP{J}_i,\forall i/i\ne N\begin{array}{cc}& \end{array}$$ E16

$$\begin{array}{cc}Start{S}_{si}+WL{S}_{si}\le Minimi{m}_s+Tim{e}_s+M\times (1-U_{si})& \forall \end{array}s,\forall i/i\ne N\begin{array}{cc}& \end{array}\begin{array}{cc}and& C{P}_s\in CP{J}_i\end{array}$$ E17

$$\begin{array}{cc}{\displaystyle \sum _{s/C{P}_s=c,C{P}_s\in CP{J}_i}WL{S}_{si}=W{L}_{ci}}*Z_{ci}& \forall \end{array}i,\forall c\begin{array}{cc}& \end{array}$$ E18

$$\begin{array}{cc}WL{S}_{si}\le M\times U_{si}& \forall \end{array}s/C{P}_s\in CP{J}_i,\forall i\begin{array}{cc}& \end{array}$$ E19

$$\begin{array}{cc}Star{t}_i\le Start{S}_{si}+M\times (1-U_{si})& \forall \end{array}s/C{P}_s\in CP{J}_i,\forall i\begin{array}{cc}& \end{array}$$ E20

$$\begin{array}{cc}En{d}_i\le Start{S}_{si}+WL{S}_{si}-M\times (1-U_{si})& \forall \end{array}s/C{P}_s\in CP{J}_i,\forall i\begin{array}{cc}& \end{array}$$ E21

$$\begin{array}{cc}En{d}_i\ge Star{t}_i& \forall \end{array}i/i\ne N\begin{array}{cc}& \end{array}$$ E22

$$\begin{array}{cc}Start{S}_{sj}\ge Start{S}_{si}+WL{S}_{si}-M\times (1-X_{sij})& \forall \end{array}s,\forall i/C{P}_s\in CP{S}_i,\begin{array}{ccc}\forall j/j\ne N& and& C{P}_s\in CP{J}_j\end{array}$$ E23

$$\begin{array}{cc}Star{t}_j\ge En{d}_i+OffSe{t}_{c_1{c}_2}-M\times (2-Z_{c_{1}i}-Z_{c_{2}j})& \forall \end{array}{c}_1,\forall c_2,\begin{array}{ccc}\forall i/i\ne N& and& c_1\in CP{J}_i\end{array},\forall j/j\ne N,i\in PR{E}_j\begin{array}{cc}and& c_2\in CP{J}_j\end{array}$$ E24

Where:

1. Objective function that aims to minimize the total production time (makespan).

2. Objective function that aims to maximize the use of internal production centers.

3. Objective function that aims to minimize the amount of downtime at the internal production centers.

4. The makespan can be seen as the ending time of the last task.

5. The amount of execution time at the internal production centers.

6. The amount of downtime at the internal production centers.

7. The amount of downtime between tasks i and j in the sequencing unit s.

8. Constrains the flow between tasks i and j.

9. X _sij = 1 if there is a flow from task i to task j at the sequencing unit s.

10. Asserts that task N belongs to every sequencing unit.

11. Asserts that each task is executed on just one production center.

12. Asserts that each task is executed on at least one sequencing unit.

13. Asserts that a task i can only be executed on a sequencing unit s if the task i is scheduled to the production center of the sequencing unit s.

14. If the task j is performed in sequencing unit s then there is just one task that immediately precedes j in s.

15. If the task j is performed in sequencing unit s then there is at most one task that is immediately preceded by j in s.

16. Asserts that each task i must be started only after the start of the sequencing unit s where task i is allocated.

17. Asserts that the maximum available time of the sequencing unit is being respected.

18. Asserts that the required workload of task i is allocated.

19. Asserts that the workload of task i at the sequencing unit s is 0 (zero) if task i is not scheduled to the sequencing unit s.

20. Asserts that the beginning time of task i, Start _i , must be lower or equal to the beginning time of task i at any sequencing unit where it is allocated.

21. Asserts that the ending time of task i, End _i , must be greater or equal to the ending time of task i at any sequencing unit where it is allocated.

22. Asserts that the ending time of task i must be at least equal to its beginning.

23. Asserts that the task i starts only after the ending time of the task j that immediately precedes i in the sequencing unit s.

24. Asserts that task j only can starts after the ending time of its predecessor tasks. This restriction takes into account the travel time between the production centers.

3. Proposed method

We propose in this work a method that combines multiobjective genetic algorithm and multicriteria decision analysis for solving the addressed problem. The multiobjective genetic algorithm (MGA) aims to find a good approximation of the efficient solution set, considering the three objectives of the problem. A multicriteria decision analysis method is applied on the solution set obtained by the MGA in order to choose one solution, which will be used by the analyzed garment company.

Deb [4] presents a list of evolutionary algorithms for solving problems with multiple objectives: Vector Evaluated GA (VEGA); Lexicographic Ordering GA; Vector Optimized Evolution Strategy (VOES); Weight-Based GA (WBGA); Multiple Objective GA (MOGA); Niched Pareto GA (NPGA, NPGA 2); Non dominated Sorting GA (NSGA, NSGA-II); Distance-based Pareto GA (DPGA); Thermodynamical GA (TDGA); Strength Pareto Evolutionary Algorithm (SPEA, SPEA 2); Mult-Objective Messy GA (MOMGA-I, II, III); Pareto Archived ES (PAES); Pareto Envelope-based Selection Algorithm (PESA, PESA II); Micro GA-MOEA (µGA, µGA2); and Multi-Objective Bayesian Optimization Algorithm (mBOA).

In this work, we have chosen the NSGA-II [17] evolutionary algorithm since it works with any number of objectives, which can be easily added or removed. This feature facilitates the company to adapt to the market demands – the current objectives may not be sufficient in the future, requiring the company to also focus on other goals –. Besides, there are another Brazilian garment companies interested in using the proposed method, which may have different objectives.

The main methods of multicriteria decision analysis are [18]: Weighted Sum Model, Condorcet method, analytic hierarchic process, ELECTRE methods, Promethee method and MacBeth method.

The Weighted Sum Model – WSM is used in this work due to its simplicity and, mainly, due to its structure of candidates and voters. In this work, WSM performs as a decision maker by considering each solution returned by the MGA as a candidate and each objective of the problem as a voter.

The method proposed in this work is detailed in Section 3.2. But first, in Section 3.1, we describe the multiobjective combinatorial optimization, in order to facilitate the understanding of the proposed method.

3.1. Multiobjective combinatorial optimization

According to Arroyo [19], a Multiobjective Combinatorial Optimization (MOCO) problem consists of minimizing (or maximizing) a set of objectives while satisfying a set of constraints. In a MOCO problem, there is no single solution that optimizes each objective, but a set of efficient solutions in such way that no solution can be considered better than another solution for all objectives.

Among the different ways of defining an optimal solution for MOCO problems, Pitombeira [20] highlights the method proposed by the economist Vilfredo Pareto in the nineteenth century, which introduces the dominance concept. He argues that an optimal solution for a MOCO problem must have a balance between the different objective functions, so that the attempt of improving the value of one function implies the worsening of one or more of the others. This concept is called Pareto optimal.

MOCO aims to find the Pareto optimal set (also known as Pareto frontier) or the best approximation of it. However, it is necessary to define a binary relationship called Pareto dominance: a solution x ₁ dominates another solution x ₂ if the functional values of x ₁ are better than or equal to the functional values of x ₂ and at least one of the functional values of x ₁ is strictly better than the functional value of x ₂ [4]. The Pareto optimal set consists of all non-dominated solutions of the search space.

Deb [4] says that in addition to finding a solution set near to the Pareto frontier, it is necessary that these solutions are well distributed, which allows a broader coverage of the search space. This fact facilitates the decision making, because, regardless of the weight assigned to each criterion, a quality solution will be chosen.

3.2. Multiobjective genetic algorithm proposed

As we have already mentioned, the model adopted for the development of the multiobjective genetic algorithm (MGA) proposed is the NSGA-II. According to Deb [4], it is an elitist search procedure, which preserves the dominant solutions through the generations. The process starts by building a population (P), with nPop individuals (solutions). The populations of the next generations are obtained through the application of mutation, selection and crossover operators. The purpose is to find a diversified solution set near to the Pareto frontier. With the crowding distance [4], we can qualify the space around the solution, allowing a greater diversity of the solution set and, thereby, leading more quickly to a highest quality solution. The crowding distance (d) of an individual in the i ^th position of the population P, considering r objectives, is given by Equation 25, where f _k ^min and f _k ^max represent, respectively, the minimum and maximum values in P for the objective function f _k (1 ≤ k ≤ r). For any solution set, the solution that brings the highest level of diversity is the one with the greatest crowding distance.

$$d_i=\frac{f_1^{(i+1)}-f_1^{(i-1)}}{f_1^{\max }-f_1^{\min }}+\frac{f_2^{(i+1)}-f_2^{(i-1)}}{f_2^{\max }-f_2^{\min }}+\mathrm{...}+\frac{f_r^{(i+1)}-f_r^{(i-1)}}{f_r^{\max }-f_r^{\min }}$$ E25

Section 3.2.1 presents the solution representation used in this work. The steps done by the MGA proposed, from the building of the initial population to the choice of the solution to be used by the analyzed garment company, is detailed in Section 3.2.2.

3.2.1. Solution representation

The solution (individual) is represented by two integer arrays: priorities array and production centers array. Tasks are represented by the indexes of both arrays. The priorities array defines the allocation sequence of the tasks and the production centers array indicates the production center responsible for the execution of each task. Figure 6 depicts an example of the solution representation used in this work, in which the first task to be allocated is the task 3 – represented by the position (index) with value 1 in the priorities array – and the production center responsible by its execution is the production center 3 – value of the position 3 of the production centers array –; the second task to be allocated is the task 7, which will be executed in the production center 5; and so on. This representation is based on the representations described in [14] [21] [22] and [23].

Figure 6.

Solution representation.

A task T _i can only start after the end of the predecessor task T _j plus the travel time from the production center responsible by T _i to the production center responsible by T _j . Thus, when a task is selected to be allocated, a recursive search is done in order to allocate the predecessor tasks of it.

3.2.2. Population evolution

The MGA proposed is described by the flowchart of Figure 7, which starts by building the initial population and finalizes when the stop criterion is reached. Mutation, selection and crossover genetic operators are applied in the current population in order to build new individuals (offsprings). At the end of each generation, the less evolved individuals are eliminated and the evolutionary process continues with the best individuals.

Step 1 – Building the initial population

Two arrays of size N are created for each individual, where N is the number of tasks to be allocated. The priorities array stores the allocation sequence and the production centers array determines the production center responsible for each task. These arrays are randomly created.

Step 2 – Generating the offspring population

An offspring population, P _aux , with nPop individuals is created from P, using the tournament selection method [24] and mutation and crossover genetic operators. The tournament method used in this work randomly selects four individuals from P and the best two are selected as the parent individuals to be used by the crossover operator.

Figure 7.

NSGA-II algorithm.

The crossover operator used in this work is based on the variable one-point cut operator [24]. Figure 8 depicts examples of the crossover (8a and 8b) and mutation (8c and 8d) operators developed in this work. As can been seen in Figure 8(a), the priorities array of the offspring individual is composed by the genes of the priorities array of the parent individual Parent ₁ until the cut-point and, from this point, it is composed by the remaining priorities in the order that they appear in the priorities array of the parent individual Parent ₂. In the production centers array, the crossover method is applied by using the same cut-point and the production centers array of the offspring individual is composed by the genes of the production centers array of the parent individual Parent ₁ until the cut-point and, from this point, it is composed by the genes of the production centers array of the parent individual Parent ₂, as can be visualized in Figure 8(b).

The mutation operator is applied at the priorities array as shown in Figure 8(c), where two genes are randomly selected and their contents are exchanged. The mutation operator acts in the production center array as shown in Figure 8(d), where a gene (position i) is randomly selected and replaced by another production center capable of execute the task i. This production center is randomly chosen. The mutation operator is performed on 5% of the genes of each offspring individual generated by the crossover operator.

Step 3 – Evaluation, sorting and grouping of individuals by dominance and crowding distance

The offspring population P _aux is added to the population P, defining a new population of 2×nPop individuals – nPop individuals from P and nPop individuals from P _aux –. It is sorted in ascending order by the dominance level

The dominance level of an individual x is the number of individuals in the population that dominates x; for example, an individual dominated by only one individual in the population has dominance level of 1.

. The crowding distance is used as a tie-breaker, i.e., when two individuals have the same dominance level, it is chosen the one with the greatest crowding distance.

Step 4 – Selection of individuals by elitism

The nPop best individuals from the new population (P _aux added to P) are selected to continue the evolutionary process, while the others are discarded.

Step 5 – Selection of the best individual

At the end of the evolutionary process, the MGA returns a set of individuals with dominance level of 0 (zero), that is, individuals of the current population that no other individual dominates. This set of individuals represents an approximation of the Pareto frontier.

The Weight Sum Model (WSM) [25] multicriteria decision method is applied for choosing a solution from the set returned by the MGA that will be used by the analyzed garment company. In the WSM method, the candidates are ranked by the preferences of the decision maker, in which the best candidate for a particular preference receives 1 (one) point, the second one receives 2 (two) points, and so on. The points received for each preference are summed, and the best candidate is the one with the smallest sum.

Figure 8.

Genetic operators of crossover and mutation.

In this work, the WSM method replaces the grade given by the voters to the candidates. This replacement ranks each solution returned by the MGA according to each objective. Figure 9 illustrates the use of the WSM method in this work where four solutions (columns) must be evaluated according to three objectives (rows). For the first objective, to minimize the total production time (makespan), the solution 3 has the best value, obtaining the rank 1; the solution 4 has the best second value, obtaining the rank 2; and the solutions 1 and 2 obtain, respectively, the ranks 3 and 4. The same ranking is done for the others objectives. After summing the rank obtained for each objective, the solution 1 is chosen because it has the smallest sum.

4. Computational results

All computational experiments were performed on a Dell Vostro 3700 notebook with 1.73 GHz Intel Core I7 processor and 6 Gbytes of RAM memory.

The computation experiments regard to real data that represent the May 2012 production demand of the analyzed company: 567 products, 1511 production orders, 3937 tasks and 181 production centers.

Figure 9.

Weighted sum model.

In the experiments, 12 hours of execution time was established as the stop criterion of the genetic algorithm. This value was defined because it represents the available time between two work days. The population size (nPop) and the mutation rate (tx) were empirically set at nPop=200 individuals and tx=5%.

In the first experiment, we compare the results of the proposed method with the results manually obtained by the analyzed company at May 2011. Figure 10 depicts the production deviation of each stage between May 2011 and May 2012, where we can note an increase of the production at almost all stages.

Figure 10.

Production deviation of each stage (May 2011 x May 2012).

The results obtained by the analyzed company at May 2011 were: 42 production days to execute all tasks; 20% of the tasks were performed in internal production centers; and the downtime rate of the internal production centers was 37%.

In this experiment, five runs of the proposed method were done, obtaining the following average results: 36 production days to execute all tasks; 32% of the tasks were performed in internal production centers; and the downtime rate of the internal production centers was 16%. It is worth to mention that the worst results obtained are: 38 production days to execute all tasks; 35% of the tasks were performed in internal production centers; and the downtime rate of the internal production centers was 18%. The obtained results were better than the ones manually got at May 2011, even considering the increase of the production between May 2011 and May 2012 (see Figure 10).

We mean “selected solution” as the solution (individual) of the population of generation g that would be returned by the proposed method if the genetic algorithm ended at generation g. Figures 11, 12 and 13 depict the obtained values for each objective of the selected solutions during 12 hours of execution. In these figures are also used the average results obtained after five runs of the proposed method. We can note that only after 8 hours we can get a good solution - about 40 production days, between 15 and 35% of the tasks performed in internal production centers and downtime rate of internal production centers near to 18%.

We highlight that the genetic algorithm parameters were adjusted considering an execution time of 12 hours. A genetic algorithm (GA) that works with a large population takes longer to found a good solution than a GA with a small population. However, it explores a larger solution space, thus obtaining better solutions. If a smaller execution time is required for running the proposed method, we should adjust the GA parameters in order to find good quality solutions.

We can also see in Figures 11, 12 and 13 that the objectives “to minimize the makespan” and “to minimize the internal production centers downtime” are not conflicting, i.e., when the value of one objective has an improvement, the value of the other also tends to improve. The objective “to maximize the use of internal production centers” has conflict with the others objectives.

Figure 11.

Selected solutions during 12 hours of execution. Objective: to minimize the makespan.

Figure 12.

Selected solutions during 12 hours of execution. Objective: to maximize the use of internal production centers.

Figure 13.

Selected solutions during 12 hours of execution. Objective: to minimize the internal production centers downtime.

Figure 14, 15 and 16 depict the obtained values for each selected solution and also for the best and worst solutions of the population at each generation. By analyzing the graphs presented in these figures, we can realize the diversification of the population throughout the generations. Again we can note that the objective “to maximize the use of internal production centers” (Figure 15) is conflicting with the other two. While the selected solutions tend to get close to the best solutions for the other two objectives (Figures 14 and 16), for this objective the selected solutions tend to get close to the worst solutions.

In the second experiment, the proposed method was compared with the commercial application PREACTOR, which is the leading software in the sector of finite capacity production planning in Brazil and worldwide, with over 4500 customers in 67 countries [26]. However, it was necessary to execute the proposed method considering only the objective "to minimize the makespan", because it was not possible to configure PREACTOR for working with three objectives.

Although the proposed method and PREACTOR perform the task scheduling, they have different purposes. PREACTOR is a universal tool of finite capacity production planning, which uses priority rules to perform the scheduling. The users of this tool can interact with the generated production planning. The proposed method is specific for garment companies, in which the large number of tasks makes difficult a manual evaluation. The purpose of the comparison between these methods is to validate the scheduling obtained by our proposal.

Figure 14.

Best, worst and selected solutions during 12 hours of execution. Objective: to minimize the makespan.

Figure 15.

Best, worst and selected solutions during 12 hours of execution. Objective: to maximize the use of internal production centers.

Figure 16.

Best, worst and selected solutions during 12 hours of execution. Objective: to minimize the internal production centers downtime.

In this experiment, five runs of the proposed method were done. After 12 hours of execution, the proposed method has obtained an average of 32 days production planning, 17.9% lower than the 39 days production planning proposed by PREACTOR. The worst result obtained by the proposed method was 33 days production planning. It is worth to mention that PREACTOR took 12 minutes to reach its result. Figure 17 depicts that the proposed method overcomes the result obtained by PREACTOR after about 100 minutes of execution.

Figure 17.

Proposed method × PREACTOR.

5. Conclusion remarks

The objective of this work is to develop a method to carry out the production scheduling of a Brazilian garment company in real time. Three objectives were considered: to minimize the total production time; to maximize the use of internal production centers; and to reduce the downtime of the internal production centers.

To achieve this goal, initially we have defined a mixed integer programming model for the addressed problem. Based on this model, we have proposed a method that combines a NSGA-II multiobjective genetic algorithm with the multicriteria method Weighted Sum Model - WSM. The mathematical model, the multiobjective genetic algorithm developed and its automatic combination with the multicriteria method WSM are contributions of this work.

Computational experiments were done in order to evaluate the proposed method. It was used real data provided by the analyzed garment company, which are related to May 2012 production demand. In the first experiment, the average results obtained by the proposed method were compared with the results manually obtained by the analyzed company at May 2011. Even with the increase of the production between these periods, the proposed method has decreased of 16.3% the production days. It has also got a higher rate of use and a smaller downtime rate of internal production centers. We have highlighted that the proposed method can obtain good quality solutions even when a smaller execution time is available. However, it is necessary to make an adjustment of the genetic algorithm parameters considering the available execution time.

In the second experiment, the proposed method was compared with the commercial software PREACTOR, considering only the objective "to minimize the makespan". The average obtained result was 17.9% better than the one obtained by PREACTOR. It was also shown that the proposed method overcame the result obtained by PREACTOR after about 100 minutes of execution.

It is worth to mention another advantage of the proposed method: as it is based on NSGA-II model, we can easily add and remove objectives. To do that a slight modification in the procedure that evaluates solutions is necessary. Thus, the proposed method can be suited to new needs of the garment industry or to other industrial branches.