# A Study of Flexible Flow Shop Scheduling Problem with Various Heterogeneous Labors

Authors: Rong-Hwa Huang; Shao-Jung Chang; Shun-Chi Yu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This study considers the necessity of hiring heterogeneous labors. So far, many studies focus more on manufacturing of equipment and control systems in the intelligent production planning. In fact, the regular labors’ processing time may be affected by the external factors and the disabled labors by the mentally handicapped. Therefore, this study sets the processing time of the two types of labors as fuzzy sets. The extra processing time from overtime generated by physical deterioration of old-aged labors is equal to the processing time of regular labors multiplied by the physical deterioration rate of old-aged labors on machine. The coefficient of the cost function is the stepwise function of cost structure. Besides, the dispatching rule based on floating time utilizes ant colony optimization to minimize the makespan. The data test results indicate that the proposed algorithm can efficiently dispatch and schedule the operations, with the average improvement ratio about 11.76%, and demonstrates high capability for the intelligent production planning


---

## Body

## 1. Introduction

In recent years, the value of old-age population over the age of 65 in the production line attracts more attention, as companies have been faced with the lack of skilled labors. Operations scheduling pursues to optimize resources and thus improves production efficiency and customers’ satisfaction. Belabid et al. [1] indicated that each job, represented by a set of operations, generates the path to be followed in the production scenario and considers a set N = {1, …, n} of n independent jobs that must be treated on a set of M = {1, …, m} machines within the same order [2, 3]. Many alike production treatments can be summarized as a flexible flow shop scheduling problem, representing the presence of parallel machines in some or all stages; thus, each stage of each job can be treated on several similar machines, and the processing time of each machine is different [4, 5]. The problem definition of this study is to solve the flexible flow shop scheduling problem with various heterogeneous labors, consisting of the regular, the disabled, and old-aged labors, for better arranging human power and limited resources. Thus, many studies focus more on manufacturing of equipment and control systems in the intelligent production planning, although it is observed that in some cases the processing times of operations can be controlled by allocating available resources [6]. Basically, the controlled processing times focuses on machine operational capacity or device parameter for processing work-in-piece; however, the uncertainty processing time in this study considers the different processing conditions like machine amounts, heterogeneous labors, or jobs with different materials. Notwithstanding, well-constructed medical care and health networks have extended the added value of the old-aged labors. The United Nations adopted the Convention on the Rights of Persons with Disabilities (CRPD) in 2006 [7]. Generally, the type of production management combines approaches of distributing operational productions to decrease makespan cost, inventory cost, wages, and other operational costs. In order to minimize those costs, the employment of the disabled and older labors becomes an alternative production choice. Meanwhile, many useful methods exist for solving scheduling problems and have various results [8].As far as all the scheduling problems are concerned, flexible flow shop scheduling is seen as the most popular production condition in the real manufacturing industry, such as in the pharmaceutical factory, mouldmaking, steel mill, and accessories shop processing scenarios. In flexible flow shop problems, various jobs go through a predetermined path and the sequence of using machines are the same for all jobs [9]. A well-arranged heterogeneous labor in the flow shop scheduling can efficiently decrease the excessive costs compared with competitors with the intelligent production planning. That is, the flow shop is an important way of production for daily necessities. The flow shop scheduling involving multiple agents has been investigated by more and more researchers because of its importance in realistic manufacturing and service systems [10, 11].Baker [12] indicated that common approach taken by most researchers is to use either an integer linear program or mixed integer linear program to find a minimum makespan solution. Huq et al. [13] pointed out that optimization algorithms did not always produce reasonable results when studying job shop and flow shop problems [14]. Generally, n jobs must be processed through m available machines in a flow shop scheduling problem. The jobs follow the pattern flow of machines. If the jobs follow the same sequence through machines, the problem is defined as a permutation flow shop [15]. Therefore, a multiobjective problem considering flexibility of job processing machines in a flexible flow shop (FFS) is considered using manufacturing simulation; results show the optimal resource assignment and optimal job sequence with efficiency and productivity. In addition, this method can minimize makespan, the number of late jobs, total flow time, and total weighted flow time in the flexible flow shop.As for heterogeneous labors, most studies considered unrelated machines for solving the attempted scheduling problems. Adapting an exact branch-and-price algorithm to a parallel machine scheduling problem on unrelated machines with sequence- and machine-dependent setup times, and parallelizing the adapted algorithm by implementing a distributed-memory parallelization with a master/worker approach, the conducting extensive computational experiments showed that the efficiency of parallelization approach can lead to superlinear speedup but can vary substantially between instances [16–18]. Researchers have developed increasingly efficient dispatching methods, heuristics, and algorithms for solving different scheduling problems. Scheduling considering learning effect is applied to solve a comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop [19]. Blum and Miralles [20] proposed an algorithm based on beam search for solving the Assembly Line Worker Assignment and Balancing Problem (ALWABP) with the objective of minimizing the cycle time when given a fixed number of workstations and workers. The result proved the efficiency and effectiveness of the method to solve the heterogeneous stations and workers.In regard to uncertainty processing time, Daniels and Kouvelis [21] applied the best worst-case performance compared to the corresponding optimal solution over all potential realization of job processing time, which was a more appropriate guide to schedule selection, besides the vague job processing times using triangular and trapezoidal fuzzy numbers in job shop production systems, in which the fuzzy makespans and fuzzy mean flow times are then calculated for greater decision-making information [22]. Joo et al. [23] developed an iterative job sequencing algorithm for solving a multilevel job scheduling problem in a single machine under uncertainty processing time that can be used for a given order sequence. Compared with the heuristic method and the unknown processing time fitting the practical situation, the results confirm that the proposed metaheuristic method with or without the iterative job sequencing algorithm indicates good performance [24]. It is reasonable to develop novel models and algorithms based on uncertainty processing time so as to solve uncertainty job shop scheduling problems [25–29]. Besides, stochastic processing time is common in literature [30, 31]. Rodrigues et al. [32] posited that many techniques cope with uncertainty, namely, deterministic models with inventory buffers, robust optimization, and stochastic programming, and thus models incorporating conditional value-at-risk measures are mostly considered. A fuzzy number which is essentially a generalized interval can represent this processing time interval exactly and naturally, though processing times can be more accurately represented as intervals with the most possible completion time somewhere amid the interval. Silva and de Souza [33] demonstrated an approximate dynamic programming with integer programming model, which outperformed the efficiency and effectiveness especially on solving the attempted problem, under uncertainties inherent to the surgical processes. Thus, this study applies fuzzy processing time for approximating the real world, instead of crisp value.As to algorithms, Huang and Lin [34] adopted a new bee colony optimization algorithm using idle-time-based filtering scheme based on the processes of the Forward Pass of bee’s foraging behaviors. That is, less machine idle time efficiently saves resources and production costs. Besides, Engin et al. [35] demonstrated an efficient genetic algorithm (GA) program using a full factorial experimental design to solve the hybrid flow shop scheduling with multiprocessor task problem. Computational results indicated that the proposed approach efficiently solves the problem of makespan. Nevertheless, many algorithms suffer limitations owing to the varied nature of problems that can be encountered. Zhen et al. [36] formulated a mixed integer linear programming model and developed an improved particle swarm optimization algorithm (IPSO) to solve the problem raised by hybrid electric vehicles (HEVs) with the advantages of low energy consumption and pollution, while their disadvantage mainly lies in their limited continuous driving range. The IPSO outperformed other approaches with efficiency and effectiveness. Thus, Dorigo et al. [37] developed the ant system using a population of cooperating agents and communicating via a distributed and shared memory and proved that the proposed algorithm can be applied to combinatorial optimization problems. Ant colony optimization (ACO) has an excellent ability to solve scheduling problems in the literature [14, 38, 39].This study examines the flexible flow shop scheduling with various heterogeneous labors using ant colony optimization, as this problem is more popular and real than most other problems. In fact, the regular labors’ processing time may be affected by the external factors and the disabled labors by the mentally handicapped. Therefore, this study sets the processing time of the two types of labors as fuzzy sets. Besides, this problem is complicated and worthy of verifying. This study compared the feasible solutions that are acceptable by different papers using the same effectiveness improvement rate proposed by this study. Singh and Singh [40] demonstrate 0.8% and 5.64% of the average relative effectiveness improvement rates of HGWOSCA against PSO and GWO, respectively. Chou et al. [41] show 61.65% and −1.68% of the average relative error rates of MABC against PSO and GA, respectively. Gupta and Srivastava [42] posited their testing results that demonstrate that ACO attains global minima in lesser number of iterations with a lower value when compared with PSO. However, each method has a distinct applicable area and is favorable to a particular domain based on its features. The motivation of using ACO in this study is the consideration of various heterogeneous labors, fuzzy processing time, and stepwise function of cost structure, not just comparisons among methods. Besides, the dispatching rule based on floating time utilizes ant colony optimization to minimize the makespan. Thus, ACO is proposed to solve this complex problem. This study applies an efficient dispatching rule, fuzzy processing time, and three heterogeneous labors using ACO to search for minimization of makespan. Also, the dispatching rule can prompt ants efficiently identify the next route. This performance reinforces the solution capacity of ACO and outperforms most of trade-off problems for future studies.


