Sage Journals: Discover world-class research

Abstract

A new mathematical method and an optimization model are proposed in this study to solve the tool requirement and pre-scheduling optimization problems involved in the tool flow system of digital workshops. This model aims to minimize the system makespan under the constraint of the tool purchase cost. A double-layer genetic algorithm based on the heuristic algorithm is then developed. This algorithm not only combines the advantages but also avoids the weaknesses of the two algorithms. Finally, a case study is conducted to validate the effectiveness and superiority of the proposed algorithm and the tool-machine dual-resource pre-scheduling optimization model.

Keywords

Tool requirement pre-scheduling double-layer genetic algorithm heuristic algorithm optimization

Introduction

In manufacturing workshops, the impact of tools on productivity can reach up to 25%–30%. The machine cost and labor charges account for 20% and 38%, respectively, of the total manufacture cost.^1,2 Unreasonable tool allocation often leads to the following cases: 16% of the production scheduling becomes abnormal, 30%–60% of the inventory tools become out of control, mechanics spend 20% of their time finding the right tool, and supervisors spend 40%–80% of their time looking for tools or supplying them.^3,4 These situations imply that the problems caused by tools seriously affect the production efficiency. The waiting time for production and the time spent on finding the tools would naturally decrease if a manufacturing system was configured with adequate tools. However, the tool purchase cost would increase. Therefore, a rational tool requirement should be planned within the allowable range of funds, which includes the configuration of tools with rational types, specifications, and quantity, not only to ensure the tool performance and durability, shorten the job processing time, and increase the productivity, but also to reduce the tool and manufacturing costs and improve the production scheduling efficiency.⁵ Production scheduling is the core content and key technology of workshop production management.⁶ Tools and machines coexist and influence each other during the scheduling process, which indicates that limited tool resources pose constraints on machine operation and scheduling decisions.^7,8 The traditional production scheduling only considers machine resources and assumes that tool resources are unlimited. In contrast, a study on tool scheduling has shown that scheduling is limited to the tool itself, and the impact of the machine resources is disregarded.^9,10 Thus, the pre-scheduling optimization proposed in this study is actually a comprehensive scheduling based on tool and machine, which finishes the job processing sequence and processing time under the limited production resources, thereby ultimately making the established goals optimal.¹¹

Two main types of tool scheduling methods presently exist: “simulation + rule” heuristic scheduling and optimal scheduling.¹² The goal of the “simulation + rule” heuristic scheduling is to obtain a better scheduling solution in a relatively fast time, instead of obtaining the optimal solution. Therefore, its advantages include high efficiency, favorable real-time performance, and small cost. Buyurgan et al.¹³ proposed a heuristic algorithm for tool flexibility. This tool uses tool size/tool life as the evaluation criterion for allocating tools, but without considering the influence of the scheduling policy on tool planning. Kumar and Sridharan¹⁴ studied three types of tool assignment rules. They then analyzed and compared the performance of the production system without considering the tool failure, process delay, and other factors. In allusion to the problems of tool assignment, Özpeynirci and colleagues^15,16 considered maximizing the total weight as an optimization objective and established the mixed-integer linear programming model under the constraints of tool resources and tool storage capacity, which used branch and bound methods in problem solving. Accordingly, Zhang et al.¹⁷ built an optimal scheduling model under fixed tool resources, considering the tool exchange times as the optimization objective, which he solved by improving genetic algorithm. However, this model was only developed for the already determined tool resources. Zhao et al.¹⁸ built an integrated scheduling model for part flow and tool flow systems, whose optimization objective was to minimize the makespan through a double-layer genetic algorithm. However, the method only aimed at dynamic scheduling and ignored tool resource preparation and planning.

Currently, the research on tool requirement planning mainly focuses on the tool flow manufacturing system. Wang et al.¹⁹ proposed a tool requirement planning method for the tool flow system. They made use of the tool scheduling policy, which is not sensitive to the cycle time, through recursive algorithm to solve the cycle time and tool waiting time. They then added a critical tool to optimize the tool allocation until it reached the constraint of the tool purchase cost. Guanghui²⁰ proposed that a genetic algorithm can be used to solve the tool requirement planning problem of the flexible manufacturing system (FMS) under a specific job scheduling policy with the tool purchase cost as a constraint and minimizing the makespan as the goal.

