1.Introduction

Integrated process planning and scheduling problem (IPPS) is a mixture of process planning and scheduling. Process planning contains sub-problems of routing and loading. Routing focuses on determining which sequence to use among the replaceable operational sequences, and loading is a problem of determining which resources such as machines and tools are allocated to the operation for execution. A variety of resources and alternative sequences are available in manufacturing for the same manufacturing feature. On the other hand, scheduling is a problem of determining when the operations start and end on each machine, assuming that a process plan has been determined [6, 20].

In IPPS, several flexibilities and constraints have been considered. Process flexibility means that there are alternative operation sequences to be performed in a job. Sequence flexibility is a changeability of sequence order of operations. Machine and tool flexibilities imply that an operation can be performed on alternative machines with alternative tools and tool access direction, respectively. Process planning is related to the process, machine, and tool flexibilities, and scheduling targets the sequence flexibility. Each machine (or machining center) has a tool magazine that can mount multiple tools, thus can handle many kinds of operations in a machine. In practice, since the magazine capacity and the number of tools are limited, efficient decision-making is required under the limited manufacturing resources.

Due to the high degree of complexity, traditionally, a sequential approach has been preferred for IPPS, which determines process planning firstly and then performs scheduling independently based on the results. However, the two sub-problems are intricately interwoven. Thus, the optimal process plan does not result in the optimal schedule. Even the optimal process plan can lead to an infeasible schedule [19, 23]. It highlights the importance of the IPPS which solve both sub-problems simultaneously.

There is a myriad of alternative solutions in IPPS due to various flexibilities. It makes the problem complicated, but at the same time, it has the considerable potential to improve the performance of the system. Since IPPS is NP-hard [10], meta-heuristics have been mainly applied as optimization methods. According to Ausaf et al. [2] and Petrović et al. [21], GA, ant colony optimization (ACO), particle swarm optimization (PSO), and various memetic heuristics combined with these have frequently been applied for IPPS [12]. Among them, GA is the most preferred. With IPPS having a huge solution space, the superior exploitation capability of GA is advantageous to improve the solution quality.

There are abundant studies to solve IPPS using GA. Morad and Zalzala [18] proposed a simple GA for IPPS considering machine flexibility only. To deal with various flexibilities such as process, sequence, and machine in IPPS, Kim et al. [11] introduced a symbiotic evolutionary algorithm that mimics the process of coevolution of various species. Kim et al. [10] improved their previous study by proposing a multi- layered symbiotic evolutionary algorithm for IPPS, which considers tool flexibility, tool magazine capacity constraint, and tool capacity constraint additionally compared to previous IPPS. Shao et al. [22] proposed a GA that establishes an optimal plan reflecting the real-time status of the shop floor. Liu et al. [17] developed an adaptive annealing genetic algorithm for IPPS in a job shop, which adopts Boltzmann probability selection using adaptive mutation probability and simulated annealing to avoid premature convergence. Li et al. [14] presented a mathematical programming modeling for IPPS and optimized it by an evolutionary algorithm. Li et al. [15] also proposed a hybrid algorithm that uses the GA as the main algorithm and applies the Tabu search to further improve the solution. Li et al. [13] proposed a GA that improves premature convergence by a learning operator that perform a crossover operation between the currently selected solution and the current best solution or the generation’s best solution. Lian et al. [16] applied the imperialist competitive algorithm [1] to enhance exploitation, which evolves empires consisting of an imperialist and colonies in parallel. Zhang and Wong [24] proposed a GA with object-coding representation, inferior selection, job-based precedence preservative crossover, shifting gene and shifting machine mutations, and crowding replacement scheme. Cinar et al. [7] proposed a constructive GA based on the Giffler-Thompson algorithm [8] for flexible job shop scheduling, in which a priority-based representation that consists of the priority of operations is used.

Although many studies using GA for IPPS have been conducted in the past, tool flexibility and capacity constraints are not considered except for Kim et al. [10]. Also, most studies use the problem set of Kim et al. [11] as a benchmark to evaluate the performance of their algorithms. This paper, which considers tool flexibility and capacity constraints, uses the new problem set of Kim et al. [10] as a benchmark. In this respect, this study is different from the existing studies.