## 2. Problem definition

Related definitions and notifications are as follows.


### 2.1. Definition

(1)FFcZijWkMkrw,ZijWkMkdw,ZijWkMkow,er,ed,eoCmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo,where FFc represents a flexible flow shop environment involving k machines, ZijWhMk′rw,ZijWhMk′dw,ZijWhMk′ow represent the regular, disabled, and old-aged labor, respectively, er,ed,eo represent the quantity of the regular, disabled, and old-aged labor, respectively, and Cmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo demonstrates that the objective is to minimize the product of makespan considering the number of hired regular, disabled, and old-aged labors and deduction of subsidies of the disabled and old-aged labors from unit cost generated by incremental makespan.


### 2.2. Notification

n = total number of jobsm = total number of machinesw = total number of stationso = total number of operations to finishJi = job of number i, i = 1, 2, …, nOij = the jth operation of JiWh = the hth station of wWhMk = machine of number k in the hth stationOijWhMk=Oij is processed on Mk in the hth stationFFHWhMk = number of free float time on Mk in the hth stationIFHWhMk = number of interfering float time on Mk in the hth stationUWhMk = assigned number of operations on Mk in the hth stationrw = the amount of regular labordw = the amount of disabled laborow = the amount of old-aged laborer = number of hired regular labored = number of hired disabled laboreo = number of hired old-aged laborE= = number of total hired heterogeneous laborsWher = number of hired regular labors in the hth stationWhed = number of hired disabled labors in the hth stationWheo = number of hired old-aged labors in the hth stationC0 = unit cost generated by incremental makespanSd = the coefficient of subsidy per hour for hiring a disabled laborSo = the coefficient of subsidy per hour for hiring an old-aged laborCmaxer,ed,eo = makespan considering number of hired regular, old-aged, and disabled laborAi = number of operations to finish JiB = a big numberf = the physical deterioration rate of old-aged laborsSijWhMk = starting time of OijWhMk in the hth stationpijWhMk = processing time of OijWhMk in the hth stationFijWhMk = completion time of OijWhMk in the hth stationpijWhMkrw = processing time for regular labor to process OijWhMk in the hth stationpijWhMkdw = processing time for disabled labor to process OijWhMk in the hth stationpijWhMkow = processing time for old-aged labor to process OijWhMk in the hth stationuijow = the extra processing time from overtime generated by physical deterioration of old-aged laborsXijWhMk=1,ifOijis processed onMkin thehth station,0,otherwiseYijlqWhMk=1,ifOijis processed beforeOlqonMkin thehth station,0,otherwiseZijWhMkrw=1,ifMkis processed by regular labor in thehth station,0,otherwiseZijWhMkdw=1,ifMkis processed by disabled laborin thehth station,0,otherwiseZijWhMkow=1,ifMkis processed by old−aged laborin thehth station,0,otherwiseTijrw = the unit cost for processing Oij by hired regular laborsTijdw = the unit cost for processing Oij by hired disabled laborsTijow = the unit cost for processing Oij by hired old-aged labors


### 2.3. Mathematical Model

Formulation is as follows:(2)minZ=Cmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo,minZ=Cmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo,subject to(3)Cmaxer,ed,eo=max1≤k≤mFijWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(4)FijWhMk=SijWhMk+pijWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(5)Fij−1WhMk≤SijWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(6)pijWhMk=pijWhMkrwifZijWhMkrw=1,pijWhMkowifZijWhMkow=1,pijWhMkdwifZijWhMkdw=1,,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(7)FijWhMk−B1−YijlqWhMk≤SlqWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m;l=1,2,…,n;q=1,2,…,Qo;i≠l,(8)FlqWhMk1−YijlqWhMk−B⋅YijlqWhMk≤SijWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m;l=1,2,…,n;q=1,2,…,Qo;i≠l,(9)∑kXijWhMk=1,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(10)PijWhMkow=pijWhMkrw+uijow,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(11)uijow=pijWhMkrw⋅f,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m.The meanings of all objectives and constraints are explained as follows:In (2), this model minimizes the product of makespan considering the number of hired regular, old-aged, and disabled labors and deduction of subsidies of the disabled and old-aged labors from unit cost generated by incremental makespan on machine Mk in the hth station.(3), makespan considering the number of hired regular, old-aged, and disabled labors represents the maximum completion time among all the machines on machine Mk in the hth station.In (4), completion time of OijWhMk is the sum of its starting time and processing time on machine Mk in the hth station.In (5), for job, OijWhMk is the starting time of the jth operation exceeds the completion time of the (j − 1)th operation on machine Mk in the hth station.In (6), the processing time of OijWhMk is decided by different labors on machine Mk in the hth station.In (7), OijWhMk is processed before OlqWhMk, and thus, the completion time of OijWhMk is smaller than the starting time of OlqWhMk on machine Mk in the hth station.In (8), OijWhMk is processed after OlqWhMk, and thus, the completion time of OlqWhMk is smaller than the starting time of OijWhMk is on machine Mk in the hth station.In (9), Oijis only processed on one machine once in the hth station.In (10), completion time of Oij is the sum of its starting time and extra processing time from overtime generated by physical deterioration of old-aged labors on machine Mk in the hth station.In (11), extra processing time from overtime generated by physical deterioration of old-aged labors is equal to the processing time of regular labors multiplied by the physical deterioration rate (100/85) of old-aged labors on machine Mk in the hth station.


## 2.1. Definition

(1)FFcZijWkMkrw,ZijWkMkdw,ZijWkMkow,er,ed,eoCmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo,where FFc represents a flexible flow shop environment involving k machines, ZijWhMk′rw,ZijWhMk′dw,ZijWhMk′ow represent the regular, disabled, and old-aged labor, respectively, er,ed,eo represent the quantity of the regular, disabled, and old-aged labor, respectively, and Cmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo demonstrates that the objective is to minimize the product of makespan considering the number of hired regular, disabled, and old-aged labors and deduction of subsidies of the disabled and old-aged labors from unit cost generated by incremental makespan.


## 2.2. Notification

n = total number of jobsm = total number of machinesw = total number of stationso = total number of operations to finishJi = job of number i, i = 1, 2, …, nOij = the jth operation of JiWh = the hth station of wWhMk = machine of number k in the hth stationOijWhMk=Oij is processed on Mk in the hth stationFFHWhMk = number of free float time on Mk in the hth stationIFHWhMk = number of interfering float time on Mk in the hth stationUWhMk = assigned number of operations on Mk in the hth stationrw = the amount of regular labordw = the amount of disabled laborow = the amount of old-aged laborer = number of hired regular labored = number of hired disabled laboreo = number of hired old-aged laborE= = number of total hired heterogeneous laborsWher = number of hired regular labors in the hth stationWhed = number of hired disabled labors in the hth stationWheo = number of hired old-aged labors in the hth stationC0 = unit cost generated by incremental makespanSd = the coefficient of subsidy per hour for hiring a disabled laborSo = the coefficient of subsidy per hour for hiring an old-aged laborCmaxer,ed,eo = makespan considering number of hired regular, old-aged, and disabled laborAi = number of operations to finish JiB = a big numberf = the physical deterioration rate of old-aged laborsSijWhMk = starting time of OijWhMk in the hth stationpijWhMk = processing time of OijWhMk in the hth stationFijWhMk = completion time of OijWhMk in the hth stationpijWhMkrw = processing time for regular labor to process OijWhMk in the hth stationpijWhMkdw = processing time for disabled labor to process OijWhMk in the hth stationpijWhMkow = processing time for old-aged labor to process OijWhMk in the hth stationuijow = the extra processing time from overtime generated by physical deterioration of old-aged laborsXijWhMk=1,ifOijis processed onMkin thehth station,0,otherwiseYijlqWhMk=1,ifOijis processed beforeOlqonMkin thehth station,0,otherwiseZijWhMkrw=1,ifMkis processed by regular labor in thehth station,0,otherwiseZijWhMkdw=1,ifMkis processed by disabled laborin thehth station,0,otherwiseZijWhMkow=1,ifMkis processed by old−aged laborin thehth station,0,otherwiseTijrw = the unit cost for processing Oij by hired regular laborsTijdw = the unit cost for processing Oij by hired disabled laborsTijow = the unit cost for processing Oij by hired old-aged labors


## 2.3. Mathematical Model