In terms of the tool flow system, some literature proved that the tool scheduling policy is not the main factor affecting the task completion time. Therefore, the job scheduling policy for planning the tool requirement of a tool flow system was assumed in the existing literature, which only considered the effects of the tool resource allocation. However, present digital workshops generally have part flow systems of mass and small batch production. Therefore, this study focuses on the part flow system and proposes a new double-layer genetic algorithm based on the heuristic algorithm, which considers the tool requirement planning and dual-resource pre-scheduling. In indefinite tool resources (considering the tool purchase cost), various types of tools should be rationally allocated. In addition, under the constraint of a determined tool allocation, the operation sequence and the processing time must be finished to optimize the defined overall objective.

Problem description

In this article, “tool” refers to the metal-cutting tools used in machining. Configuring rational tool specifications and quantity and relating the processing sequence of each job to each machine and processing time to define the overall objective are the main problems addressed in this study considering the case of an uncertain tool resource allocation and the tool purchase cost. As we know, the production environment is dynamic and constrained by machines and tools as well as different release times for each job. The specific assumptions are set as follows to simplify the problem analysis and reflect on the actual situation inside the workshop:

The job-processing route and the operation (step) processing time are all definite and identified;

Each machine can only process one operation at a specific time;

Each tool can only process one operation on one machine at a specific time;

The computer numerical control (CNC) and general machines can shut down the reblading step;

The machine center cannot stop when a work is in progress;

Fault does not happen during the automated guided vehicle (AGV) car and tool manipulator operation;

Tool clamping, positioning, and other auxiliary times are included in the processing time;

Job transportation time is neglected;

Tool and machine work properly.

Mathematical model

Indices and parameter description

The following indices and parameters are introduced to describe multi-resource and target processing problems:

Indices

i = job index, if there are n types of job, $N = {1, \dots, n}$ ;

j = operation index, if there are n₁ operations, $N_{1} = {1, \dots, n_{1}}$ ;

o = step index, if there are n₂ steps, $N_{2} = {1, \dots, n_{2}}$ ;

k = machine index, if there are m machines, $M = {1, \dots, m}$ ;

t = tool index, if there are w types of tools, $W = {1, \dots, w}$ ;

Y = tool allocation, the number of various tool types;

E = various types of tool cost;

Z = total tool purchase cost.

Parameters

$O_{i j o k t}$ = step $o$ of operation $j$ under job $i$ using tool $t$ and processed by machine $k$ ;

$α_{k} (Y)$ = with the tool allocation $Y$ , the waiting tool time of machine $k$ during processing;

$β_{t} (Y)$ = with the tool allocation $Y$ , the processing waiting time caused by tool $t$ ;

$a_{i j o t}$ = when step $o$ of operation $j$ under job $i$ requires the use of tool $t$ , the value is 1, and 0, otherwise;

$b_{i j k}$ = when operation $j$ under job $i$ is processed on machine $k$ , the value is 1, and 0, otherwise;

$c_{k t}$ = when the tool exists on the machine, the value is 1, and 0, otherwise;

$T_{i j o k}$ = the processing time of step $o$ of operation $j$ under job $i$ and processed by machine $k$ ;

$D_{k}$ = tool storage capacity of machine k.

Objective function

The processing time for job $i$ under normal circumstances is provided as follows

\sum_{i = 1}^{n} \sum_{j = 1}^{n_{1}} \sum_{o = 1}^{n_{2}} T_{i j o k} b_{i j k}

(1a)

The waiting tool time of job $i$ is as follows

\sum_{i = 1}^{n} \sum_{j = 1}^{n_{1}} \sum_{o = 1}^{n_{2}} a_{i j o t} (1 - c_{k t}) α_{k} (Y) b_{i j k}

(1b)

The complete production time of job $i$ is given by the following equation

