Sage Journals: Discover world-class research

Abstract

As the most important core process in the dyeing and finishing workshop of knitting companies, the dyeing process has the characteristics of multi-variety, small-batch, parallel machine processing of multiple types, and high cost in equipment cleaning, which render the dyeing scheduling problem a bottleneck in the production management of a dyeing and finishing workshop. In this paper, the dyeing process scheduling problem in dyeing and finishing workshops is described and abstracted, and an optimized mathematical model of dyeing scheduling is constructed with the goal of minimizing the delay cost and switching cost. Constraints such as multiple types of equipment, equipment capacity, weights of orders and equipment cleaning time are considered. For the sub-problem of equipment scheduling in the dyeing scheduling problem, a heuristic rule that considers equipment utilization and order delay is proposed. For the sub-problem of order sorting of the equipment in the dyeing scheduling problem, a hybrid genetic algorithm with a variable neighbourhood search strategy has been designed to optimize sorting. The algorithm proposed in this paper has been demonstrated via case simulation to be effective in solving the scheduling problem in dyeing and finishing workshops.

Keywords

Knitting companies dyeing scheduling hybrid genetic algorithm smart production

Introduction

Knitting companies often include weaving workshops (in which the yarns (raw materials) are weaved into fabrics) and dyeing and finishing workshops (in which grey fabrics are dyed to colours required by customers). In the actual dyeing process of dyeing and finishing workshops in knitting companies, most companies use intermittent dyeing machines for production. This intermittent production mode consumes more than 98% of the water, dyes and auxiliary ingredients that the companies consume.^1,2 Therefore, if a scheduling programme is not rational, numerous resources will be wasted.^3,4 The dyeing programme has a decisive role in the production management process in dyeing and finishing workshops and is an important factor for reflecting the actual economic value and additional value of products. This programme directly determines whether customers’ orders can be delivered on time. If the scheduling programme is not rational, problems such as serious delays to orders, excessive resource consumption for equipment cleaning and unstable dyeing quality will occur. Currently, most companies employ manual production scheduling, which has disadvantages such as low scheduling efficiency and inaccurate time control. Therefore, improving the production efficiency and ensuring the dyeing quality of companies via rational scheduling of the dyeing process has significance.

The scheduling of dyeing and finishing workshops has the following characteristics: (1) The setup time (cleaning time) for the dyeing tank is related to the colours in the next task and the task that just finished. The setup time of the dyeing tank is related to the colours before and after the process. When the next dyeing task is to be conducted, a certain amount of time (setup time) is needed to drain and remove the dyes and chemicals that remain after the preceding dyeing batch of fabric materials. The difference in setup time depends on the colour switch between the product to be processed and the product that just finished processing. When the preceding task uses a light colour and the following task utilizes a dark colour, a relatively short time is required for cleaning the dyeing tank. Conversely, if the processed product is darker, and the following product is lighter, a longer cleaning time is required. Different processing sequences may produce different dye switching times and water costs. (2) The capacity of the dyeing tank has double limits of cloth weight and cloth length. To dye knitted fabric lace, both the maximum capacity of the dyeing tank and the minimum capacity of the dyeing tank should be considered from the perspectives of cost and resource utilization. Due to the special considerations for lace materials, the limit of the cloth length that can be dyed by the dyeing tank should also be considered. Dyeing workshops have many different types of dyeing tanks. Different types of equipment have differences in the types of products that can be processed, the maximum and minimum weight and longest cloth length that can be processed, and processing times and costs for dyeing different products. Multiple parallel pieces of equipment are of the same type and have the same capacity limit.

Dyeing scheduling problem

In the research of the scheduling problems of fabric dyeing, some problems have been solved, and some models have been proposed for the production planning and scheduling of fabric dyeing companies. Azadeh et al.⁵ integrated the computer simulation, goal programming and design of experiment (DOE) algorithms to solve workshop scheduling problems with multiple objectives for optimization. The proposed algorithm was applied to actual fabric dyeing workshops and achieved satisfactory results. Huynh and Chien⁶ proposed a multi-subpopulation genetic algorithm (GA) with heuristic embedded (MSGA-H) for studying scheduling of fabric batch dyeing. Zhang et al.⁷ proposed a multi-objective artificial bee colony algorithm for solving fabric dyeing scheduling problems and described the problems as a parallel batch processing machine scheduling model. The first objective function of the model reflected the delay cost, and the second objective function was aimed at the utilization of the dyeing tank. Hsu et al.⁸ proposed a problem for yarn dyeing scheduling, which involved multi-stage production, sequence-dependent setup time, hierarchical product structure and group delivery. Jiang et al.⁹ solved the scheduling of continuous dyeing processes and developed a GA to minimize the total cleaning time. Chen¹⁰ analysed the technological process of dip dyeing in the dyeing workshop of fabric companies and constructed a mathematical model of dip dyeing optimization based on batch processing, in which he applied the branch and bound method in the General Algebraic Modelling System (GAMS) to solve the model. However, in the actual modelling process, the cleaning time of the dyeing equipment was not considered, while the cleaning time and cleaning cost of the equipment are important factors that cannot be disregarded in dyeing scheduling problems.