In this paper, we aim at developing an improved genetic algorithm for IPPS with tool flexibility and tool related constraints. We adopted a traditional genetic algorithm procedure, but we employed three methods to improve solution quality and computation time. The first is the initial population generation using a random circular queue. It binds the population size, which decreases computation time critically. Second, we adopted an inferior selection to maintain exploitation capability in the evolution process. Third, we employed a modification of the hybrid scheduling algorithm [3, 10] to decode the chromosome of the individual into a schedule.

We organized this paper as follows. Section 2 explains IPPS in detail after the description on flexibilities for the flexible manufacturing system and network representation. The proposed genetic algorithm is introduced in Section 3. Section 4 is prepared for describing the experimental parameters and results. Finally, we conclude and discuss our research in Section 5.

2.IPPS Problem

A simple description of the IPPS problem is as follows [5].

We assume following operating conditions:

We will illustrate the problem in detail using the network representation by Ho and Moodie [9]. <Figure 1> shows a simple example of an IPPS. There are a total of three jobs, job 1, job 2, and job 3, each of which is a network of operation nodes. The node number is the identifier of an operation in the job, that is, the operation 1 of job 1 and the operation 1 of job 2 may be different. Each job network has two dummy nodes indicating the start (S1, S2, and S3) and the end of the job (E1, E2, and E3). Arrowed lines indicate precedence constraints. The operations with the tail of the arrowed line are the immediate predecessors of the operation indicated by the head of the arrow. That is, the head operation must be processed after the tail operation is completed. For example, operation 1 of job 1 must be completed before operation 2 of the job is executed. They cannot be processed simultaneously, and succeeding operations cannot be pre-processed.

In the network representation, OR notation implies process flexibility, only one branch can be selected for processing. If a schedule does not satisfy any precedence constraint, it becomes infeasible. In the network representation, the branching node without OR notation such as operation 1 in job 3 denotes an AND node that all operations belonging to the branch must be processed to complete the job. For instance, job 1 consists of 9 nodes, 1 AND node (S1), 1 OR node (operation 1), and seven ordinary nodes (operation 2 to 7 and E1). The S1 node has two process routes (operation 1 to 5 and 6-7) and both routes have to be processed because it is an AND node. The operation 1, on the other hands, is an OR node which has two process routes, (2-3) and (4). They can produce the same manufacturing features. This means that we can choose either one, and the unselected one is not taken into account when creating a schedule. For example, If (4) is selected, then operation 2 and 3 become dummy operations. In the opposite case, operation 4 becomes a dummy operation.

Finally, we have to determine which machines and tools will process the operations. In <Figure 1(b)>, it shows the possible combination of alternative machines and tools which process the operation 4 of job 3. It also presents the processing times depending on the decisions. For example, if operation 4 is run on machine 3 using tool 8, it will take 14-time units to complete.

3.Proposed Genetic Algorithm

3.1.Overall GA Procedure

We adopt a traditional genetic algorithm procedure. <Figure 2> shows the procedure steps and the techniques used in this paper. At the initial population creation step, a certain number of individuals are generated using a circular queue that uniformly allocates the machine and tool to be processed on the operations in the individual. The next sub-section will illustrate the detailed explanation on it. Next, all individuals in the population are evaluated by a fitness function. Since the objective of our IPPS is to minimize the makespan, which is the completion time of all operations, decoding (scheduling in IPPS) has to be performed on each individual. We use a modified hybrid scheduling algorithm (MHS) that is a modification of Bierwirth and Mattfeld [3, 10]. Then, the GA checks the termination condition that is a fixed number of generations to be evolved. If the condition is passed, the algorithm performs the selection, crossover, and mutation operations sequentially on the population. As a result, the offspring replaces the parents, and the new generation starts. If the termination condition meets, the algorithm stops and the current best solution becomes the final solution.

3.2.Individual Representation

Due to the high flexibility, a simply structured chromosome representation for IPPS is not allowed. The traditional representation for IPPS [10, 15, 16, 17, 21], constructs separate representations for each required information. For example, the information on the machine allocation is stored in individual W, the information on the tool allocation is stored in individual X, the information on the execution order is stored in individual Y, and the information on the selected process route is stored in individual Z. Each of these does not represent a complete manufacturing plan. Only when the individuals W, X, Y, and Z are combined, a meaningful manufacturing plan can be obtained and evaluated. Moreover, the multiple types of individuals require multiple populations to be evolved, which results in a complicated GA procedure and a long calculation time.