P = \sum_{i = 1}^{n} \sum_{j = 1}^{n_{1}} \sum_{o = 1}^{n_{2}} T_{i j o k} b_{i j k} + \sum_{i = 1}^{n} \sum_{j = 1}^{n_{1}} \sum_{o = 1}^{n_{2}} a_{i j o t} (1 - c_{k t}) α_{k} (Y) b_{i j k}

(1c)

The objective function-minimized production makespan is presented as follows

M i n (P_{\max})

(1d)

Constraint conditions

1. Each step of each job can be processed on a single machine using the following equation

\sum_{k = 1}^{m} b_{i j k} = 1

(1e)

2. The succeeding operation for one job starts after the preceding operation finishes

S_{i j k_{2}} ⩾ S_{i (j - 1) k_{1}} + R_{i (j - 1) k_{1}}

(1f)

where $S_{i j k}$ represents the start time of the ith job of operation j, which is processed on machine k; $R_{i j k}$ represents the total processing time of the ith job of operation j, which is processed on machine k; and $k_{1}, k_{2} \in M$ .

3. The tool stock restriction is determined as follows

\sum_{t = 1}^{w} c_{k t} ⩽ D_{k}

(1g)

4. The constraints on the decision variables are as follows

a_{i j o t} \in {0, 1}

(1h)

b_{i j k} \in {0, 1}

(1i)

c_{k t} \in {0, 1}

(1j)

5. The constraint on the tool purchase cost is determined as follows

\sum_{t = 1}^{w} E Y ⩽ Z

(1k)

Algorithm-solving process

The tool resource allocation herein was first made indefinite by combining the tool-machine dual-resource pre-scheduling with the tool requirement planning, and then solving for the optimal scheduling and the appropriate tool allocation using the double-layer genetic algorithm based on the heuristic algorithm, in which the outer optimization function aims at the indefinite tool resource allocation during the selection process to utilize the advantages of the heuristic algorithm. The inner optimization function aims at the dual-resource pre-scheduling problem based on the optimization result of the outer function. The overall objective function is to minimize the makespan. Figure 1 shows the flow diagram.

Figure 1.

Flow chart of the pre-scheduling problem solution.

The outer optimization function of the double-layer genetic algorithm is based on a heuristic algorithm

The outer layer optimization function of the double-layer genetic algorithm based on a heuristic algorithm was mainly used to solve the problem on the allocation of the rational tool resources and apply the algorithm to the inner-layer optimization function and obtain the optimal pre-scheduling scheme. The critical tools are then determined, and the number of critical tools is added using the heuristic algorithm. Finally, the tool resource allocation is updated and continuously optimized until the optimal solution is obtained and inherited by the next generation.

Encoding and decoding

A real number encoding method is adopted in this study for the tool resource allocation, in which the chromosome number of genes is equal to the total types of tools, and the value of each gene represents the number of the corresponding types of tools. For example, there are six types of tools, in which the number of the second and fourth types is 2 (Figure 2).

Figure 2.

Chromosome encoding of tools.

The value of each position gene was decoded by scanning the tool resource chromosome from left to right, which indicated that the corresponding tool was categorized and quantified. Table 1 shows the tool allocation corresponding to the chromosome-decoding process.

Table 1.

Chromosome decoding of tools.

Tool category	Tool number
$C_{1}$	$T_{1}$
$C_{2}$	$T_{2}$ , $T_{3}$
$C_{3}$	$T_{4}$
$C_{4}$	$T_{5}$ , $T_{6}$
$C_{5}$	$T_{7}$
$C_{6}$	$T_{8}$

The corresponding minimum makespan and the waiting time for all types of tools are easily obtained by constructing the tool allocation scheme as a known condition included in the inner layer function.

Initial population

The genetic algorithm is a population type of operation algorithm, in which a certain number of chromosomes can be generated after encoding the variables of the solution space to construct the initial population of the genetic algorithm.²¹ The static tool requirements need to be calculated for the input scheduling tasks considered in this article. A tool should then be added to each tool type. The initial population number is equal to the type of tools.

Chromosome selection and crossover

Selection is the process of selecting a strong individual from the population and including it in the new population. The optimal retention strategy is used, that is, keeping the best fit individual in the current population and passing their traits to the next generation. The most critical tool, which is the most needed by the system is then determined according to the formula, $K_{t} = β_{t} (Y)$ , thereby adding another one to the next generation.