Scheduling problem of batch processing machine

Domestic and foreign scholars have conducted a substantial amount of research on parallel batch processing machines and have achieved substantial results.^11,12 Foreign scholars Pinto and Grossmann were the first scholars to address the problem of batch processing. They proposed a continuous time scheduling model based on time slots to solve this problem after they investigated the batch processing of multiple processes and multiple products.¹³ Jia et al.¹⁴ proposed a metaheuristic algorithm based on the maximum and minimum ant system method and considers scheduling n jobs of arbitrary size using a set of m identical and parallel batch processing machines with the aim of minimizing the makespan. Kashan et al.¹⁵ explored the problem of scheduling jobs of different sizes with a single batch processing machine. A batch processing machine can simultaneously process multiple jobs as long as the total number of jobs to be processed does not exceed the capacity of the machine. The batch processing time is equal to the longest processing time in all jobs in a batch. Two different types of multi-objective GAs that consider the two aims of minimizing makespan and minimizing maximum delay were proposed. To address the delay time and makespan, Li et al.¹⁶ proposed an ant colony optimization (ACO) algorithm that considers the batch processing machine scheduling problems with constraints such as incompatible job group, dynamic job makespan, and sequence-related setup time. Abedi et al.¹⁷ proposed a new bi-objective mixed integer linear scheduling model for parallel batch processing machines that considers constraints such as an arbitrary job size, different job time and capacity limitations. The goal was to minimize the makespan and total weighted early and delay time. They proposed a fast non-dominated sorting genetic algorithm (NSGA-II) and a multi-objective imperialist competition algorithm (MOICA) to determine the optimal solution to the problem. Shahvari et al.¹⁸ proposed a tabu search algorithm for solving batch scheduling problems that consider dynamic job posting, upper and lower batch size limits, and unrelated parallel machines. Bilyk et al.¹⁹ proposed two metaheuristic methods – variable neighbourhood search (VNS) and greedy randomized adaptive search procedure (GRASP) – for solving batch machine scheduling problems that consider the workpiece arrival time and sequence constraints. Shen et al.²⁰ designed a VNS algorithm to solve parallel machine scheduling problems and minimize the total completion time that considers the setup time between two groups of workpieces based on their sequence relations. However, most batch processing machine scheduling problems did not consider multiple types of equipment, which have different constraints of upper and lower capacities. These constraints must be considered in the dyeing and finishing workshops of knitting companies.

Application of GA to scheduling problems

GAs are extensively applied to solve many optimization problems, including scheduling problems, due to their evolutionary performance of parallel search. Alper et al.²¹ proposed a hybrid algorithm that combines a GA and VNS for the flexible workshop scheduling problem to reduce the total delay time. Huang et al.²² utilized a hybrid algorithm that combines a GA and simulated annealing and considers transportation time to solve the multi-objective flexible workshop scheduling problem. They also utilized an external elitism memory library as a knowledge library to guide searches that use a GA into the region of better performance. Moghadam et al.²³ developed an improved hybrid GA to reduce the maximum completion time of a pipe spool fabrication shop and designed an operation order-based global selection, which considered the processing time and workload of the machines when orders were allocated to the machines. Offspring and mutation operators were generated for sorting and job routing sub-problems by priority-based swapping, even swap, swapping operators and intelligent mutation operators. Kurdi²⁴ proposed a new type of island model GA for the workshop scheduling problem with the goal of minimizing the manufacturing cycle. They proposed a new natural heuristic evolution model and natural heuristic migration selection mechanism to improve the search diversity and delay premature convergence. Fu et al.²⁵ investigated parallel machine scheduling with dynamic resource allocation; proposed a strategy mainly via a GA to determine workpiece allocation, workpiece sequence and resource allocation; and designed a greedy heuristic rule to determine the start time of a workpiece. Li et al.²⁶ established an integrated mathematical model of production planning and scheduling and designed a method based on an evolutionary algorithm to achieve the integration and optimization of production planning and scheduling. They also developed effective genetic representation and operators to improve the optimization performance of the method.

Most literature about dyeing scheduling problems assumed that job tasks can be dyed in all equipment. The specialty of equipment for certain dyeing jobs was not considered. The equipment cleaning time and cost between two jobs using different colours are also constraints that cannot be disregarded in dyeing and finishing workshop scheduling. In dyeing and finishing workshop scheduling, the set of processable equipment of the job needs to be considered and reasonable job sorting should be conducted to reduce the cleaning time and cost caused by different job sorting tasks for low-carbon green produce. In most batch processor scheduling research, different types of equipment and equipment capacity constraints were not considered. Although equipment capacity has been considered in some studies, the maximum capacity was employed as the equipment capacity, which does not sufficiently reflect the characteristics of scheduling operations in an actual workshop. When allocating dyeing equipment jobs, the upper and lower limits of the equipment capacity should be considered to improve the utilization efficiency of equipment. In most studies that applied GAs to solve scheduling problems, job completion time was set as the goal, and GAs and other search algorithms or rules were combined to use hybrid GAs to solve the problem. In dyeing and finishing workshop scheduling, the on-time delivery goal of an order must be considered at once; otherwise, it will affect the production of garments and delay the opportunities of the clothing market. Therefore, this paper focuses on two optimization goals: delay time of the orders and cost of equipment cleaning between two jobs with full consideration of constraint factors such as the upper and lower capacities of multiple types of parallel equipment, specific processing operations, and dye switching between two jobs. To address the dyeing scheduling problem of a dyeing and finishing workshop, a dyeing scheduling algorithm based on a hybrid GA is designed to solve the problem of allocation and sorting of dyeing jobs.