Formulation is as follows:(2)minZ=Cmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo,minZ=Cmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo,subject to(3)Cmaxer,ed,eo=max1≤k≤mFijWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(4)FijWhMk=SijWhMk+pijWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(5)Fij−1WhMk≤SijWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(6)pijWhMk=pijWhMkrwifZijWhMkrw=1,pijWhMkowifZijWhMkow=1,pijWhMkdwifZijWhMkdw=1,,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(7)FijWhMk−B1−YijlqWhMk≤SlqWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m;l=1,2,…,n;q=1,2,…,Qo;i≠l,(8)FlqWhMk1−YijlqWhMk−B⋅YijlqWhMk≤SijWhMk,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m;l=1,2,…,n;q=1,2,…,Qo;i≠l,(9)∑kXijWhMk=1,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(10)PijWhMkow=pijWhMkrw+uijow,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m,(11)uijow=pijWhMkrw⋅f,∀i=1,2,…,n;j=1,2,…,Qi;h=1,2,…,w;k=1,2,…,m.The meanings of all objectives and constraints are explained as follows:In (2), this model minimizes the product of makespan considering the number of hired regular, old-aged, and disabled labors and deduction of subsidies of the disabled and old-aged labors from unit cost generated by incremental makespan on machine Mk in the hth station.(3), makespan considering the number of hired regular, old-aged, and disabled labors represents the maximum completion time among all the machines on machine Mk in the hth station.In (4), completion time of OijWhMk is the sum of its starting time and processing time on machine Mk in the hth station.In (5), for job, OijWhMk is the starting time of the jth operation exceeds the completion time of the (j − 1)th operation on machine Mk in the hth station.In (6), the processing time of OijWhMk is decided by different labors on machine Mk in the hth station.In (7), OijWhMk is processed before OlqWhMk, and thus, the completion time of OijWhMk is smaller than the starting time of OlqWhMk on machine Mk in the hth station.In (8), OijWhMk is processed after OlqWhMk, and thus, the completion time of OlqWhMk is smaller than the starting time of OijWhMk is on machine Mk in the hth station.In (9), Oijis only processed on one machine once in the hth station.In (10), completion time of Oij is the sum of its starting time and extra processing time from overtime generated by physical deterioration of old-aged labors on machine Mk in the hth station.In (11), extra processing time from overtime generated by physical deterioration of old-aged labors is equal to the processing time of regular labors multiplied by the physical deterioration rate (100/85) of old-aged labors on machine Mk in the hth station.


## 3. ACO, Fuzzy Processing Time, and Dispatching Rule

### 3.1. Ant Colony Optimization

Ant colony optimization is derived from the ant system (AS) first introduced by [43]. The development and applications of ACO grew rapidly since then. Dorigo et al. [44] applied AS to solve the traveling salesman problem, quadratic assignment problem, and scheduling problem. Subsequently, Dorigo and Gambardella [45] improved AS to create ant colony system (ACS). Finally, Dorigo and Di Caro [46] combined the properties of AS and ACS and developed ant colony optimization (ACO). A detailed introduction to ACO can be found in [47].ACO simulates the behavior of ants searching for food. Each ant uses exploitation and exploration for route selection. The state transition rule is used to balance exploitation and exploration behaviors:(12)s=argmaxu∈Jkrτr,uα⋅ηr,uβ,ifq≤q0,Pkr,s,otherwise,(13)Pkr,s=τr,sα⋅ηr,sβ∑u∈Jkrτr,sα⋅ηr,sβ,s∈Jkr,0,otherwise.The upper half of (12) comprises artificial ant exploitation behavior. When q≤q0, the ant will choose to progress to a node with the largest quantity of pheromones. q denotes a random number, and q0 represents a constant. Both q and q0 are real numbers between 0 and 1. Otherwise, the artificial ant uses exploration. As in (13), the quantity of pheromones determines the likelihood of an ant moving to the adjacent nodes. Ants perform route selection using the state transition rule. τ denotes the quantity of pheromones between two nodes r,u. Furthermore, η represents the greedy heuristic, which equals the inverse of the distance between nodes r,u. Jkr denotes the set of unexplored adjacent nodes. Furthermore, β is a constant which controls the relative importance of pheromone amount and greedy heuristic.When an ant chooses a complete route, the route can be transferred into a feasible schedule and objective value. The ant then leaves pheromone based on the objective value. The local pheromone update of ants is as shown in the following:(14)τr,s≔1−ρ⋅τr,s+ρ⋅Δτr,s.Local pheromone update prevents ants from solely selecting the best-known route, not exploring potential better routes, and falling into a local optimum.ρ denotes local pheromone evaporation rate and comprises a number between 0 and 1. Δτr,s represents the amount of pheromone increased between nodes r,s, as shown in (16). Q is a positive constant. Finally, Lk represents the objective value derived from the ant selected route.Following all ants in the present iteration select their route, the ant selecting the best route will initiate a global pheromone update to increase the influence of good route in the succeeding iterations. The following equation shows the global pheromone update:(15)τr,s≔1−σ⋅τr,s+σ⋅Δτr,s,(16)Δτr,sQLk,ifr,s∈global−best−tour,0,otherwise,where σ denotes the global pheromone evaporation rate and comprises a number between 0 and 1.


### 3.2. Fuzzy Processing Time

Concerning fuzzy processing time, Balin [30] posited various factors concerned in practical scheduling problems that were often uncertain or imprecise in nature. This is especially real when human-made factors are comprised of the problems. A fuzzy number is virtually a generalized interval that can indicate the processing time interval actually and naturally [48]. Fuzzy makespans and fuzzy mean flow times are then computed for greater decision-making message. By retaining the fuzziness throughout the analysis process, the decision-maker holds the whole message useful for subsequent sensitivity analysis of the capability criteria. Thus, this study utilizes fuzzy processing time for approximating the practical world, instead of crisp value.In order to meet the actual production situation, the working time is set as a fuzzy set. The most likely time for the completion of a job is called the most likely time (MLT), the minimum time required for a job to complete successfully is called the optimistic time (OT), and the longest time is called the most pessimistic time (PT). And the most optimistic time for the old-aged and disabled labors may be smaller than that of the most pessimistic time of the regular ones. Figure1 showed the graph of the fuzzy processing time range.Figure 1
The graph of the fuzzy processing time range.In terms of cost structure, this study assumes that fixed and intangible costs have been depreciated and amortized and only considers labors’ salary. In practice, when the completion time exceeds the expected completion due date, extra costs such as the overtime cost of the workers and the penalty cost of the tardiness will be derived. Therefore, the cost coefficient is set to a stepwise type, that is, when the maximum completion time exceeds the completion due date. A certain percentage of overtime will lead to an increase in the cost factor; this assumption complies with the practical situation.Before the assignment phase, defuzzification must be performed in advance, and the fuzzy set is converted into a crisp value, and then the subsequent operations are performed. The defuzzification process uses the triangular fuzzy number ordering condition proposed by [40]. The formula is as follows:(17)CA˜=a1+2a2+a34,CA˜=a1+2a2+a34.


### 3.3. Dispatching Rule