The total number of tools for same-generation individuals is the same. Thus, the traditional crossover method is not available. A new method is designed in this study. The specific operation proceeded as follows: first, the differences between the parent chromosome and the other random individuals are identified, and the gene positions that have been added tools in the parent chromosome are determined (another individual is used if the individual is the same as the parent generation); the total number of tools are then randomly added to the other genes that do not certainly contain added tools; finally, the respective filial chromosomes are produced (Figure 3).

Figure 3.

Chromosome crossover.

Parent generations 1 and 2 yield sets [4, 4, 5, 4, 3] and [3, 3, 7, 4, 3], respectively. First, the difference between parent generations 1 and 2 is calculated, thereby generating a difference set of [1, 1, –2, 0, 0]. Second, a new set is randomly generated based on the difference sets, in which the number of elements is equal to “0” and the sum of the elements in the new set is equal to the positive elements. Third, the value of the new set is added to the corresponding parent gene position, where the value of the difference set is “0” and further increased to “1” at the left most difference set for “0,” which corresponds to the parent generation gene position. For example, filial generation 1 randomly generates set ${2, 0}$ . First, ${2, 0}$ is added to the parent 1 gene position, where “0” in the difference set corresponds to and the filial generation 1 is changed to [3, 3, 5, 6, 3]. Similarly, filial generation 2 is changed to [3, 3, 5, 5, 4]. The left most difference set for “0” corresponding to the gene position value is then increased by 1. The filial generation 1 set is [3, 3, 5, 7, 3], whereas the filial generation 2 set is [3, 3, 5, 5, 4]. The example not only guarantees the consistency of the total number of tools in the same generation but also ensures that the total number of tools in the filial generation has more 1 than the parent generation, and the crossover method is valid.

This new crossover method is an absolute new approach that can ensure that the total number of tools in the filial generation has more 1 than the parent generation. The method also satisfies the purport put forward by this study. The demand of the chromosome crossover cannot be realized if the crossover method of the traditional genetic algorithm (e.g. PMX, OX, and LOX), whose total number of tools in every generation is the same, is used.

Chromosome variation

The swap variation method in the outer-layer function chromosome variation is designed. In this method, two gene positions are randomly selected; 1 is then added on the left-side position; and the genes are swapped. This method guarantees that the total number of tools in the filial generation has more 1 than the parent generation (Figure 4).

Figure 4.

Chromosome variation in the parental and filial generations.

The chromosome of the parent generation is [4, 4, 5, 4, 3]. The third gene in the parent generation is increased to 1, and then exchanged with the fifth gene, which results in the filial generation [4, 4, 3, 4, 6].

Similarly, the chromosome variation of the traditional genetic algorithm is only selecting the gene positions and swapping them, which cannot realize the purpose of having the filial generation have more 1s than the parent generation. However, the new chromosome variation method designed in this study satisfied the requirements well, which ensures that the total number of tools in the filial generation has more 1s than the parent generation.

The inner optimization function of the double-layer genetic algorithms based on the heuristic algorithm

The inner optimization function, which is under the tool resource allocation of the outer optimization function, optimizes the tool-machine pre-scheduling and doubling of resources with the objective of minimizing the makespan.

Chromosome encoding

In this article, one chromosome represents one scheduling solution of the inner optimization function. Thus, the inner function also uses the real number encoding method. The chromosome is divided into three parts. The first part is the operation chromosome, which encodes for the operation determining the processing sequence of each operation. The second part is the machine chromosome, which encodes for the machine corresponding to the operation. The third part is the tool chromosome, which encodes for the tool usage information for each step. Considering the tool lifespan, tool cutting parameters, and other factors, taking the tools that can satisfy the processing time in just one grinding and can avoid production delay and quality problems caused by stopping is required to change the tools during processing.

The definite configuration of the tool resources $Y$ is provided to clearly explain the steps of the inner-layer genetic algorithm. Table 1 shows the tool resources with the arrangement of two jobs and five machines for processing. Table 2 presents the job-processing information.

Table 2.

Processing information.