To overcome these weaknesses and create a manageable representation for IPPS, we propose a permutation representation composed of entities that include all required information. To represent the integrated manufacturing plan as a single object, we created a new data structure, namely operation. Hereafter, the name of the new data structure will be italicized to distinguish those from the existing terms. The operation is composed of the following five attributes; job number, operation number, machine number, tool number, and processing time. For example, In <Figure 1(b)>, the operation 4 of the job 3, i.e., o₃₄, can be instantiated as an operation, as shown in <Figure 3(a)>, in which all attributes are assigned for scheduling.

<Figure 3(b)> shows a sample sequence of operations called as operation string and a sample array of process routes called as process string. Although the example shows only several selected operations, the complete individual must contain all the operations of whole jobs, including dummy operations that are not actually performed by OR relations. The operation string alone is not enough to make a complete individual because there is no information about which alternative process route is to be performed. The process string provides such information. It is an array of the numbers of the starting operations of the alternative sequences at each OR relation. The length of the process string is the sum of the number of OR relations in all jobs. For example, In <Figure 1(a)>, job 1 has just one OR relation having 2 alternative process routes ({2-3} and {4}), job 2 has 2 OR relations (the first one branches off to {1-2-3-4} and {5-6-7} and the second one branches off to {2} and {3}), and job 3 does not have any OR relations. Thus, the length of the process string is 3 and can be denoted as an array, e.g., [4, 5, 2] and [2, 1, 3].

3.3.Modified Hybrid Scheduling Algorithm

The individual composed of an operation string and a process string is not a final solution for IPPS. The individual must be decoded into a schedule with the information on the chromosome. An operation is schedulable only if its predecessors have been scheduled already. There are four types of schedule : semi-active, active, non-delay, and hybrid. It is well-known that the optimal schedule is an active schedule. Bierwirth and Mattfeld [3, 10] proposed a hybrid scheduling algorithm by modifying Giffler and Thompson [8], which can generate an active and non-delay schedule. In this paper, we adopted the scheduling algorithm, but partially modified it to consider dummy nodes. The detailed procedure is as follows and we follow notations of Kim et al. [10].

The design parameter θ determines the type of schedule, i.e., zero yields a non-delay schedule and one yields an active schedule. In our algorithm, we set θ as 0.5 which is known to be the best empirically by Kim et al. [10].

The MHS consumes much computing resources due to frequent search processes. To overcome it, we developed an index array which is a 2-dimentional array of indices of operation. Through this, we can find out where the specific operation is in the sequence without any search algorithm. For example, in <Figure 3(b)>, the index of o₃₄ is 3, so the third row and fourth column component of the index array is 3. That is, the index array is a lagged array which row number corresponds to the job number and column number corresponds to the operation number. Of course, the search process can be used without the index array, but the time complexity increases from O (1) to O (n) . It makes stark difference for such a complex problem.

3.4.Fitness Function

According to Petrovic et al. [21], makespan is the most popular objective function for IPPS. If the IPPS pursues multi-objectives, tardiness, workload, and machine utilization are considered further. In this paper, we choose the makespan as a single objective. Our IPPS problem considers the constraints on tool magazine capacity and tool capacity. Thus, although all precedence constraints are satisfied, it may result in an infeasible solution if the number of used tool types on a machine or the number of used tools on all machines exceeds the tool and tool magazine capacities, respectively. However, it is hard to check and repair the violation of those constraints during genetic operations. It consumes a long computation time and decreases exploitation capability. Therefore, we imposes an amount of penalty [10] for the violation of constraints as follows :

penalty = c 1 ∑ t T P ( t ) α + c 2 ∑ t M P ( m ) β

Here, tool penalty, TP (t) , denotes the excessive number of the specified usage of tool t. MP (m ) denotes the excessive number of the tool magazine capacity for machine m. Where c₁, c₁, α and β are parameters. At the end, the fitness of an individual becomes fitness = 1/(makespan+penalty).

3.5.Initial Population