Establishing a scheduling model of dyeing workshop

Problem definition

The process route of knitted fabrics throughout dyeing and finishing workshops is shown in Figure 1. Fabrics are completed by a pre-treatment process, dyeing process and post-finishing process. Among them, pre-treatment and post-finishing processes are auxiliary to the dyeing process; they use assembly lines with simple processing procedures. The dyeing process is a key process in the production of knitted fabrics that involves working with multiple different types of dyeing equipment. A rational scheduling and controlling of the dyeing process has a decisive role in scheduling the preceding fabric weaving process and timely delivery of subsequent garment processing.

Figure 1.

Product processing route.

The scheduling challenge of a knitted fabric dyeing workshop can be described as follows: the dyeing workshop is equipped with m dyeing tanks; each tank has different capacities and was divided into k equipment groups according to the machine type. In a scheduling period, there are n orders with different dyeing requirements. The product weight, dyeing parameters and delivery time are known. Some specific products need to be dyed in a specified type of equipment. Different products of the same colour can be dyed in the same equipment with the condition of not exceeding the dyeing tank capacity to achieve the same dyeing time. The main goals of dyeing scheduling are to rationally arrange tasks for multiple orders with different dyeing requirements of multiple dyeing equipment of different types for production and to determine the processing sequence of each order for the equipment to achieve minimal delay cost and production cost of all products.

Constraint conditions

Based on basic information, such as the equipment capacity and production requirement, the following assumptions are proposed to facilitate this study:

All equipment is idle at the beginning of scheduling;

The inventory of grey clothes is sufficient and satisfies the order requirements for production;

Except for specific products, dyeing equipment can dye all products in the order, but there are different dyeing capacities;

The order production time and the dye switching time (tank cleaning time) of different products are assumed to be known;

At the start of dyeing, the dyeing formulae for the orders are confirmed;

Each production order contains only one product, and two kinds of products are never dyed in one tank at the same time;

When the product quantity in an order exceeds the maximum capacity of the equipment, apply the equal batching principle;

The production process is not interrupted.

Symbol definition