Job	Operation	Processing resources and step information
$P_{1}$	$O_{11}$	$M_{2}$		–	–
		$O_{111}$ (40)	$O_{112}$ (10)	–	–
		$C_{1}$	$C_{3}$	–	–
	$O_{12}$	$M_{1}$		$M_{3}$
		$O_{121}$ (15)	$O_{122}$ (20)	$O_{121}$ (20)	$O_{122}$ (15)
		$C_{1}$	$C_{2}$	$C_{2}$	$C_{4}$
	$O_{13}$	$M_{3}$		$M_{1}$
		$O_{131}$ (10)	$O_{132}$ (15)	$O_{131}$ (15)	$O_{132}$ (10)
		$C_{1}$ or $C_{3}$	$C_{5}$	$C_{3}$	$C_{5}$ or $C_{6}$
$P_{2}$	$O_{21}$	$M_{5}$		–	–
		$O_{211}$ (20)	$O_{212}$ (10)	–	–
		$C_{1}$ or $C_{6}$	$C_{4}$	–	–
	$O_{22}$	$M_{4}$		–	—
		$O_{221}$ (15)	$O_{222}$ (15)	–	–
		$C_{4}$	$C_{6}$	–	–

This case contains five operations with a chromosome length of 15. The chromosome has three parts, namely, operation chromosome, machine chromosome, and tool chromosome. These parts represent the scheduling solution shown in Figure 5.

Figure 5.

Chromosome samples.

Chromosome decoding

The chromosome decodes from left to right starting with the operation, proceeding to the machine, and, finally, to the tool chromosome. The decoding processes are discussed as follows:

Decoding of the operation chromosome

The quantity of the genes in the operation chromosome is the same as that of the machine chromosome. Furthermore, each gene position uses a job number to decode from left to right. An appearing job sequence represents the processing sequence. The job appearing frequency indicates the quantity of operations. Figure 6 shows the decoding of the operation chromosome in this case.

Figure 6.

Operation chromosome decoding.

Decoding of the machine chromosome

The quantity of genes in the machine chromosome is equal to that of the operation gene. Moreover, the machine gene sequence is arranged by the operation processing sequence of each job. Every gene position represents an optional machine set $α_{ij}$ . The number of the gene position is equal to the machine number of the optional set. Figure 7 shows the decoding of the machine chromosome.

Figure 7.

Decoding of the machine chromosome.

Decoding of the cutting tool chromosome

The quantity of the tool gene position is consistent with the whole operations of jobs. The gene sequence is arranged by operations. Each gene position corresponds to a tool set for each step. The number of the gene position represents the tool number used by all steps. Figure 8 illustrates the decoding of the tool chromosome.

Figure 8.

Decoding of the tool chromosome.

A plan for the tool allocation and its corresponding scheduling scheme can be obtained according to the decoding of the operation, machine, and tool. Figure 9 shows the decoding of the chromosome.

Figure 9.

Chromosome decoding.

Initial population

First, a processing line is randomly selected, and the processing sequence of different jobs is randomly arranged for the operation encoding. Second, a processing machine is randomly selected for the machine encoding according to the set of operations of the optional machine. The tools whose lifespans do not satisfy the processing conditions are then eliminated from the optional tool set, and the tool numbers are set for tool encoding. Finally, the initial population is produced.

Chromosome selection and crossover

Chromosome selection still uses the optimal retention policy to enable the best-fit individuals to directly pass their traits to the next generation, which will not be destroyed by chromosome selection, crossover, and variation operations. As for the crossover, the chromosome is divided into three parts. The operation chromosome segment is cut using the IPOX crossover method. The machine and tool chromosome segments are cut using the multi-point crossover method.

For example, the tool chromosome segment is obtained through the same method used in the machine chromosome segment. The genes, where 0 corresponds to the gene position, are exchanged, and the genes, where 1 corresponds to the gene position, are retained by generating a set (Rand0-1) randomly composed by 0 and 1 and which is equal to the tool chromosomal segment gene number (Figure 10; $R a n d 0 - 1 = {0, 1, 1, 0, 0}$ ).

Figure 10.

Chromosome crossover operation of tools.

Chromosome variation