IPPS with a large solution space should maintain a sufficient exploitation capability to derive an excellent optimal solution and to prevent premature convergence of the GA. The easiest way to solve this is to construct a large population. However, it causes a long calculation time and makes the GA’s efficiency worse. While generating an individual that belongs to the initial population, all attributes of operations must be assigned. Otherwise, a fitness evaluation of the individual is impossible. A typical random assignment for the attributes limits the solution space if the population size is small. For this reason, we propose a method that assigns the attributes evenly using circular queues when constructing the initial population. A circular queue consists of all combinations of possible resource assignments for each operation. For example, if o₃₄ is processed on machine 1 using tool 2, the combination of machine and tool can be denoted as a tuple, (1, 2). In <Figure 1(b)>, all the possible combinations can be listed as follows; (1, 2), (1, 5), (1, 7), (3, 1), (3, 2), (3, 8). The circular queue corresponding to o₃₄ are generated by shuffling the list arbitrarily. While generating an individual, one element is taking out from the circular queue of the operation and the machine, tool, and subsequent processing time of it is assigned into the operation. Then, the element is reinserted into the tail of the circular queue. By doing this, all resources can be distributed evenly. This helps to maintain a reasonable size of population without serious loss of solution quality. An operation string including dummy operations is generated by applying this process iteratively. Finally, the operation string is shuffled randomly. Since the proposed GA applies a sequence independent hybrid scheduling, precedence constraints need not be satisfied. The process string is also generated by arbitrarily selecting one of the starting operations of the alternative process routes on every OR relations.

3.6.Selection, Crossover, and Mutation

In GA, the selection operation is to select parents to perform the crossover and mutation operations. A typical binary tournament selection is to randomly pick up two individuals in the population and select the one with a higher fitness. According to GA’s philosophy of inheriting superior genes, the superior selection is appropriate. However, some recent studies on IPPS [24, 25] show that the inferior selection which selects an individual with lower fitness yields better results than the superior selection. It is because the inferior selection maintains exploitation capability and prevents premature convergence in IPPS with high complexity. We already applied the circular queue for the generation of the initial population for this purpose, but the inferior selection plays a role in supplementing it.<Figure 4>

Since the chromosome is combined by the operation string and the process string, a crossover and a mutation operation should be performed respectively. For the operation string, we adopt the well-known precedence preservative crossover (PPX) [3, 4]. The PPX is performed as follows.

As for mutation, we used a feasible insertion for the operation string. A selected operation is inserted at any position between the immediate preceding and succeeding operation.

In process string, we do not perform any crossover operation because there was no significant difference in preliminary tests. However, for mutation, we employed one point mutation for the process string, in which a randomly selected element is replaced arbitrarily by one of the alternatives.

4.Experimental Results

A series of experiments were performed on the benchmark problems proposed by Kim et al. [10]. <Table 1> shows the 31 problems with a total of 18 jobs (parts). <Table 2> shows the information of the tool magazine capacity on each machine (Mcapa.), tool capacity (Tcapa.), and the required number of slots to mount each tool on a tool magazine (Req. slots).

All experiments were performed 10 times for each problem. The population size was set to be 300 regardless of the problem. The termination condition is the number of generation, which is 300 generations for all problems. Also, we assigned the crossover rate as 0.6 and the mutation rate as 0.05 for all problems. For the calculation of fitness, values of 10, 10, 0.5 and 0.5 were used for c₁, c₂, α, and β similar to Kim et al. [10], respectively. The reason for it is to compare fairly the performance of our proposed algorithm. The proposed GA was implemented in Java and has been performed on an Intel i7-5700HQ 2.7 GHz CPU.

<Table 3> and <Figure 5> present the comparison of the results of the proposed algorithm with previous evolutionary algorithms. Here, HEA represents the hierarchical evolutionary algorithm [10] and AMSEA denotes the asymmetric multileveled symbiotic evolutionary algorithm [10]. In the table, the shortest makespans for each problem among the algorithms are shown in bold. The improved rate indicates the degree of improvement compared with the best makespan among HEA and AMSEA. The gray cell denotes improved solution.

The results show that our proposed algorithm (IGA), particularly inferior selection mechanism, is much better than those of HEA and AMSEA. Although direct comparison of computation time is impossible, the results are satisfactory under the given population size of 300 individuals and the termination condition of 300 generations.

5.Conclusion

In this paper, we proposed an improved genetic algorithm for IPPS with tool flexibility and tool related constraints. Experiments on the benchmark problems proved that the proposed GA is superior to the existing best algorithm. In a practical manufacturing environment, if the subsequent operation uses another machine, the loading and unloading times of the workpiece is essential. Additional setup time should also be considered if the orientation of the tool or workpiece changes on the same machine. The IPPS in this paper assumed that these times are included in the processing time. Future studies will cover more realistic IPPS by considering such times.