Concerning dispatching rule, this study calculates the makespan considering all hired regular labors using ACO, identifying the earliest and latest time span, and proposes a novel dispatching rule based on backward scheduling adopting the free float time (FF) and interfering float time (IF) to fit the lowest costs synchronously:(18)D1k=∑i=1n∑j=1oXijWhMkFFijWhMkfWhMk,∀k=1,2,…,m,D2k=FFHWhMkfWhMk,∀k=1,2,…,m,D3k=∑i=1n∑j=1oXijWhMkIFijWhMkfWhMk,∀k=1,2,…,m,D4k=IFHWhMkfWhMk,∀k=1,2,…,m,where D1k represents the average free float time of machine k in the hth station, and its calculation method is “the sum of free float time for machining in machine k, divided by the number of operations with free floats on machine k in the hth station”; D2k means “the ratio of the number of operations with free floats on machine k to the total number of operations on that machine in the hth station”; D3k represents the average interfering float time of the machine k in the hth station, and the calculation method is “the sum of interfering float time for machining in machine k, divided by the number of operations with interfering floats on machine k in the hth station”; D4k means “The ratio of the number of operations with interfering floats on machine k in the hth station to the total number of operations on that machine.” The assignment is carried out by stages, and each stage t is screened according to Dtkfrom large to small in descending order. If D1k in the first stage is the same, the second stage is performed, and so on. In order to keep the completeness of the assignment process, if the value is still the same in the fourth stage, D5k is performed, and D5k indicates that one machine is arbitrarily selected from the machine in the hth station that was not yet assigned with labors. After being assigned in the five stages above, the dispatching rule offers initial solution of the ant colony algorithm, which can avoid excessive calculating times and difficulty in obtaining the best solution under large scale of production, and searches for the better solution within polynomial time. Even if the best solution is not obtained, the better solution would not deviate too much from the minimum.In terms of stepwise function of cost structure, the ratio of cost coefficient is based on the minimum hourly wage of the current Labor Standard Laws in Taiwan. The hourly wage is set at 15 units according to the cost ratio. The government subsidy factor for the old-aged and disabled labors is set to an hourly subsidy of 4.5 units and 7 units, respectively. The stepwise function of cost structure factor is set at 36 hours as the due date, for example. Figure2 shows when the completion time excessed the due date, which is 36 hours, about more than 11%, which equals to 4 hours, will increase the cost factor by 4 units.Figure 2
Stepwise function of cost structure.The stepwise cost function is mainly affected by two factors: “extra unit cost from overtime” and “extra multiple from overtime.” First, “overtime” is defined as the extra time of completion time of the total hired regular labors. That is, completion time is used as a benchmark, which means that working time beyond this benchmark is considered “overtime.”The “extra unit cost from overtime” is the additional cost factor per unit time for overtime work. Therefore, the cost value of the regular labor’s completion time will not be affected by the “extra unit cost from overtime,” which mainly affects the rise of each level in the step function graph. The “extra multiple from overtime” is defined as 100% of the total completion time. After hiring a heterogeneous labor, each time a certain percentage is exceeded, the “extra unit cost from overtime” rate will be stepped. The formula is incremented by 1 time, and the ratio can be adjusted according to the actual situation. The “extra cost of overtime” is represented by the cost of “overtime” times “extra unit cost from overtime.” The total cost for production is the result of the “unit hour cost for production” times “completion time of the total hired regular labors” and “extra cost of overtime.” (Algorithm1) [43]Algorithm 1:Algorithm of ACO.
(1)
Procedure ACO(2)
Select an initial pointIterationt = 1Spread pheromones for the first iteration(3)
Do until reaching the stopping criteria(4)
For each ant(5)
For each job(6)
If job ≠1 then evaluate the initial point end if(7)
Load possible ending points in the last day for jobj(8)
Generate the graph for the problem(9)
For each condition of dispatching rule(10)
Computes the visibilityη for each possible move(11)
Draw the next job to be processed considering the probabilities.(12)
Updated the sparse graphs(13)
Next condition of dispatching rule(14)
Next job(15)
Apply the local search procedure(16)
Save the solution if it is the best one(17)
Computes the quantity of pheromones to be spread by the anti in each arc, job and day.(18)
Next ant(19)
update the pheromones using the variation andσt = t + 1(20)
Loop(21)
Return the best solution found


### 3.4. Algorithm

This section presents small-scale and large-scale simulated data tests to confirm the solution capacity of ACO. Substantial evidence based on test results demonstrates that ACO solves the attempted problem with efficiency.


## 3.1. Ant Colony Optimization

Ant colony optimization is derived from the ant system (AS) first introduced by [43]. The development and applications of ACO grew rapidly since then. Dorigo et al. [44] applied AS to solve the traveling salesman problem, quadratic assignment problem, and scheduling problem. Subsequently, Dorigo and Gambardella [45] improved AS to create ant colony system (ACS). Finally, Dorigo and Di Caro [46] combined the properties of AS and ACS and developed ant colony optimization (ACO). A detailed introduction to ACO can be found in [47].ACO simulates the behavior of ants searching for food. Each ant uses exploitation and exploration for route selection. The state transition rule is used to balance exploitation and exploration behaviors:(12)s=argmaxu∈Jkrτr,uα⋅ηr,uβ,ifq≤q0,Pkr,s,otherwise,(13)Pkr,s=τr,sα⋅ηr,sβ∑u∈Jkrτr,sα⋅ηr,sβ,s∈Jkr,0,otherwise.The upper half of (12) comprises artificial ant exploitation behavior. When q≤q0, the ant will choose to progress to a node with the largest quantity of pheromones. q denotes a random number, and q0 represents a constant. Both q and q0 are real numbers between 0 and 1. Otherwise, the artificial ant uses exploration. As in (13), the quantity of pheromones determines the likelihood of an ant moving to the adjacent nodes. Ants perform route selection using the state transition rule. τ denotes the quantity of pheromones between two nodes r,u. Furthermore, η represents the greedy heuristic, which equals the inverse of the distance between nodes r,u. Jkr denotes the set of unexplored adjacent nodes. Furthermore, β is a constant which controls the relative importance of pheromone amount and greedy heuristic.When an ant chooses a complete route, the route can be transferred into a feasible schedule and objective value. The ant then leaves pheromone based on the objective value. The local pheromone update of ants is as shown in the following:(14)τr,s≔1−ρ⋅τr,s+ρ⋅Δτr,s.Local pheromone update prevents ants from solely selecting the best-known route, not exploring potential better routes, and falling into a local optimum.ρ denotes local pheromone evaporation rate and comprises a number between 0 and 1. Δτr,s represents the amount of pheromone increased between nodes r,s, as shown in (16). Q is a positive constant. Finally, Lk represents the objective value derived from the ant selected route.Following all ants in the present iteration select their route, the ant selecting the best route will initiate a global pheromone update to increase the influence of good route in the succeeding iterations. The following equation shows the global pheromone update:(15)τr,s≔1−σ⋅τr,s+σ⋅Δτr,s,(16)Δτr,sQLk,ifr,s∈global−best−tour,0,otherwise,where σ denotes the global pheromone evaporation rate and comprises a number between 0 and 1.


## 3.2. Fuzzy Processing Time

Concerning fuzzy processing time, Balin [30] posited various factors concerned in practical scheduling problems that were often uncertain or imprecise in nature. This is especially real when human-made factors are comprised of the problems. A fuzzy number is virtually a generalized interval that can indicate the processing time interval actually and naturally [48]. Fuzzy makespans and fuzzy mean flow times are then computed for greater decision-making message. By retaining the fuzziness throughout the analysis process, the decision-maker holds the whole message useful for subsequent sensitivity analysis of the capability criteria. Thus, this study utilizes fuzzy processing time for approximating the practical world, instead of crisp value.In order to meet the actual production situation, the working time is set as a fuzzy set. The most likely time for the completion of a job is called the most likely time (MLT), the minimum time required for a job to complete successfully is called the optimistic time (OT), and the longest time is called the most pessimistic time (PT). And the most optimistic time for the old-aged and disabled labors may be smaller than that of the most pessimistic time of the regular ones. Figure1 showed the graph of the fuzzy processing time range.Figure 1
The graph of the fuzzy processing time range.In terms of cost structure, this study assumes that fixed and intangible costs have been depreciated and amortized and only considers labors’ salary. In practice, when the completion time exceeds the expected completion due date, extra costs such as the overtime cost of the workers and the penalty cost of the tardiness will be derived. Therefore, the cost coefficient is set to a stepwise type, that is, when the maximum completion time exceeds the completion due date. A certain percentage of overtime will lead to an increase in the cost factor; this assumption complies with the practical situation.Before the assignment phase, defuzzification must be performed in advance, and the fuzzy set is converted into a crisp value, and then the subsequent operations are performed. The defuzzification process uses the triangular fuzzy number ordering condition proposed by [40]. The formula is as follows:(17)CA˜=a1+2a2+a34,CA˜=a1+2a2+a34.


## 3.3. Dispatching Rule