The variation in the operation chromosome requires the exchange variation method, which randomly selects two positions to exchange genes. The positions corresponding to the machine and the tool also need to exchange genes. The machine chromosome variation randomly selects a different machine in the machine set that corresponds to the operation, whereas the corresponding tool genes should follow the variation machine encoding for re-selected tools.

Experiment verification and result analysis

The following case verifies the planning for the tool requirement and the methods of the tool-machine dual-resource pre-scheduling based on a tool flow system in a digital workshop. The case data are as follows: four machines were used, including $M_{1}$ and $M_{2}$ , with two machining centers, $M_{3}$ and $M_{4}$ . A general accuracy machine tool was used. Four types of jobs were also considered, along with five types of tools with purchase costs of 100, 120, 150, 130, and 200. The total purchase cost was 1500. A simulation environment was created under MATLAB 7.1. The initial tool requirement was one for each type of tools. Table 3 shows the processing information, while Table 4 presents the setting for the genetic algorithm parameters.

Table 3.

Process information.

Job	Operation	Processing resources and step information
$P_{1}$	$O_{11}$	$M_{1}$		$M_{4}$
		$O_{111} (10)$	$O_{112} (12)$	$O_{111} (13)$	$O_{112} (15)$
		$L_{1}$	$L_{2}$	$L_{2}$	$L_{5}$
	$O_{12}$	$M_{2}$		$M_{3}$
		$O_{121} (24)$	$O_{122} (7)$	$O_{121} (10)$	$O_{122} (18)$
		$L_{3}$	$L_{4}$	$L_{1}$	$L_{3}$
	$O_{13}$	$M_{3}$		–
		$O_{131} (15)$	$O_{132} (25)$	–	–
		$L_{1} or L_{2}$	$L_{3}$	–	–
	$O_{14}$	$M_{4}$		–
		$O_{141} (26)$	$O_{142} (23)$	–	–
		$L_{4}$	$L_{2}$	–	–
$P_{2}$	$O_{21}$	$M_{3}$		$M_{1}$
		$O_{211} (10)$	$O_{212} (15)$	$O_{211} (10)$	$O_{212} (20)$
		$L_{1}$	$L_{2}$	$L_{3}$	$L_{2}$
	$O_{22}$	$M_{3}$		–
		$O_{221} (18)$	$O_{222} (15)$	–	–
		$L_{4}$	$L_{1}$	–	–
	$O_{23}$	$M_{2}$		–
		$O_{231} (27)$	$O_{232} (15)$	–	–
		$L_{2}$	$L_{3} or L_{4}$	–	–
$P_{3}$	$O_{31}$	$M_{4}$		$M_{3}$
		$O_{311} (23)$	$O_{312} (17)$	$O_{311} (18)$	$O_{312} (20)$
		$L_{1}$	$L_{3}$	$L_{2}$	$L_{4}$
	$O_{32}$	$M_{2}$		–
		$O_{321} (15)$	$O_{322} (20)$	–	–
		$L_{5}$	$L_{4}$	–	–
	$O_{33}$	$M_{3}$		$M_{1}$
		$O_{331} (13)$	$O_{332} (27)$	$O_{331} (15)$	$O_{332} (20)$
		$L_{2}$	$L_{3}$	$L_{3}$	$L_{1}$
$P_{4}$	$O_{41}$	$M_{4}$		–
		$O_{411} (12)$	$O_{412} (33)$	–	–
		$L_{3}$	$L_{1}$	–	–
	$O_{42}$	$M_{2}$		$M_{1}$
		$O_{421} (8)$	$O_{422} (32)$	$O_{421} (16)$	$O_{422} (20)$
		$L_{4}$	$L_{2}$	$L_{2}$	$L_{3}$
	$O_{43}$	$M_{1}$		–
		$O_{431} (25)$	$O_{432} (10)$	–	–
		$L_{1}$	$L_{3}$	–	–

Table 4.

Genetic algorithm’s basic parameters.

Number of individuals	Maximum hereditary algebra	Generation gap	Crossover probability	Variation probability
500	50	0.9	0.8	0.1