For the convenience of description, variable symbols are designed for the mathematical model. Currently, $n$ orders of products to be scheduled are set. The order set is $I = {1, 2, \dots, i, \dots, n}$ . $D_{i}$ is the delivery time of order $i$ . $N_{i}$ is the product weight requested by order $i$ . $φ_{i}$ is the number of batches for the product in order i. $cTyp e_{i}$ is the colour series of the product in order $i$ . $D P_{i}$ is the colour shade value of the product in order $i$ . The colours are divided into nine colour series: white, black, blue, skin colour, green, orange, yellow, purple and red, with value ${1, 2, \dots, 9, 10}$ for $cTyp e_{i}$ . The colour shade value of each colour series ranges between 0 and 100. $δ_{1}$ is the task switching coefficient of the same colour series. $δ_{2}$ is the task switching coefficient of different colour series. $LE V_{i}$ is the level of the customer of order $i$ . $β$ is the weight coefficient of the customer. $w t_{i}$ is the gramme weight of the product of order $i$ , and $w d_{i}$ is the fabric width of the product of order $i$ . The equipment set is $J = {1, 2, \dots, j, \dots, m}$ . $U_{j}^{\min}$ is the minimum capacity of equipment $j$ , and $U_{j}^{\max}$ is the maximum capacity of equipment $j$ . $G_{j}$ is the number of fabric transfer ducts in equipment $j$ . $L_{j}^{\max}$ is the maximum fabric length allowed by the dyeing tank. $T S_{ij}$ is the time when order $i$ starts on equipment $j$ , and $T E_{ij}$ is the time when order $i$ finishes dyeing on equipment $j$ . $t A_{ij}$ is the time of the products in order $i$ that are dyed with equipment $j . t C_{ii' j}$ is the cleaning time needed to switch from order $i$ to order $i'$ with equipment $j$ . $CCOS T_{ii' j}$ is the cleaning cost spent on switching from order $i$ to order $i'$ for equipment $j$ . $DCOS T_{i}$ is the delay cost of order $i$ . $X_{ij}$ is a variable with the value of 1 if order $i$ is processed using equipment $j$ ; otherwise, the value is 0.

Mathematical model

The optimization goals of this study are to control the order completion time within the delivery deadline and to minimize the number of tank switching and cleaning during the production process to reduce the cost of equipment cleaning. Therefore, the two objective functions of this study are minimizing the cleaning costs and the delay costs

f_{1} = \min (\sum_{i \in I, i' \in I, j \in J} CCOS T_{ii' j})

(1)

f_{2} = \min (\sum_{i \in I} DCOS T_{i})

(2)

s . t . \sum_{i \in I} \sum_{j \in J} X_{i j} = 1

(3)

X_{ij} U_{j}^{\min} \leq \frac{N_{i}}{φ_{i}} \leq X_{ij} U_{j}^{\max} i \in I, j \in J

(4)

\frac{\frac{N_{i}}{φ_{i}}}{w d_{i} \times w t_{i} \times G_{j}} \leq L_{j}^{\max} i \in I, j \in J

(5)

T S_{ij} + φ_{i} \times t A_{ij} \leq T E_{ij} i \in I, j \in J

(6)

T E_{ij} + t C_{ii' j} \leq T S_{i' j} i, i' \in I, j \in J

(7)

\begin{matrix} CCOS T_{ii' j} = δ_{1} (D P_{i} - D P_{i'}) i \neq i', cTyp e_{i} \\ = cTyp e_{i'} D P_{i} > D P_{i'} \end{matrix}

(8)

CCOS T_{ii' j} = δ_{2} (D P_{i}) i \neq i', cTyp e_{i} \neq cTyp e_{i'},

(9)

DCOS T_{i} = β (\max (T E_{ij} - D_{i}, 0)) i \in I, j \in J, β > 0

(10)

where formula (3) expresses the allocation constraints; formula (4) expresses that the equally divided batch size of the order cannot exceed the equipment capacity; formula (5) expresses that the equally divided batch of the order must not exceed the fabric length constraint of the equipment; formula (6) expresses the order processing time constraints; formula (7) expresses that the start time of the next order should be the after processing completion time of the preceding order plus the switching time; formulae (8) and (9) express the switching costs, where formula (8) indicates the switching cost of orders for the same colour series and formula (9) gives the calculation of switching costs of orders in a different colour series; and formula (10) expresses the calculation of delay costs.

Formula (1) expresses minimization of the switching costs, and formula (2) expresses minimization of delay costs. This article uses linear weighting to aggregate the two objective functions into a single objective function, as shown as formula (11)

F = ε_{1} \frac{f_{1}}{avg (f_{1})} + ε_{2} \frac{f_{2}}{avg (f_{2})}

(11)

where $ε_{1}$ is the weight coefficient of $f_{1}$ , and $ε_{2}$ is the weight coefficient of $f_{2}$ .

Design of dyeing scheduling method based on hybrid GA

The dyeing scheduling problem in a dyeing and finishing workshop is a typical scheduling problem of multi-type parallel machine batch processing. This problem mainly consists of two sub-problems: equipment selection of order tasks and task sorting with the equipment. This paper designs a scheduling algorithm based on a hybrid GA for solving the two sub-problems. First, initial sets that utilize heuristic rules and random allocation rules are generated to complete equipment allocation for order tasks. Second, the tasks with the equipment are sorted and optimized using the VNS algorithm, and each chromosome is calculated for the switching costs and delay costs incurred by it as the fitness values. The overall flow of the algorithm is exhibited in Figure 2.

Figure 2.

Flowchart of the hybrid GA.

Task allocation based on heuristic rules

Considering the characteristics of dyeing production in the dyeing and finishing workshop and constraints such as the order size and the number of products in the orders that can be processed by equipment, heuristic rules are designed for the dyeing equipment allocation that can fulfil the requirements. A detailed description of the rules is presented as follows:

Rule 1: Tasks of the same colour series in the scheduled order task are considered. The equipment allocated by tasks of the same colour series is eliminated. Whether the $U_{j}^{\max} / N_{i}$ value of the new task allocated to this equipment is greater than 1 is calculated. The task is allocated to this equipment if the value is greater than 1. The advantage of this step is that orders of the same colour series are arranged in the same dyeing tank equipment for production, which reduces the cleaning cost caused by order switching.

Rule 2: The equipment with the shortest delay time, maximum equipment utilization, and smallest task volume is selected. This approach is conducive to improving the equipment utilization and reducing order delays.

The detailed allocation steps of the order tasks based on the heuristic rules are described as follows:

Step 1: The order tasks are sorted according to the urgency of the delivery time. If the delivery time is the same, the orders are randomly sorted. The original task set is sorted to form the new pending task set WaitP. The initial position $k = 0$ ; the processing task sequence set of equipment j is $π (j) = Ø$ ; and the scheduled task set is $P = Ø$ .

Step 2: The order task i at position k is removed from the task set WaitP. If there are tasks of the same colour series in the scheduled order task set P, rule 1 is invoked to select the equipment for task i and add the task to the processing sequence $π (j)$ of equipment j and $π (j) = π (j) + i$ . The current task volume of the selected equipment is updated: $Tas k_{j} = Tas k_{j} + N_{i}$ . Task i is deleted from WaitP and added to set P. Step 7 is referred.

Step 3: Invoking Rule 2, the available processing equipment set is selected. Among all of the equipment in the workshop, according to the quantity requirements of order i and capacity requirements of the dyeing tank, all equipment that can process order i are selected to form the set $Array_M 1$ .

Step 4: The completion time is calculated for each equipment inserted into the order array i in $Array_M 1$ , and the delay time of order i is calculated.

Step 5: The equipment set $Array_M 2$ that causes the least delay time is selected. If there are multiple types of equipment in $Array_M 2$ , the equipment set $Array_M 3$ with $U_{j}^{\max} / N_{i}$ greater than 1 is selected. If there is no equipment with $U_{j}^{\max} / N_{i}$ greater than 1, then $φ_{i} = [N_{i} / U_{j}^{\max}] + 1$ , the equipment set $Array_M 3$ with $U_{j}^{\max} / (N_{i} / φ_{i})$ greater than 1 is selected.

Step 6: Equipment j with the smallest volume of tasks is selected in $Array_M 3$ . If the volume of tasks is the same, the equipment number j is randomly selected; thus, the equipment selection of order i is completed. The task is added to the processing sequence $π (j)$ of equipment j, where $π (j) = π (j) + i$ . The current task volume of the selected equipment is updated: $Tas k_{j} = Tas k_{j} + N_{i}$ . Task i is deleted from set WaitP and added to set P.

Step 7: If WaitP is not empty, steps 2–6 are repeated. Otherwise, the equipment selection for the tasks in all orders is ended and completed.

Task sorting based on hybrid GA

Individual coding design

Double-layer coding is adopted. The upper layer is the order code, and the lower layer is the equipment code. The order and equipment are coded in natural numbers. The auxiliary code of the equipment is 1-M. The processing sequence of the tasks for the same equipment follows the sequence of the upper order sequence. The chromosome code is shown in Figure 3.

Figure 3.

Design of chromosome coding.

Population initialization

The heuristic rule allocation method designed in ‘Problem definition’ section is employed to generate chromosomes. The initial population is set to $popsize$ . This operation is repeated $popsize$ times to complete the population initialization.

Fitness function and population selection

The calculation of the fitness function adopts formula (11) to calculate the total cost value of each chromosome C, which is stored in the fitness value set of the current population $array_Fitness$ . The population selection operation adopts the classic roulette method to select an individual chromosome in the population set. First, the selection probability of individuals in the population is calculated. Second, a certain chromosome within the probability range is selected to be inherited into the next-generation population. To increase the convergence rate of the algorithm, the elite individual preservation method is adopted. The superior portion of individuals in each generation of every population is directly inherited into the next-generation population to become individuals, which increases the pressure on the selection of the parent population and increases the probability that the superior chromosomes are selected.

Crossover and mutation

Due to the specialty of chromosome coding in this paper, if the traditional crossover method is adopted, infeasible chromosomes may be produced. Therefore, the EOX crossover method is adopted as follows: A section of chromosome X is randomly cut out in parent chromosome 2. By comparing the first line of parent chromosome 1 with the first line of chromosome X, the same genes are deleted from parent chromosome 1. X is inserted into the first position of the deleted genes in chromosome 1, followed by the other genes, to obtain the new offspring chromosome 1′. This operation is also performed on chromosome 2 to obtain the offspring chromosome 2′. The crossover operation is shown in Figure 4.

Figure 4.

Crossover operation.

The mutation operation discussed in this paper is aimed at the single-point mutation of the equipment performed on the second layer of the chromosomes. The mutation position of the chromosome is randomly selected, and the equipment code is changed to any equipment in the task equipment set. The feasibility of the chromosome is determined after the mutation. If it is not feasible, the mutation operation is repeated.

Local search strategy

To enhance the local search ability of the GA and optimize the sorting, a VNS algorithm is employed as a local search strategy to optimize the sorting sub-problems in the dyeing scheduling. The main purpose of the algorithm is to design a suitable optimal solution to search the neighbourhood to obtain the superior individuals in a local range. According to the structural characteristics of the chromosomes, this paper utilizes three neighbourhood structures for VNS.

Swap structure

A two-point swap operation is performed on the chromosomes. The two positions of genes in the chromosome length generated by a random function are swapped. For example, if the upper chromosome is ‘186597324’ and the positions ‘2’ and ‘5’ are randomly generated, the upper chromosome after the neighbourhood structure swapping is ‘196587324’.

Front structure insertion

The front structure insertion is an insertion operation based on the crossover method. For each chromosome, the randomly generated positions of two genes are pos1 and pos2. Setting pos2 > pos1, the gene at position pos2 in the chromosome is removed and placed before position pos1. Thus, the previous position of pos1 and genes after it are postponed to form a new chromosome.

Heuristic structure

The heuristic structure is a neighbourhood structure based on heuristic thinking. The orders in each dyeing tank equipment are sorted to obtain the optimal solution in this neighbourhood. The detailed steps are listed as follows:

Step 1: For the optimal chromosome X, the gene position Pos is randomly generated to obtain the lower-layer coding gene a of this gene, which gives the equipment coding.

Step 2: All lower-layer genes that are coded as a are removed to form the gene set g_Array. The number of genes in set g_Array is defined as Count, and a gene is randomly selected in g_Array.

Step 3: The gene selected in step 2 is removed and inserted into each index position in set g_Array to form multiple sets. The genes in the sets are re-inserted in the original chromosomes according to their original position to form the Count 1 number of chromosomes. The fitness values of each newly formed chromosome are calculated, and the chromosome that corresponds to the smallest fitness value is taken as the new chromosome X1. For example, a gene set with a lower-layer gene of 3 is ‘3267’, position 2 is randomly generated, three positions can be inserted, and the possible new sets are ‘2367’, ‘3627’ and ‘3672’. The genes in the sets are re-inserted into the original chromosomes at their corresponding positions to form three new chromosomes, and the fitness value is calculated.

Test cases and analysis

Test data

Assume that the dyeing and finishing workshop of the company has nine dyeing machines and 42 orders. The basic equipment information is shown in Table 1. The detailed order information is shown in Table 2. The order delivery time is expressed in hours. For other parameters, the customer weight coefficients are divided into the four levels A, B, C and D, which correspond to coefficients of 2, 1.8, 1.6 and 1.2, respectively. The product processing time in the order satisfies $U [3, 7]$ ; the weight of the product satisfies $U [100, 200]$ ; the product width satisfies $U [100, 250]$ ; the switching time of the ordered product satisfies $U [1, 3]$ ; the switching coefficients for different colour series and the same colour series are 0.9 and 0.7, respectively; and the colour depth value satisfies $U [0, 100]$ .

Table 1.

Equipment information in the workshop.

Equipment code(equipment type)	Quantity(piece)	Minimumcapacity (kg)	Maximumcapacity (kg)	Number of fabric transferducts	Number
A (100 kg)	2	40	70	1	01/02
B (150 kg)	2	70	100	1	01/02
C (250 kg)	3	100	200	2	01/02/03
D (500 kg)	2	200	400	4	01/02

Table 2.

Order information.

Job number	Product ID	Customer level	Product quantity (kg)	Product colour	Delivery time (h)
1	AB74428/037	A	56	Raw white	13
2	MB75972/230/S	B	63	Normal white	8
3	A73380/029	A	60	55 light green	12
4	XJB75973/070/M	D	62	80 green	15
5	MB75966/230	D	65	Black	25
6	XHB75977/180/M	C	50	Pink	8
7	HB73681/220/S/B	D	70	Normal black	35
8	QB75951/230/P	D	60	34 PINK	15
9	H74976/190	B	57	Red glacier	30
10	BB74997/063	B	84	Silver	8
11	MB74356/230/S	A	75	GEM15 dark green	26
12	GB75493/230/P/S	C	460	Dark blue	45
13	BB74325/055	B	174	Slate grey	20
14	A70121/035	A	162	Dragon skin colour	15
15	HB74804/068/R/L	A	85	Plum	30
16	J70722/024	B	90	50 Melon red	30
17	J70722/024	C	75	Normal white	12
18	A75674/024	C	156	05083 denim blue	38
19	AB73734/015	A	82	Off-white	15
20	A73887/010	D	184	SQ Frost grey	30
21	J71332/026	B	138	LC7515 purple	40
22	JB75392/070	A	135	PASTE	10
23	B71067/094/A	B	86	Coffee	12
24	JB75392/070	D	82	Coffee	17
25	BB74997/063	B	128	Blue Gem 57M1	25
26	QB73728/230/R/S	B	136	IMPERIAL BLUE	25
27	A70169/014	C	268	PETAL PINK	18
28	A70303/057	B	335	Purple	40
29	MB74707/230/P	C	152	Silver	9
30	GB75383/230	A	140	Normal white	8
31	A70303/080	A	87	Light beige	9
32	A74992/025	A	180	Pink	12
33	JB75392/070	C	150	Green	30
34	EB75170/030/M	A	160	50 green	30
35	VLB75376/230/S	D	170	Black	35
36	BB74864/025	B	125	Fresh White	12
37	A70674/121/M	A	220	Rose red	20
38	A70169/014	A	250	Dark red	23
39	A70005/060/A	B	354	Dark purple	40
40	P75923/240/S	C	265	Light beige	9
41	P75923/240/S	D	312	Black	15
42	HB75745/230	B	320	BK8350B black	34

Comparison and analysis of the simulation results

The initial population size $popsize$ of the algorithm is 100; the crossover probability of the algorithm $pcross$ is 0.8; the mutation rate $pmutation$ is 0.03; the number of iterations $maxgen$ is 200 times; and the number of VNS $vnsgen$ is 100 times, which are set according to reference.²⁷

Initial solution comparison experiment

To verify the influence of the heuristic rules proposed in this paper on the initial solution, 42 actual cases of orders have been tested, and the advantages and disadvantages of the initial solutions generated by the heuristic rules and random rules have been compared. Twenty experiments have been conducted to calculate and record the mean values of the solution of the initial population by the two methods. A detailed data comparison is shown in Figure 5. As shown in Figure 6, the mean value of the initial solution generated by the heuristic algorithm is optimal at 152.07 and the mean value of the initial solution generated by the random initial population is optimal at 315.29, which fully demonstrates that the heuristic rules proposed in this paper are conducive to the initial population generation.

Figure 5.

Initial solution comparison chart.

Figure 6.

Convergence curve of mean values of different sorting methods.

Comparative test of equipment allocation methods of jobs

To verify the impact of the sorting methods of the pending task set on the population iterative process of the GA during the equipment allocation of tasks, the following three methods for sorting the pending task set were experimented in this paper.

Random sorting method

The order of the tasks in the pending task set is randomized to form a new set.

Sorting method of delivery time

The tasks in the set of pending tasks are sorted according to the delivery date. First, the tasks with urgent delivery dates are allocated with equipment, and tasks with the same delivery date are randomly sorted.

Colour series grouping and sorting method

The tasks in the pending order set are grouped by colour series, and the tasks in each group are sorted by the delivery date. If the delivery dates are the same, the tasks are sorted according to colour from dark to light. Each group of tasks is placed in sequence in the set to form a new task set.

The exemplary algorithm that was presented is provided as an example; 20 experiments are performed for each task sorting method; and the 20 iteration curves obtained by each method are averaged to obtain the comparative iteration curve in Figure 6. The data in the figure reveal that this paper utilizes the sorting of the initial set of pending tasks according to the delivery date order, followed by execution of the hybrid GA. The obtained method – sorting by weight of average solution – is superior to the two methods of sorting randomly and sorting by groups, which demonstrates that scheduling production according to the delivery date, which is selected in this paper, has a better impact on the population iterative process.

Comparison of simulation and experiments

To verify the performance of the algorithm in this paper, this paper tests two case sizes, $3 \times 4 \times 20$ and $4 \times 9 \times 42$ , where the first number represents the number of equipment types, the second number represents the number of equipment, and the third number represents the number of orders. Twenty tests are performed for each size, and the results of the $GAVNS$ algorithm proposed in this paper were compared with those obtained by the GA of the random initial population, the improved GA with heuristic rule (IGA) and the improved $HA$ .²⁸ The comparison results are shown in Tables 3 and 4. The data in the table indicate that the optimal solution value and mean value obtained by the hybrid GA proposed in this paper are better than those obtained by the GA, IGA and improved $HA$ . The optimization effect is also more obvious.

Table 3.

The $3 \times 4 \times 20$ case result comparison.

Algorithm	Optimized value	Mean value	Time (s)
HA	41.936	46.177	/
GA	22.125	36.355	4.59
IGA	12.902	23.318	6.37
GAVNS	5.05	9.07	19.84

HA: heuristic algorithm; GA: genetic algorithm; IGA: improved genetic algorithm with heuristic rule; GAVNS: genetic algorithm with variable neighbourhood search.

Table 4.

The $4 \times 9 \times 42$ case result comparison.

Algorithm	Optimized value	Mean value	Time (s)
HA	88.717	124.26	/
GA	67.039	80.045	11.59
IGA	31.168	50.625	21.7
GAVNS	11.241	20.273	44.37

HA: heuristic algorithm; GA: genetic algorithm; IGA: improved genetic algorithm with heuristic rule; GAVNS: genetic algorithm with variable neighbourhood search.

Figure 7 shows a Gantt chart of the scheduling results of case $4 \times 9 \times 42$ . The times of switching for cleaning is small in the scheduling strategy, and the total number of delayed orders is 3, which has an obvious optimizing effect on the cleaning cost and delay cost. Figure 8 shows the convergence curves of the algorithms.

Figure 7.

Gantt chart of scheduling results.

Figure 8.

Population iteration curve.

Conclusion

This paper has investigated the dyeing scheduling problems of dyeing and finishing workshops in knitting companies and proposed a hybrid GA that combines heuristic rules and VNS algorithms. The following conclusions have been obtained:

The actual production constraints of the dyeing workshop of knitting fabric companies have been abstracted. Scheduling models for dyeing workshops that are more suitable for actual production constraints have been proposed with a comprehensive consideration of constraints, such as the multiple parallel dyeing equipment of multiple types, upper and lower capacity limits of the equipment, relevance between specific dyeing task and equipment, and time and cost of equipment cleaning between two tasks that use different colours.

A hybrid GA that combines heuristic rules and the VNS algorithm has been employed to solve the dyeing workshop scheduling problem. Starting from actual production, the ultimate goal of scheduling is to minimize the cost of tank cleaning between two tasks and the delay cost. Therefore, when allocating equipment for dyeing order tasks, heuristic rules that consider product colour series switching and delays to delivery time have been designed. Detailed steps based on heuristic rules for equipment allocation of orders have been given. When using the hybrid GA to solve the scheduling problem, heuristic rules have been applied to generate the initial population. The neighbourhood search strategy has increased the diversity of dyeing colours and improved the evolutionary results of the algorithm.

The feasibility and effectiveness of the model and algorithm in solving the dyeing scheduling problems have been verified by testing cases in actual companies, which has an excellent prospect in engineering applications. Further research can consider the emergent dynamics of task orders and dynamic scheduling caused by re-working of unqualified dyeing in dyeing workshops.

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: This work is supported by National Natural Science Foundation of China under Grant No.51905091.

ORCID iD

Yaqin Zhou

References

Qiu

Zhou

Cheng

, et al. Study on optimizing production schedule based on pollution source control: a case study in a cotton knitting dyeing mill. Chin J Environ Eng 2016; 33(6): 1010–1016.

Zhou

Qiu

. Water conservation in textile dyeing process by optimizing production schedule. China Water Wastewater 2017; 33(6): 110–115.

Wang

Zhang

, et al. A collaborative architecture of the industrial internet platform for manufacturing systems. Robot Comput Integr Manuf 2020; 61: 101854.

Wang

Yang

Zhang

, et al. AdaBalGAN: An improved generative adversarial network with imbalanced learning for wafer defective pattern recognition. IEEE Trans Semicond Manuf 2019; 32(3): 310–319.

Azadeh

Ghaderi

Dabbaghi

, et al. Integration of simulation, design of experiment and goal programming for minimization of makespan and tardiness. Int J Adv Manuf Technol 2010; 46: 431–444.

Huynh

Chien

. A hybrid multi-subpopulation genetic algorithm for textile batch dyeing scheduling and an empirical study. Comput Ind Eng 2018; 125: 615–627.

Zhang

Chang

Song

, et al. A multi-objective artificial bee colony algorithm for parallel batch-processing machine scheduling in fabric dyeing processes. Knowl Based Syst 2017; 116: 114–129.

Hsu

Hsiung

Chen

, et al. A GA methodology for the scheduling of yarn-dyed textile production. Expert Syst Appl 2009; 36(10): 12095–12103.

Jiang

Yuan

Jun

, et al. Conserving water by optimizing production schedules in the dyeing industry. J Clean Prod 2020; 18(16–17): 1696–1702.

10.

Chen

. Research and design of optimized production planning of VAT system in dyeing yarn workshop. Hangzhou, China: Zhejiang University of Technology, 2007.

11.

Wen

Gao

. A new two-level hierarchical diagnosis network based on convolutional neural network. IEEE T Instrum Meas 2019; 69: 330–338.

12.

Wen

Gao

. A new snapshot ensemble convolutional neural network for fault diagnosis. IEEE Access 2019; 7: 32037–32047.

13.

Pinto

Grossmann

. Optimal cyclic scheduling of multistage continuous multiproduct plants. Comput Chem Eng 1994; 18(9): 797–816.

14.

Jia

Leung

JYT

. A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes. Europ J Oper Res 2015; 240(3): 649–665.

15.

Kashan

Karimi

Jolai

. An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes. Eng Appl Artif Intell 2010; 23(6): 911–922.

16.

Qiao

. ACO-based multi-objective scheduling of parallel batch processing machines with advanced process control constraints. Int J Adv Manuf Technol 2009; 44(9–10): 85–94.

17.

Abedi

Seidgar

Fazlollahtabar

, et al. Bi-objective optimisation for scheduling the identical parallel batch-processing machines with arbitrary job sizes, unequal job release times and capacity limits. Int J Prod Res 2005; 53(6): 1680–1711.

18.

Shahvari

Logendran

. An enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes. Comput Oper Res 2017; 77: 154–176.

19.

Bilyk

Mönch

Almeder

. Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics. Comput Ind Eng 2014; 78: 175–185.

20.

Shen

Mönch

Buscher

. A simultaneous and iterative approach for parallel machine scheduling with sequence-dependent family setups. J Schedul 2014; 17(5)): 471–487.

21.

Türkyılmaz

Bulkan

. A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel VNS execution. Int J Prod Res 2015; 53(6): 1832–1848.

22.

Huang

Yang

. A hybrid genetic algorithm for multi-objective flexible job shop scheduling problem considering transportation time. Int J Intel Comput Cybernet 2019; 12(2): 154–174.

23.

Moghadam

Wong

Piroozfard

. Solving a hybrid jobshop scheduling problem with space constraints and reentrant processes by using an improved hybrid genetic algorithm: a case study. Int J Ind Eng 2017; 24(5): 483–504.

24.

Kurdi

. An effective new island model genetic algorithm for job shop scheduling problem. Comput Oper Res 2016; 67: 132–142

25.

Tian

, et al. Parallel machine scheduling with dynamic resource allocation via a master-slave genetic algorithm. IEEJ Trans Electr Electron Eng 2018; 13(5): 748–756.

26.

Gao

Shao

, et al. Mathematical modeling and evolutionary algorithm-based approach for integrated process planning and scheduling. Comput Oper Res 2010; 37(4): 656–667.

27.

Zhou

Yang

, et al. Scheduling the production of aerospace structural parts with dual resource constraints. J Mech Eng 2018; 54(9): 55–63.

28.

Jin

Song

Yang

, et al. Dyeing machine scheduling problem in dyeing & finishing workshop. Comput Int Manuf Syst 2008; 14(3): 543–547.

Research on dyeing workshop scheduling methods for knitted fabric production based on a multi-objective hybrid genetic algorithm

Abstract

Keywords

Introduction

Dyeing scheduling problem

Scheduling problem of batch processing machine

Application of GA to scheduling problems

Establishing a scheduling model of dyeing workshop

Problem definition

Constraint conditions

Symbol definition

Mathematical model

Design of dyeing scheduling method based on hybrid GA

Task allocation based on heuristic rules

Task sorting based on hybrid GA

Individual coding design

Population initialization

Fitness function and population selection

Crossover and mutation

Local search strategy

Swap structure

Front structure insertion

Heuristic structure

Test cases and analysis

Test data

Comparison and analysis of the simulation results

Initial solution comparison experiment

Comparative test of equipment allocation methods of jobs

Random sorting method

Sorting method of delivery time

Colour series grouping and sorting method

Comparison of simulation and experiments

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References