Concerning dispatching rule, this study calculates the makespan considering all hired regular labors using ACO, identifying the earliest and latest time span, and proposes a novel dispatching rule based on backward scheduling adopting the free float time (FF) and interfering float time (IF) to fit the lowest costs synchronously:(18)D1k=∑i=1n∑j=1oXijWhMkFFijWhMkfWhMk,∀k=1,2,…,m,D2k=FFHWhMkfWhMk,∀k=1,2,…,m,D3k=∑i=1n∑j=1oXijWhMkIFijWhMkfWhMk,∀k=1,2,…,m,D4k=IFHWhMkfWhMk,∀k=1,2,…,m,where D1k represents the average free float time of machine k in the hth station, and its calculation method is “the sum of free float time for machining in machine k, divided by the number of operations with free floats on machine k in the hth station”; D2k means “the ratio of the number of operations with free floats on machine k to the total number of operations on that machine in the hth station”; D3k represents the average interfering float time of the machine k in the hth station, and the calculation method is “the sum of interfering float time for machining in machine k, divided by the number of operations with interfering floats on machine k in the hth station”; D4k means “The ratio of the number of operations with interfering floats on machine k in the hth station to the total number of operations on that machine.” The assignment is carried out by stages, and each stage t is screened according to Dtkfrom large to small in descending order. If D1k in the first stage is the same, the second stage is performed, and so on. In order to keep the completeness of the assignment process, if the value is still the same in the fourth stage, D5k is performed, and D5k indicates that one machine is arbitrarily selected from the machine in the hth station that was not yet assigned with labors. After being assigned in the five stages above, the dispatching rule offers initial solution of the ant colony algorithm, which can avoid excessive calculating times and difficulty in obtaining the best solution under large scale of production, and searches for the better solution within polynomial time. Even if the best solution is not obtained, the better solution would not deviate too much from the minimum.In terms of stepwise function of cost structure, the ratio of cost coefficient is based on the minimum hourly wage of the current Labor Standard Laws in Taiwan. The hourly wage is set at 15 units according to the cost ratio. The government subsidy factor for the old-aged and disabled labors is set to an hourly subsidy of 4.5 units and 7 units, respectively. The stepwise function of cost structure factor is set at 36 hours as the due date, for example. Figure2 shows when the completion time excessed the due date, which is 36 hours, about more than 11%, which equals to 4 hours, will increase the cost factor by 4 units.Figure 2
Stepwise function of cost structure.The stepwise cost function is mainly affected by two factors: “extra unit cost from overtime” and “extra multiple from overtime.” First, “overtime” is defined as the extra time of completion time of the total hired regular labors. That is, completion time is used as a benchmark, which means that working time beyond this benchmark is considered “overtime.”The “extra unit cost from overtime” is the additional cost factor per unit time for overtime work. Therefore, the cost value of the regular labor’s completion time will not be affected by the “extra unit cost from overtime,” which mainly affects the rise of each level in the step function graph. The “extra multiple from overtime” is defined as 100% of the total completion time. After hiring a heterogeneous labor, each time a certain percentage is exceeded, the “extra unit cost from overtime” rate will be stepped. The formula is incremented by 1 time, and the ratio can be adjusted according to the actual situation. The “extra cost of overtime” is represented by the cost of “overtime” times “extra unit cost from overtime.” The total cost for production is the result of the “unit hour cost for production” times “completion time of the total hired regular labors” and “extra cost of overtime.” (Algorithm1) [43]Algorithm 1:Algorithm of ACO.
(1)
Procedure ACO(2)
Select an initial pointIterationt = 1Spread pheromones for the first iteration(3)
Do until reaching the stopping criteria(4)
For each ant(5)
For each job(6)
If job ≠1 then evaluate the initial point end if(7)
Load possible ending points in the last day for jobj(8)
Generate the graph for the problem(9)
For each condition of dispatching rule(10)
Computes the visibilityη for each possible move(11)
Draw the next job to be processed considering the probabilities.(12)
Updated the sparse graphs(13)
Next condition of dispatching rule(14)
Next job(15)
Apply the local search procedure(16)
Save the solution if it is the best one(17)
Computes the quantity of pheromones to be spread by the anti in each arc, job and day.(18)
Next ant(19)
update the pheromones using the variation andσt = t + 1(20)
Loop(21)
Return the best solution found


## 3.4. Algorithm

This section presents small-scale and large-scale simulated data tests to confirm the solution capacity of ACO. Substantial evidence based on test results demonstrates that ACO solves the attempted problem with efficiency.


## 4. Data Testing and Analysis

### 4.1. Data Generation