Table 5 presents the case-solving results, which shows that the waiting tool time and the makespan are different with different tool allocations. The critical tool section provides the critical tools under each allocation case. A continuous addition of the appropriate critical tools to the next generation is conducted according to the method proposed in this study until the optimal allocation of the tool requirement and the pre-scheduling scheme of the tool-machine dual-resource is determined. The sixth tool allocation is better than the seventh and eighth. Although their makespans are the same (i.e. 156), the sixth program has a lower cost. Therefore, the sixth program is the optimal scheme for this case, meaning three of $L_{1}$ , two of $L_{2}$ , two of $L_{3}$ , two of $L_{4}$ , and one of $L_{5}$ . The makespan is 156, and the tool purchase cost is 1300. Figures 11 and 12 illustrate the optimal pre-scheduling scheme of the tool-machine dual-resource.

Table 5.

Maximum completion time under different tool allocations.

No.	Tool allocation					Waiting tool time					Makespan	Critical tool	Tool cost
0	L ₁	L ₂	L ₃	L ₄	L ₅	L ₁	L ₂	L ₃	L ₄	L ₅	Makespan	Critical tool	Tool cost
1	1	1	1	1	1	41	13	43	69	18	226	L ₄	700
2	1	1	1	2	1	38	19	69	38	0	209	L ₃	830
3	1	1	2	2	1	58	31	0	13	0	189	L ₁	980
4	2	1	2	2	1	24	18	4	0	0	185	L ₁	1080
5	3	1	2	2	1	25	41	15	0	0	176	L ₂	1180
6	3	2	2	2	1	0	23	0	23	0	156	L ₂	1300
7	3	3	2	2	1	0	23	10	23	0	156	L ₂	1420
8	3	4	2	2	1	0	0	0	0	0	156	–	1540
9	Infinite	Infinite	Infinite	Infinite	Infinite	0	0	0	0	0	156	–	–

Figure 11.

Optimal pre-scheduling scheme.

Figure 12.

Usage of tools.

The case or data for the tool requirement or dual-resource pre-scheduling optimization in the tool flow system of digital workshops barely exist at the present. Therefore, there is no way to compare the results with any other cases. However, in Figure 13, the decrease of the average makespan over 10 runs for the sixth tool allocation program with four jobs, four machines, and five types of tools is drawn. Noting that the algorithm presented in this article improves the average makespan at a very fast speed is possible. Furthermore, the best makespan equal to 156 is reached after 10 generations and is optimal. With regard to the self-built case, although the scale is not too large or cannot better reflect the superiority of the proposed intelligent optimization algorithm, it can effectively and quickly obtain the optimal solution.

Figure 13.

Decrease of the makespan.

Conclusion

This study aimed to address the tool requirement and pre-scheduling optimization problems in the tool flow system of a digital workshop. Accordingly, an optimization model was initially built and a new intelligent optimization algorithm (i.e. a double-layer genetic algorithm based on a heuristic algorithm) was proposed for the tool requirement and pre-scheduling for the tool-machine dual-resource with the primary objective of minimizing the system makespan under the constraint of the tool purchase cost. A more complex flexible scheduling case was chosen to better verify the performance of the algorithm in dealing with large-scale and complex problems. An optimal allocation for the tool requirement and pre-scheduling scheme for the tool-machine dual-resource was obtained by utilizing the proposed algorithm. At the same time, the decrease of the makespan was drawn to prove that the algorithm can quickly and effectively obtain the optimal solution in a very short time as well as the effectiveness and superiority of the algorithm in dealing with large-scale and complex problems. The case study verified that the rational tool requirement plan and the pre-scheduling optimization model of the tool-machine dual-resource in the tool flow system of a digital workshop are effective.

Footnotes

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The research is supported by the National Natural Science Foundation of China (NSFC) under Grant No. 51205429, the Program for Innovative Research Team in University of Ministry of Education of China under Grant No.IRT_15R64, the Science and Technology Project of Chongqing under Grant No. cstc2014zktjccxyyBX0019, and the National Science and Technology Pillar Program during the 12th Five-year Plan Period of China under Grant No.2012BAF01B01.

References

Cao

Wang

Zhou