This study examines the following subject scheduling problem ofFFcZijWkMkrw,ZijWkMkdw,ZijWkMkow,er,ed,eoCmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo. The following parameters are considered in generating test data: FFc represents a flexible flow shop environment involving k machines; ZijWhMk′rw,ZijWhMk′dw,ZijWhMk′ow represent the regular, disabled, and old-aged labor, respectively; er,ed,eorepresent the quantity of the regular, disabled, and old-aged labor, respectively; Cmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eodemonstrates that the objective is to minimize the product of makespan considering number of hired regular, disabled, and old-aged labors and deduction of subsidies of the disabled and old-aged labors from unit cost generated by incremental makespan. Parameters related to ACO algorithms include the following: α is the weight coefficient of pheromone influence, β is the weight coefficient of visibility function, σ is a global pheromone evaporation coefficient, ρ is a local pheromone evaporation coefficient, q0 is exploration/exploitation control ratio, and z is number of ants in each iteration and iterations (loop).The parameter settings in the proposed algorithm are decided during pretest, as listed in Table1. All tests are performed on a personal notebook with Intel R Core TM i5-3210M CPU @ 2.50 GHz, 4.0 GB RAM, and the OS version is Windows 10 R 64 bit. Finally, the test results are compared and analyzed.Table 1
Parameters setting of algorithm.
Parameterαβσρq0zLoopValue110.10.10.510200Regarding the setting of the weights of measuring criteria, the real business decision process is taken into consideration. Companies requirements in terms of criteria measurement weights vary according to their priorities. According to the feature of the attempted problem, this study adopts various scale number of machines and jobs. The ranges from small to large-scale number are as follows: scale (1):w = 3, n = 5; scale (2): w = 4, n = 10; scale (3): w = 5, n = 15; and scale (4): w = 6, n = 20. Due to limitation of content, this study lists w = 3, n = 5 for small scale and w = 6, n = 20 for demonstration of large scale, respectively. The item “E” in Table 2 indicates the number of hired heterogeneous labors, and “R,” “O,” and “D” in dispatching rule represent the assigned regular, old-aged, disabled labor, respectively, and the item “ms” means microsecond of CPU.Table 2
The optimal solution and makespan withw = 3, n = 5.
Amount of hired heterogeneous labors (E)Arrangement of laborsDispatching ruleCmaxOptimum solutionCPU timeer,ed,eo(w = 1, m = 3)(w = 2, m = 2)(w = 3, m = 2)(Total cost)(ms)0(7, 0, 0)RRRRRRR60.56352.5—1(6, 0, 1)RRRRRRO61.566186.78296.86(6, 1, 0)RRRRRRD61.946070.37296.872(5, 0, 2)RRORRRO63.376083.76265.62(5, 1, 1)RRDRRRO64.566036.36297.34(5, 2, 0)RRDRRRD62.625698.42281.243(4, 0, 3)RRORORO63.865842.96281.25(4, 1, 2)RRORDRO64.465736.72249.99(4, 2, 1)RRDRDRO60.845262.88265.76(4, 3, 0)RRDRDRD66.365573.82296.864(3, 0, 4)ROORORO64.685626.94218.74(3, 1, 3)RDORORO65.485532.64249.99(3, 2, 2)RDORDRO66.95485.96249.99(3, 3, 1)RDDRDRO67.977306.78249.99(3, 4, 0)RDDRDRD68.367177.28249.995(2, 0, 5)ROOOORO67.857497.7297.21(2, 1, 4)ROODORO68.097354.1296.87(2, 2, 3)RDODORO67.97163.14328.11(2, 3, 2)RDODDRO68.417045.97328.11(2, 4, 1)RDDDDRO68.716905.1265.81(2, 5, 0)RDDDDRD69.866845.79296.876(1, 0, 6)OOOOORO69.777395.09484.36(1, 1, 5)DOOOORO68.687107.86281.24(1, 2, 4)DOODORO68.016869.26312.49(1, 3, 3)DDODORO71.026994.98281.24(1, 4, 2)DDODDRO69.646684.96234.74(1, 5, 1)DDDDDRO68.676420.88415.25(1, 6, 0)DDDDDRD72.386586.49389.77(0, 0, 7)OOOOOOO71.177224.01292.84(0, 1, 6)OOOOODO71.177046.08283.21(0, 2, 5)DOOOODO71.176868.15311.78(0, 3, 4)DOODODO71.176690.22319(0, 4, 3)DDODODO78.539384.04285.18(0, 5, 2)DDODDDO71.466359.72316.43(0, 6, 1)DDDDDDO73.828452.39287.57(0, 7, 0)DDDDDDD77.178643.32338.08Note. The grey shading represents the minimal makespan among all combinations.As shown in Table2 and Figure 3, the assigned sequence considering degree of slack is W3M2 ⟶ W1M3 ⟶ W2M2 ⟶ W1M2 ⟶ W2M1 ⟶ W1M1 ⟶ W3L1. When hiring a heterogeneous labor, the best assignment is RRR RR RD. That is, the total cost is deduced from 6352.50 to 6070.37 when a heterogeneous labor is hired; when hiring two, the best assignment is RRD RR RD; when hiring three, the best assignment is RRD RD RO, and the results demonstrate that the hiring of heterogeneous labors surely decreases costs with efficiency. Since the lowest cost is 5262.88, the cost increases with the increasing amount of heterogeneous labors hired. Therefore, under the condition of w = 3, n = 5, and m = 7, it is recommended to hire 3 heterogeneous labors including 2 disabled labors to operate in W1M3 and W2M2, 1 old-aged labor to operate in W3M2, and regular labors to operate in W1M1, W1M2, W2M1, and W3M1, which generates the most efficiency of saving costs. The results reveal that production manager can choose the better way to hire appropriate amount of heterogeneous labors for cost-saving and to minimize completion time using the proposed dispatching rule. Besides, ACO solves the attempted problem with efficiency. The arrangement of labors, jobs, and machines is both effective and efficient for companies to apply in the real world.Figure 3
Scatter plot of cost structure with (w) = 3 and (n) = 5.As shown in Table3 and Figure 4, the assigned sequence considering degree of slack is W1M2 ⟶ W6M2 ⟶ W6M1 ⟶ W2M1 ⟶ W6M4 ⟶ W2M3 ⟶ W4M1 ⟶ W3M3 ⟶ W5M3 ⟶ W6M3 ⟶ W4M2 ⟶ W4M3 ⟶ W3M1 ⟶ W1M3 ⟶ W3M2 ⟶ W5M1 ⟶ W2M4 ⟶ W1M1 ⟶ W5M2 ⟶ W2M2. When hiring a heterogeneous labor, the best assignment is RDR RRRR RRR RRR RRR RRRR, when hiring two, the best assignment is RDR RRRR RRR RRR RRR RDRR, when hiring three, the best assignment is ROR RRRR RRR RRR RRR DDRR, and so on; the results demonstrate that the hiring of heterogeneous labors surely decreases costs with efficiency. Since the lowest cost is 156719.61, the cost increases with the hired amount of heterogeneous labors. Therefore, under the condition of w = 6, n = 20, m = 20, it is recommended to hire 9 heterogeneous labors including 6 disabled labors to operate in W2M1, W2M3, W3M3, W4M1, W5M3, and W6M4, 3 old-aged labors to operate in W1M2, W6M1, and W6M2, and regular labors to operate in W1M1, W1M3, W2M2, W2M4, W3M1, W3M2, W4M2, W4M3, W5M1, W5M2, and W6M3, which generates the most efficiency of saving costs. This study just demonstrates the amount of hired heterogeneous labors from 0∼7 and 20, due to the limit of content. The results reveal that production manager can choose the better way to hire appropriate amount of heterogeneous labors for cost-saving and to minimize completion time using the proposed dispatching rule.Table 3
The optimal solution and makespan withw = 6, n = 20.
Amount of hired heterogeneous labors (E)Arrangement of laborsDispatching ruleCmaxOptimum solutionCPU timeer,ed,eo(w = 1, m = 3)(w = 2, m = 4)(w = 3, m = 3)(w = 4, m = 3)(w = 5, m = 3)(w = 6, m = 4)(Total cost)(ms)0(20, 0, 0)RRRRRRRRRRRRRRRRRRRR590.5177150—1(19, 0, 1)RORRRRRRRRRRRRRRRRRR587.29173544.25315.63(19, 1, 0)RDRRRRRRRRRRRRRRRRRR589.25172650.255218.082(18, 0, 2)RORRRRRRRRRRRRRRRORR605.47176190.325331.14(18, 1, 1)RORRRRRRRRRRRRRRRDRR599.96173087.745295.04(18, 2, 0)RDRRRRRRRRRRRRRRRDRR599.43171436.275376.23(17, 0, 3)RORRRRRRRRRRRRRROORR611.46175182.575263.86(17, 1, 2)RORRRRRRRRRRRRRRDORR615.22174721.775375.03(17, 2, 1)RORRRRRRRRRRRRRRDDRR600.21168957.715302.12(17, 3, 0)RDRRRRRRRRRRRRRRDDRR612.15170789.155534.994(16, 0, 4)RORORRRRRRRRRRRROORR613.08172887.155481.58(16, 1, 3)RORDRRRRRRRRRRRROORR595.37166405.225319.75(16, 2, 2)RORDRRRRRRRRRRRRDORR602.28166831.565470.35(16, 3, 1)RORDRRRRRRRRRRRRDDRR602.74165450.765358.12(16, 4, 0)RDRDRRRRRRRRRRRRDDRR599.82163151.725531.055(15, 0, 5)RORORRRRRRRRRRRROORO616.05170954.575417.81(15, 1, 4)RORORRRRRRRRRRRROORD618.81170172.755599.63(15, 2, 3)RORDRRRRRRRRRRRROORD617.06168149.535392.19(15, 3, 2)RORDRRRRRRRRRRRRDORD619.57167282.555545.63(15, 4, 1)RORDRRRRRRRRRRRRDDRD612.53163851.115641.47(15, 5, 0)RDRDRRRRRRRRRRRRDDRD612.25162246.255452.246(14, 0, 6)RORORORRRRRRRRRROORO620.49169393.095592.88(14, 1, 5)RORORDRRRRRRRRRROORO613.28165890.895470.4(14, 2, 4)RORORDRRRRRRRRRROORD614.12164584.165654.9(14, 3, 3)RORDRDRRRRRRRRRROORD618.42164189.185562.88(14, 4, 2)RORDRDRRRRRRRRRRDORD631.46166073.325736.43(14, 5, 1)RORDRDRRRRRRRRRRDDRD613.77159886.435522.81(14, 6, 0)RDRDRDRRRRRRRRRRDDRD623.56160878.485609.587(13, 0, 7)RORORORRRRORRRRROORO625.11167842.715539.26(13, 1, 6)RORORORRRRDRRRRROORO625.54166392.315747.1(13, 2, 5)RORORDRRRRDRRRRROORO627.68165393.025707.66(13, 3, 4)RORORDRRRRDRRRRROORD622.06162358.315529.52(13, 4, 3)RORDRDRRRRDRRRRROORD628.93162577.765670.48(13, 5, 2)RORDRDRRRRDRRRRRDORD634.34162391.045532.89(13, 6, 1)RORDRDRRRRDRRRRRDDRD635.2161023.835863.24(13, 7, 0)RDRDRDRRRRDRRRRRDDRD635.44159495.445635.2120(0, 0, 20)OOOOOOOOOOOOOOOOOOOO713.87207022.888159.69(0, 1, 19)OOOODOOOOOOOOOOOOOOO715.98205844.258298.79(0, 2, 18)OOOODOOOOOOOOODOOOOO713.39203316.728401.87(0, 3, 17)DOOODOOOOOOOOODOOOOO714.9201958.48321.09(0, 4, 16)DOOODODOOOOOOODOOOOO714.99200197.768190.65(0, 5, 15)DOOODODOOOOOODDOOOOO719.76199733.968045.88(0, 6, 14)DOOODODODOOOODDOOOOO721.78256232.978086.76(0, 7, 13)DODODODODOOOODDOOOOO720.542539907999.67(0, 8, 12)DODODODDDOOOODDOOOOO722.76252966.358213.06(0, 9, 11)DODODODDDOOODDDOOOOO721.33250662.528260.78(0, 10, 10)DODODODDDOODDDDOOOOO724.77250045.318469.36(0, 11, 9)DODODODDDOODDDDOOODO725.78248580.688293.31(0, 12, 8)DODODODDDOODDDDDOODO723.89246123.968562.87(0, 13, 7)DODODODDDDODDDDDOODO722.77243935.218583.97(0, 14, 6)DODODODDDDDDDDDDOODO726.89243509.168756.91(0, 15, 5)DODODDDDDDDDDDDDOODO725.76241316.28861.01(0, 16, 4)DODODDDDDDDDDDDDOODD724.35239034.518684.7(0, 17, 3)DODDDDDDDDDDDDDDOODD727.54238269.688798.53(0, 18, 2)DODDDDDDDDDDDDDDDODD729.49237084.258689.65(0, 19, 1)DODDDDDDDDDDDDDDDDDD731.13235787.818759.75(0, 20, 0)DDDDDDDDDDDDDDDDDDDD730.98233914.248860.41Figure 4
Scatter of cost structure with (w) = 6 and (n) = 20.The results again reveal that production manager can choose the better way to hire appropriate number of heterogeneous labors for cost-saving and to minimize completion time using the proposed dispatching rule. Besides, ACO solves the attempted problem with efficiency. The arrangement of labors, jobs, and machines is both effective and efficient for companies to utilize in the real world.As shown in Table4, the improvement ratios of optimum are up to 17.15%, which demonstrates the percentage of cost-down under the proposed dispatching rule, with tolerable makespans compared with all regular workers hired. Test results show that improvement ratios are definite and outstanding in each test scale. As shown in Table 5, the optimum solutions are proved significantly difference in this study for solving the attempted problems.Table 4
The improvement ratios of optimal solution.
Scale (1)Scale (2)Scale (3)Scale (4)Workstationw3456Job (n)5101520Machine (m)7121720Best combination of dispatchingRegular∗4, disabled∗2, old-aged∗1Regular∗8, disabled∗2, old-aged∗2Regular∗11, disabled∗4, old-aged∗2Regular∗11, disabled∗6, old-aged∗3CPU time (ms)10396.6197351.64468900.351618725.21Optimum of all regular labors hired6352.550715114686.25177150Optimum of heterogeneous labors hired5262.8846931.62102196.77156719.61Improvement ratios (%)17.15%7.46%10.89%11.53%Table 5
Thet-test of various conditions optimal solution.
Scale (1)Scale (2)Scale (3)Scale (4)t Stat−44.404∗∗∗−83.939∗∗∗−194.167∗∗∗P (T ≤ t) one-tail0.0000.0000.000Note:∗ denotes p<0.05; ∗∗ denotes p<0.01; ∗∗∗ denotes p<0.001.


## 4.1. Data Generation

This study examines the following subject scheduling problem ofFFcZijWkMkrw,ZijWkMkdw,ZijWkMkow,er,ed,eoCmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo. The following parameters are considered in generating test data: FFc represents a flexible flow shop environment involving k machines; ZijWhMk′rw,ZijWhMk′dw,ZijWhMk′ow represent the regular, disabled, and old-aged labor, respectively; er,ed,eorepresent the quantity of the regular, disabled, and old-aged labor, respectively; Cmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eodemonstrates that the objective is to minimize the product of makespan considering number of hired regular, disabled, and old-aged labors and deduction of subsidies of the disabled and old-aged labors from unit cost generated by incremental makespan. Parameters related to ACO algorithms include the following: α is the weight coefficient of pheromone influence, β is the weight coefficient of visibility function, σ is a global pheromone evaporation coefficient, ρ is a local pheromone evaporation coefficient, q0 is exploration/exploitation control ratio, and z is number of ants in each iteration and iterations (loop).The parameter settings in the proposed algorithm are decided during pretest, as listed in Table1. All tests are performed on a personal notebook with Intel R Core TM i5-3210M CPU @ 2.50 GHz, 4.0 GB RAM, and the OS version is Windows 10 R 64 bit. Finally, the test results are compared and analyzed.Table 1
Parameters setting of algorithm.
Parameterαβσρq0zLoopValue110.10.10.510200Regarding the setting of the weights of measuring criteria, the real business decision process is taken into consideration. Companies requirements in terms of criteria measurement weights vary according to their priorities. According to the feature of the attempted problem, this study adopts various scale number of machines and jobs. The ranges from small to large-scale number are as follows: scale (1):w = 3, n = 5; scale (2): w = 4, n = 10; scale (3): w = 5, n = 15; and scale (4): w = 6, n = 20. Due to limitation of content, this study lists w = 3, n = 5 for small scale and w = 6, n = 20 for demonstration of large scale, respectively. The item “E” in Table 2 indicates the number of hired heterogeneous labors, and “R,” “O,” and “D” in dispatching rule represent the assigned regular, old-aged, disabled labor, respectively, and the item “ms” means microsecond of CPU.Table 2
The optimal solution and makespan withw = 3, n = 5.
Amount of hired heterogeneous labors (E)Arrangement of laborsDispatching ruleCmaxOptimum solutionCPU timeer,ed,eo(w = 1, m = 3)(w = 2, m = 2)(w = 3, m = 2)(Total cost)(ms)0(7, 0, 0)RRRRRRR60.56352.5—1(6, 0, 1)RRRRRRO61.566186.78296.86(6, 1, 0)RRRRRRD61.946070.37296.872(5, 0, 2)RRORRRO63.376083.76265.62(5, 1, 1)RRDRRRO64.566036.36297.34(5, 2, 0)RRDRRRD62.625698.42281.243(4, 0, 3)RRORORO63.865842.96281.25(4, 1, 2)RRORDRO64.465736.72249.99(4, 2, 1)RRDRDRO60.845262.88265.76(4, 3, 0)RRDRDRD66.365573.82296.864(3, 0, 4)ROORORO64.685626.94218.74(3, 1, 3)RDORORO65.485532.64249.99(3, 2, 2)RDORDRO66.95485.96249.99(3, 3, 1)RDDRDRO67.977306.78249.99(3, 4, 0)RDDRDRD68.367177.28249.995(2, 0, 5)ROOOORO67.857497.7297.21(2, 1, 4)ROODORO68.097354.1296.87(2, 2, 3)RDODORO67.97163.14328.11(2, 3, 2)RDODDRO68.417045.97328.11(2, 4, 1)RDDDDRO68.716905.1265.81(2, 5, 0)RDDDDRD69.866845.79296.876(1, 0, 6)OOOOORO69.777395.09484.36(1, 1, 5)DOOOORO68.687107.86281.24(1, 2, 4)DOODORO68.016869.26312.49(1, 3, 3)DDODORO71.026994.98281.24(1, 4, 2)DDODDRO69.646684.96234.74(1, 5, 1)DDDDDRO68.676420.88415.25(1, 6, 0)DDDDDRD72.386586.49389.77(0, 0, 7)OOOOOOO71.177224.01292.84(0, 1, 6)OOOOODO71.177046.08283.21(0, 2, 5)DOOOODO71.176868.15311.78(0, 3, 4)DOODODO71.176690.22319(0, 4, 3)DDODODO78.539384.04285.18(0, 5, 2)DDODDDO71.466359.72316.43(0, 6, 1)DDDDDDO73.828452.39287.57(0, 7, 0)DDDDDDD77.178643.32338.08Note. The grey shading represents the minimal makespan among all combinations.As shown in Table2 and Figure 3, the assigned sequence considering degree of slack is W3M2 ⟶ W1M3 ⟶ W2M2 ⟶ W1M2 ⟶ W2M1 ⟶ W1M1 ⟶ W3L1. When hiring a heterogeneous labor, the best assignment is RRR RR RD. That is, the total cost is deduced from 6352.50 to 6070.37 when a heterogeneous labor is hired; when hiring two, the best assignment is RRD RR RD; when hiring three, the best assignment is RRD RD RO, and the results demonstrate that the hiring of heterogeneous labors surely decreases costs with efficiency. Since the lowest cost is 5262.88, the cost increases with the increasing amount of heterogeneous labors hired. Therefore, under the condition of w = 3, n = 5, and m = 7, it is recommended to hire 3 heterogeneous labors including 2 disabled labors to operate in W1M3 and W2M2, 1 old-aged labor to operate in W3M2, and regular labors to operate in W1M1, W1M2, W2M1, and W3M1, which generates the most efficiency of saving costs. The results reveal that production manager can choose the better way to hire appropriate amount of heterogeneous labors for cost-saving and to minimize completion time using the proposed dispatching rule. Besides, ACO solves the attempted problem with efficiency. The arrangement of labors, jobs, and machines is both effective and efficient for companies to apply in the real world.Figure 3
Scatter plot of cost structure with (w) = 3 and (n) = 5.As shown in Table3 and Figure 4, the assigned sequence considering degree of slack is W1M2 ⟶ W6M2 ⟶ W6M1 ⟶ W2M1 ⟶ W6M4 ⟶ W2M3 ⟶ W4M1 ⟶ W3M3 ⟶ W5M3 ⟶ W6M3 ⟶ W4M2 ⟶ W4M3 ⟶ W3M1 ⟶ W1M3 ⟶ W3M2 ⟶ W5M1 ⟶ W2M4 ⟶ W1M1 ⟶ W5M2 ⟶ W2M2. When hiring a heterogeneous labor, the best assignment is RDR RRRR RRR RRR RRR RRRR, when hiring two, the best assignment is RDR RRRR RRR RRR RRR RDRR, when hiring three, the best assignment is ROR RRRR RRR RRR RRR DDRR, and so on; the results demonstrate that the hiring of heterogeneous labors surely decreases costs with efficiency. Since the lowest cost is 156719.61, the cost increases with the hired amount of heterogeneous labors. Therefore, under the condition of w = 6, n = 20, m = 20, it is recommended to hire 9 heterogeneous labors including 6 disabled labors to operate in W2M1, W2M3, W3M3, W4M1, W5M3, and W6M4, 3 old-aged labors to operate in W1M2, W6M1, and W6M2, and regular labors to operate in W1M1, W1M3, W2M2, W2M4, W3M1, W3M2, W4M2, W4M3, W5M1, W5M2, and W6M3, which generates the most efficiency of saving costs. This study just demonstrates the amount of hired heterogeneous labors from 0∼7 and 20, due to the limit of content. The results reveal that production manager can choose the better way to hire appropriate amount of heterogeneous labors for cost-saving and to minimize completion time using the proposed dispatching rule.Table 3
The optimal solution and makespan withw = 6, n = 20.
Amount of hired heterogeneous labors (E)Arrangement of laborsDispatching ruleCmaxOptimum solutionCPU timeer,ed,eo(w = 1, m = 3)(w = 2, m = 4)(w = 3, m = 3)(w = 4, m = 3)(w = 5, m = 3)(w = 6, m = 4)(Total cost)(ms)0(20, 0, 0)RRRRRRRRRRRRRRRRRRRR590.5177150—1(19, 0, 1)RORRRRRRRRRRRRRRRRRR587.29173544.25315.63(19, 1, 0)RDRRRRRRRRRRRRRRRRRR589.25172650.255218.082(18, 0, 2)RORRRRRRRRRRRRRRRORR605.47176190.325331.14(18, 1, 1)RORRRRRRRRRRRRRRRDRR599.96173087.745295.04(18, 2, 0)RDRRRRRRRRRRRRRRRDRR599.43171436.275376.23(17, 0, 3)RORRRRRRRRRRRRRROORR611.46175182.575263.86(17, 1, 2)RORRRRRRRRRRRRRRDORR615.22174721.775375.03(17, 2, 1)RORRRRRRRRRRRRRRDDRR600.21168957.715302.12(17, 3, 0)RDRRRRRRRRRRRRRRDDRR612.15170789.155534.994(16, 0, 4)RORORRRRRRRRRRRROORR613.08172887.155481.58(16, 1, 3)RORDRRRRRRRRRRRROORR595.37166405.225319.75(16, 2, 2)RORDRRRRRRRRRRRRDORR602.28166831.565470.35(16, 3, 1)RORDRRRRRRRRRRRRDDRR602.74165450.765358.12(16, 4, 0)RDRDRRRRRRRRRRRRDDRR599.82163151.725531.055(15, 0, 5)RORORRRRRRRRRRRROORO616.05170954.575417.81(15, 1, 4)RORORRRRRRRRRRRROORD618.81170172.755599.63(15, 2, 3)RORDRRRRRRRRRRRROORD617.06168149.535392.19(15, 3, 2)RORDRRRRRRRRRRRRDORD619.57167282.555545.63(15, 4, 1)RORDRRRRRRRRRRRRDDRD612.53163851.115641.47(15, 5, 0)RDRDRRRRRRRRRRRRDDRD612.25162246.255452.246(14, 0, 6)RORORORRRRRRRRRROORO620.49169393.095592.88(14, 1, 5)RORORDRRRRRRRRRROORO613.28165890.895470.4(14, 2, 4)RORORDRRRRRRRRRROORD614.12164584.165654.9(14, 3, 3)RORDRDRRRRRRRRRROORD618.42164189.185562.88(14, 4, 2)RORDRDRRRRRRRRRRDORD631.46166073.325736.43(14, 5, 1)RORDRDRRRRRRRRRRDDRD613.77159886.435522.81(14, 6, 0)RDRDRDRRRRRRRRRRDDRD623.56160878.485609.587(13, 0, 7)RORORORRRRORRRRROORO625.11167842.715539.26(13, 1, 6)RORORORRRRDRRRRROORO625.54166392.315747.1(13, 2, 5)RORORDRRRRDRRRRROORO627.68165393.025707.66(13, 3, 4)RORORDRRRRDRRRRROORD622.06162358.315529.52(13, 4, 3)RORDRDRRRRDRRRRROORD628.93162577.765670.48(13, 5, 2)RORDRDRRRRDRRRRRDORD634.34162391.045532.89(13, 6, 1)RORDRDRRRRDRRRRRDDRD635.2161023.835863.24(13, 7, 0)RDRDRDRRRRDRRRRRDDRD635.44159495.445635.2120(0, 0, 20)OOOOOOOOOOOOOOOOOOOO713.87207022.888159.69(0, 1, 19)OOOODOOOOOOOOOOOOOOO715.98205844.258298.79(0, 2, 18)OOOODOOOOOOOOODOOOOO713.39203316.728401.87(0, 3, 17)DOOODOOOOOOOOODOOOOO714.9201958.48321.09(0, 4, 16)DOOODODOOOOOOODOOOOO714.99200197.768190.65(0, 5, 15)DOOODODOOOOOODDOOOOO719.76199733.968045.88(0, 6, 14)DOOODODODOOOODDOOOOO721.78256232.978086.76(0, 7, 13)DODODODODOOOODDOOOOO720.542539907999.67(0, 8, 12)DODODODDDOOOODDOOOOO722.76252966.358213.06(0, 9, 11)DODODODDDOOODDDOOOOO721.33250662.528260.78(0, 10, 10)DODODODDDOODDDDOOOOO724.77250045.318469.36(0, 11, 9)DODODODDDOODDDDOOODO725.78248580.688293.31(0, 12, 8)DODODODDDOODDDDDOODO723.89246123.968562.87(0, 13, 7)DODODODDDDODDDDDOODO722.77243935.218583.97(0, 14, 6)DODODODDDDDDDDDDOODO726.89243509.168756.91(0, 15, 5)DODODDDDDDDDDDDDOODO725.76241316.28861.01(0, 16, 4)DODODDDDDDDDDDDDOODD724.35239034.518684.7(0, 17, 3)DODDDDDDDDDDDDDDOODD727.54238269.688798.53(0, 18, 2)DODDDDDDDDDDDDDDDODD729.49237084.258689.65(0, 19, 1)DODDDDDDDDDDDDDDDDDD731.13235787.818759.75(0, 20, 0)DDDDDDDDDDDDDDDDDDDD730.98233914.248860.41Figure 4
Scatter of cost structure with (w) = 6 and (n) = 20.The results again reveal that production manager can choose the better way to hire appropriate number of heterogeneous labors for cost-saving and to minimize completion time using the proposed dispatching rule. Besides, ACO solves the attempted problem with efficiency. The arrangement of labors, jobs, and machines is both effective and efficient for companies to utilize in the real world.As shown in Table4, the improvement ratios of optimum are up to 17.15%, which demonstrates the percentage of cost-down under the proposed dispatching rule, with tolerable makespans compared with all regular workers hired. Test results show that improvement ratios are definite and outstanding in each test scale. As shown in Table 5, the optimum solutions are proved significantly difference in this study for solving the attempted problems.Table 4
The improvement ratios of optimal solution.
Scale (1)Scale (2)Scale (3)Scale (4)Workstationw3456Job (n)5101520Machine (m)7121720Best combination of dispatchingRegular∗4, disabled∗2, old-aged∗1Regular∗8, disabled∗2, old-aged∗2Regular∗11, disabled∗4, old-aged∗2Regular∗11, disabled∗6, old-aged∗3CPU time (ms)10396.6197351.64468900.351618725.21Optimum of all regular labors hired6352.550715114686.25177150Optimum of heterogeneous labors hired5262.8846931.62102196.77156719.61Improvement ratios (%)17.15%7.46%10.89%11.53%Table 5
Thet-test of various conditions optimal solution.
Scale (1)Scale (2)Scale (3)Scale (4)t Stat−44.404∗∗∗−83.939∗∗∗−194.167∗∗∗P (T ≤ t) one-tail0.0000.0000.000Note:∗ denotes p<0.05; ∗∗ denotes p<0.01; ∗∗∗ denotes p<0.001.