. Study on tool management based total life. Modul Mach Tool Automat Manuf Tech 2005; 10: 66–70.

Wang

Feng

. Research on tool assembly model and schedule simulation in FMS. J Syst Simul 2003; 15(9): 1211–1213.

Keung

Lee

. A genetic algorithm approach to the multiple machine tool selection problem. J Intell Manuf 2001; 12(4): 331–342.

. Research on flexible job shop dynamic scheduling problem. J Syst Simul 2008; 20(14): 3828–3832.

Wang

C-Y

W-S

Jun

. Optimization algorithm study for multiple-constrained and multiple-objective job-shop tool dynamic distribution. Appl Mech Mater 2014; 551: 612–616.

Liu

. A cross-entropy-based approach for joint process plan selection and scheduling optimization. Proc IMechE, Part B: J Engineering Manufacture 2016; 230: 1525–1536.

Rui

Shilong

Zhu

. An ant colony algorithm for job shop scheduling problem with tool flow. Proc IMechE, Part B: J Engineering Manufacture 2014; 228(8): 959–968.

Shen

Zhu

. Chance-constrained model for uncertain job shop scheduling problem. Soft Comput 2016; 20(6): 2383–2391.

Asadzadeh

Zamanifar

. An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Math Comput Model 2010; 52(11): 1957–1965.

10.

Jin

Zhang

Shao

. Mathematical modeling and a memetic algorithm for the integration of process planning and scheduling considering uncertain processing times. Proc IMechE, Part B: J Engineering Manufacture 2016; 32(32): 245–256.

11.

Chen

Frank Chen

. Adaptive scheduling and tool flow control in flexible job shops. Int J Prod Res 2008; 46(15): 4035–4059.

12.

Chen

Wang

. Research on dynamic scheduling technology in job shop with tool flow. Appl Mech Mater 2013; 313–314: 685–688

13.

Buyurgan

Saygin

Kilic

. Tool allocation in flexible manufacturing systems with tool alternatives. J Manuf Syst 2004; 20(4): 341–349.

14.

Kumar

Sridharan

. Simulation modeling and analysis of tool sharing and part scheduling decisions in single-stage multimachine flexible manufacturing systems. Robot Comput Integrated Manuf 2007; 23(4): 361–370.

15.

Özpeynirci

Azizoglu

. Bounding approaches for operation assignment and capacity allocation problem in flexible manufacturing systems. Comput Oper Res 2009; 36(9): 2531–2540.

16.

Özpeynirci

. A heuristic approach based on time-indexed modelling for scheduling and tool loading in flexible manufacturing systems. Int J Adv Manuf Tech 2015; 77(5–8): 1269–1274.

17.

Zhang

Peihuang

Wuru

. Application of an improved genetic algorithm for tool scheduling in FMS. Ind Control Comput 2009; 22(9): 75–78.

18.

Zhao

Zhang

J-T

Shu

. Double layer genetic algorithm for integrated scheduling optimization of part and tool flows. J Southwest JiaoTong Univ 2010; 45(6): 926–931.

19.

Wang

Feng

. Heuristic algorithm for tool requirements planning in flexible manufacturing system. J XI’AN JiaoTong Univ 2003; 37(12): 1259–1262.

20.

Guanghui

. Genetic algorithm of tools requirement in flexible manufacturing system. J WuHan Univ Technol (Inform Manage Eng) 2006; 28(6): 45–47.

21.

Onwubolu

. Manufacturing cell scheduling using genetic algorithms. Proc IMechE, Part B: J Engineering Manufacture 2000; 214(2): 159–163.

Tool requirement and pre-scheduling optimization model of the tool flow system of a digital workshop

Abstract

Keywords

Introduction

Problem description

Mathematical model

Indices and parameter description

Objective function

Algorithm-solving process

The outer optimization function of the double-layer genetic algorithm is based on a heuristic algorithm

Encoding and decoding

Initial population

Chromosome selection and crossover

Chromosome variation

The inner optimization function of the double-layer genetic algorithms based on the heuristic algorithm

Chromosome encoding

Chromosome decoding

Initial population

Chromosome selection and crossover

Chromosome variation

Experiment verification and result analysis

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References