## 5. Conclusion

This study examines the flexible flow shop scheduling problem, which is well-known for its strong NP-hard. The problem we study can be depicted asFFcZijWkMkrw,ZijWkMkdw,ZijWkMkow,er,ed,eoCmaxer,ed,eo⋅Co⋅m−Sd⋅ed−So⋅eo. The problem involves fuzzy numbers, stepwise cost function, float time, and heterogeneous labors in a flexible flow shop, in which the objective is to minimize the product of makespan considering costs of hired regular, disabled, and old-aged labors and deduction of subsidies for the disabled and old-aged labors from unit cost emerged by incremental makespan.The extra processing time from overtime generated by physical deterioration of old-aged labors is equal to the processing time of regular labors multiplied by the physical deterioration rate of old-aged labors on machine. The coefficient of the cost function is the stepwise function of cost structure. Besides, the dispatching rule based on floating time utilizes ant colony optimization to minimize the makespan. Numerous studies indicate that ACO has excellent capacity to solve flexible flow shop scheduling problems, and this study demonstrates its effectiveness in solving the attempted problems.This study significantly surmounts and grants ACO to solve the flexible flow shop scheduling problem and then compares various scales of solutions for saving costs. According to the test results and analysis, this study infers the following.(1)
The advantage of this study is to downsize the complexity of the combination, assigning heterogeneous labors for keeping efficiency and costs of production. The effectiveness improvement ratio of hiring heterogeneous labors compared with regular ones inw = 3 and n = 5 is 17.15%, and 7.46% in w = 4 and n = 10, 10.89% in w = 5 and n = 15, and 11.53% in w = 6 and n = 20. This examines that the proposed method significantly surpasses the dispatching rule in terms of effectiveness and costs.(2)
By screening the degree of float time of machines, assigning appropriate labors to operate can really reduce the computation time and the impact of hiring heterogeneous labors on the total completion time. The results indicate that the effectiveness and efficiency of the proposed method clearly transcends than that of manual production scheduling.(3)
Under the various scales set in this study, ACO has excellent solving efficiency, which matches the capability of intelligent production planning. The data test results indicate that the proposed algorithm can efficiently dispatch and schedule the operations, with the average improvement ratio about 11.76%, and demonstrates high capability for the intelligent production planning.(4)
The suggestions for the future studies are using different dispatching rules or total flow time that might better match the real-world situations.Above all, this study indicates that ACO outperforms advantages over both effectiveness and cost-saving. Thus, ACO has the potential to solve complicated problems in the practical scenario and becomes a significant heuristic algorithm for this kind of problem, responding to both production situations and future research.



---

*Source: 5529612-2021-07-12.xml*