Sage Journals: Discover world-class research

Abstract

In recent years, Virtual Cellular Manufacturing Systems, which combine virtual cells to construct new manufacturing systems in response to changing market dynamics, have attracted considerable attention. Especially, the real-time scheduling of Virtual Cellular Manufacturing Systems has been of significant importance. In this article, a hybrid control architecture based on multi-agent technology is introduced to support the coordination mechanism to schedule tasks and resources in real-time. Using the revised resource element approach with the pheromone concept, the real-time scheduling problem is divided into two sub-problems, that is, task ranking and resource load-balancing, which can be solved by explicit and implicit coordination mechanisms, respectively. Finally, the proposed coordination mechanism is proven in illustrative examples to perform more efficiently with reduced processing and holding costs.

Keywords

Coordination mechanism pheromone quantum implicit coordination explicit coordination function-shared-degree

Introduction

The dynamic global market, characterized by compressed product life cycles, increased product varieties, volatile conditions and fiercely competitive market competition, has compelled manufacturing firms to improve their abilities to face the challenges. One of the most effective strategies to boost productivity is to re-configure its facilities.¹ The concept of Virtual Cellular Manufacturing Systems (VCMSs) was first proposed by National Bureau of Standards (NBS) on the assumption that the “factory of the future” with a hierarchical structure can dynamically alter its subsystem allocations as demands change. The benefits of VCMSs include reduced set-up times, lower work-in-process levels, shorter throughput times, improved product quality, and reduced material handling.²

The life cycle of a VCMS is typically composed of four stages, that is, cell formation (CF), production planning, real-time scheduling, and conflict resolution. Currently, most researchers focus on the CF problem in the first stage which is essential in the establishment of a VCMS (classical, dynamic, and virtual). The formation of a virtual manufacturing cell involves the allocation of machines to each cell that take care of certain part families.³ CF is complex because it has to consider various production factors, such as alternative process routings, operational sequences, batch size, machine capacities, tooling times, and others as discussed by various researchers.^4–6

All the aforementioned issues have to be considered when modeling manufacturing resources in CF problems. However, the current work has not paid sufficient attention to some actual problems. Along with the advances in manufacturing technology and equipment, the capacity boundaries of each machine and the operations they can perform are largely extended. Some operations can be conducted on more than one machine, and some machines can perform a number of different operations. The classical way of defining manufacturing systems and their capacities does not provide sufficient details on the similar and exclusive boundaries among facilities. The shared issues in VCMSs should not be a machine but some function parts of a machine.⁷ Not all the function parts of a machine are required by the virtual cells (VCs), while some special function parts can be handled by a few VCs. Thus, to address the aforementioned deficiencies, the resource element (RE)-based approach has been adopted to define and tackle the resource modeling problems in manufacturing systems.⁸

With the RE algorithms, the many-to-many relationship between the parts and cells can be transformed into one-to-one mappings, and the nonlinear process plans can be transformed into linear RE sequences. However, the complicated many-to-many relationship between the parts and cells must be recognized and dealt with in the CF phase using mathematical programming or other optimization algorithms. The cell configuration could change significantly from one period to another caused by the fluctuations in some parameters of the system, such as part demand and machine capacity.³ The manufacturing resources required to complete the process cannot be determined without referring to real-time production capacity of the system. In addition, data inaccuracy and unforeseen events, such as machine breakdowns, communication issues in the manufacturing processes, or a scheduled facility that may have to be replaced at the last minute, may cause jobs to take longer than originally planned.

Thus, after the linear RE sequences assist to verify the similarities in the machines and cluster the machines into the VCs, the nonlinear property of the process plans in VCMSs should be maintained throughout the period of production scheduling. Hence, real-time control and scheduling of VCMSs remain largely unexplored.

For example, when some resources are selected according to the processing cost, the manager does not know whether the decision is right or not in the long run. Especially for multi-function machines, if they are selected to finish a process with a shared function, they may not be available to handle other processes with an exclusive function in the future. If the machines are not selected, other more costly machines may have to be used and lead to an increase in total cost. Therefore, the processing cost and the utilization rate of shared function should be considered in parallel, resulting in trade-offs. In particular, the coordination mechanism should be adaptive to fine-tuning its properties according to different manufacturing systems as well as task execution procedures.

Introduced to analyze and judge the future trend, the pheromone concept in ant colony optimization (ACO) approach can guide tasks select lower cost resource with functions which are also less shared with other resources. The pheromone quantum can be changed according to the manufacturing process and machine utilization rate. When the current tasks are completed, they would evaporate along with the time in order to avoid falling into the local optima. Using the revised RE approach with the pheromone concept and the support of hybrid control architecture, the coordination mechanism can operate more efficiently at improved productivity and reduced communication and negotiation costs.

The proposed approach consists of three parts as follows:

Manufacturing resource modeling: under the Form Generating Schema (FGS) concept, each manufacturing resource represents a collection of FGSs as well as the exclusive and shared capacity boundaries between available machine tools in a manufacturing unit in order to help virtual CF. Having pheromone properties, the manufacturing resources model can be extended to help solve real-time scheduling problems more efficiently.

Control architecture: a hybrid control architecture based on multi-agent technology is adopted to coordinate and schedule tasks and resources in VCMSs. With the control architecture, the real-time scheduling problem is divided as two sub-parts, namely, the task ranking problem and the resource load-balancing problem.

Coordination mechanism: explicit coordination mechanism (ECM) and implicit coordination mechanism (ICM) are built into the control architecture to coordinate the activities among the tasks and manufacturing resources. The explicit mechanism deals with the task ranking problem with due consideration of the processing costs and due dates. The implicit mechanism focuses on the resource load-balancing by selecting adequate resource according to their pheromone which can be renewed from candidate resources as well as potential competitive resources having similar functions in the future.

The rest of this article is organized as follows. The main focuses of the research are summarized in section “Literature review.” The modeling methodology and the control mechanism are described in section “The coordination mechanism–oriented real-time scheduling.” Illustrative examples and further discussions are given in section “Illustrative examples.” Finally, conclusions are drawn in section “Conclusion.”

Literature review

Supported by the rapid development of computer technology and the increasing trend of economic globalization, contemporary manufacturing environment has changed significantly with customer-driven, dynamic and changeable product requirements.⁹ In addition to providing high-quality products, manufacturing enterprises should also be able to react quickly to unexpected circumstances in a cost-effective manner.

Undoubtedly, one of the most effective strategies to boost the capacity of a manufacturing unit is to re-configure its facilities.¹ Hence, research work of reconfiguration problems to deal with internal and external disturbances has been widely published. After Flexible Manufacture System (FMS), Holonic Manufacturing System (HMS), Cellular Manufacturing System (CMS) concepts, VCMSs using new reconfiguration approach with more flexibility in response to changing requirements were developed by NBS in the 1980s.¹⁰

In VCMSs, to retain the functional layout, a VC is defined as a logical grouping of processors that is not necessary to be transposed into physical proximity. In fact, a virtual machine does not exist in reality but put together by the systems in the form of a logical entity.¹¹ The main difference between a VC and a classic cell lies with the dynamic nature of the VC. The physical location and capacity of a classic cell is normally fixed, whereas a VC allows flexible reconfiguration of shop floors in response to changing requirements.¹²

In VCMSs, as a complex and time-consuming non-deterministic polynomial-time (NP) hard problem,⁴ CF is the most important step in designing manufacturing systems with completely independent machine cells having identified and allocated part families.^13,14 CF solutions often contain Exceptional Elements (EEs) problem,^15–18 where machines are required by a number of part families or conversely parts are processed on machines in several cells. Although CF and EEs problems are both crucial in the design and operation of VCMSs, the former problem has attracted more attentions and gained momentum during the last decade. In most literature,^19,20 EEs problems are dealt with after CF and much less common compared to the CF problems.

VCMSs are complex to design and operate because of the inherent judgments involved in deciding machine groupings and product families which dictate the system’s performance. All the aforementioned issues have some contributions to modeling the manufacturing resources in EEs and CF problems. However, their research has not paid sufficient attention to the crucial problems of multi-function machines.

Along with the advances in manufacturing technology and machines, the capacity boundaries of each machine and the operations they can perform are well defined. Some operations can be performed on more than one machine, while some machines can handle a number of different tasks. The classical way of defining manufacturing systems and their capacities does not provide sufficient details in describing the similar and exclusive boundaries between machines. Not all the function parts of a machine are required by the VCs, while some special function parts can be handled by a few VCs. To address the aforementioned deficiencies in VCMSs, the RE-based approach has been adopted in some research work to define and tackle the many-to-many relationships in resource modeling. RE approach combines the advantages of functional and product-oriented resources structures supporting both efficient internal logistics management and convenient production resources management.^7,8,21–25

In addition, with the development of computer technology, the anticipated extensive use of VCMSs in the future has encouraged its intensive research on their control and scheduling methodologies in recent years. However, few research has been carried out on real-time scheduling of VCMSs. Previous work mainly focuses on their static production plan and scheduling mainly using linear programming.^24,26 Linear programming control models lack real-time feedback function in the process of control. They require iterations through phases of trial, analysis and redesign in order to converge to a desired property. For complex VCMSs, the time-consuming calculations may slow down the response speed of systems.

Thus, in this article, efficient control architecture and coordination mechanism are proposed for VCMSs in order to improve their real-time scheduling performance.

The coordination mechanism–oriented real-time scheduling

Manufacturing resource modeling based on RE approach

As a foundational element of RE approach, FGS is a structured schema for defining potential machining operations, stating processing requirements of parts and the capabilities of machine tools. Technically, an FGS is a meaningful integration of a cutting tool of a specific geometry, a set of relative motions between the part and the cutting tool, and typical levels of technological output associated with using a combination of tool and relative motions.²¹ The representation of FGS is shown in Figure 1, and equation (1) shows how a FGS named $f_{a}$ ^22,25,27 can be expressed

f_{a} = {P_{a}, T_{a}, R_{a}}

(1)

$P_{a}$ represents the machining processes;

$T_{a}$ is the part type;

$R_{a}$ includes the information of the machining process, which is expressed as a triple array ( $Cut, Mp, \Pr e$ );

$Cut$ denotes the cutting tool in the machining process;

$Mp$ is expressed as the array according to the processing type with references to Figure 1:

$R$ denotes the rotating processing of machine axis, the subscript denotes the direction parallel the principal axis;

$T$ presents the feeding operation parallel the clamping surface of part, the subscript denotes the required feeding direction of cutting tool;

$t$ presents the feeding operation parallel the principal axis, the subscript denotes the required feeding direction of cutting tool;

$Pre$ denotes the machining precision, which is expressed as the combination of surface roughness $Sur$ and calibration tolerance $Tol$ ;

$x$ and $y$ parallel the clamping surface of part; $z$ parallels the principal axis; and $i, j, k$ are the feeding operations corresponding to the $x, y, z$ axes, respectively.

Figure 1.

FGS representation.

As mentioned above, it is acceptable to represent a single machine or a multi-functional machine center as a collection of FGSs on a shop floor, such that

\begin{matrix} F = {f_{1,} f_{2}, \dots, f_{n}} \\ N = {1_{1,} 2, \dots, n} \end{matrix}

(2)

in which, $n$ denotes the quantity of FGSs in $F$ .

By identifying whether a manufacturing resource includes the FGSs, the manufacturing resources $M_{k}$ can be expressed as

\begin{matrix} M_{k} = (m_{1 k} f_{1}, m_{2 k} f_{2}, \dots, m_{ik} f_{i}, \dots, m_{nk} f_{n}), \forall M_{k} \in M \\ m_{ik} = {\begin{matrix} 1, if f_{i} \in M_{k} \\ 0, if f_{i} \notin M_{k} \end{matrix} \end{matrix}

(3)

in which, if $M_{k}$ includes the function $f_{i}$ , then $m_{ik} = 1$ ; otherwise $m_{ik} = 0$ .

According to the presentations, every manufacturing resource can be expressed as a collection of FGSs. An illustrative example is shown in Figure 2. It can be deduced that using the RE approach, the manufacturing system can be divided into different function parts, and each RE is composed of an exclusive set of machine functions.

Figure 2.

The manufacturing resource model based on RE approach.

To a single-function machine, there are no differences to model the manufacturing resources between FGS approach and other modeling approaches. However, for a multi-functional machine center, the similar and exclusive functions can be recognized and defined clearly. Thus, if the FGS approach is introduced into manufacturing resource modeling, the similar and exclusive functions can be distinguished from the machines with overlapping functions to simplify the CF problem. In VCMSs, in order to improve the scheduling phase, the similarity or exclusive degree must be recognized and quantized to clarify the number of resources sharing a given FGS. The degree will support the decisions that whether the resource should be alternative or not if resource conflicts arise.

Thus, in this article, the Function-Shared-Degree (FSD) concept is introduced to indicate the degree to which a machine has exclusive functions. The higher the FSD, the more exclusive functions a machine has. According to the meanings of FSD, the transformation algorithm of RE can be revised to calculate the FSD of every manufacturing resource as follows:

According to the FGS definition, all the manufacturing resources are represented as a collection of FGSs.

Select manufacturing resource $M_{k}$

M_{k} = (m_{1 k} f_{1}, m_{2 k} f_{2}, \dots, m_{ik} f_{i}, \dots, m_{nk} f_{n})

Select FGS $f_{j}$ , $m_{jk} = 1$ .

Select manufacturing resource $M_{l} (l \neq k)$ .

If $m_{jk} = m_{jl} = 1$ , then $N_{j}^{k} = N_{j}^{k} + 1$ .

Repeat Steps 4 and 5 for all $l = 1, 2, \dots, m$ .

Repeat Steps 3–6 for all $j = 1, 2, \dots, n$ .

Calculate the FSD ( $ρ_{S}^{k}$ ) of the manufacturing resource $M_{k}$

ρ_{S}^{k} = \frac{\sum_{j = 1}^{n} \frac{1}{N_{j}^{k}}}{n}

(4)

Repeat Steps 2–8 for all $k = 1, 2, \dots, m$ , get the FSD of every manufacturing resource.

Using the calculation procedures, the FSD values of the resources shown in Figure 1 can be obtained as shown in Table 1.

Table 1.

The FSD of the machines.

	Machine 1	Machine 2	Machine 3	Machine 4
FSD	0.28	0.17	0.5	0.06

FSD: Function-Shared-Degree.

It is apparent to the manufacturing resources that the value should be located within a range. If there is no function in a resource similar with other resources, the value equals to 1; otherwise, the value must be less than 1. Along with the incensement of the similar functions, the value will decrease and tend to 0. Thus, the range is $(0, 1]$ .

Pheromone concept

With the FGS concept, the similar and exclusive functions can be recognized to facilitate task allocation and static process plan. However, in real-time scheduling, things can be more complex.

For example, some resources are selected according to the processing cost required to handle the task. The manager does not know whether the decision is positive in the future because static processing plan is drafted according to the current manufacturing system parameters. In real-time scheduling, all the parameters may vary over time. Especially for multi-function machines, if they are selected to finish a process with a shared function, they cannot be used to handle other processes which may be an exclusive function in the future. If they are not considered, perhaps higher cost machines are selected with increased total cost. Therefore, the processing cost and the FSD should be combined and dynamically considered.

To tackle the problem, according to the swarm intelligent approach, the pheromone concept in the ant society is introduced into the proposed model. Pheromone is a secreted or excreted chemical factor that triggers a response in members of the same species. According to the pheromone quantum, ants can transmit the information to guide a correct route when the ants are foraging. In addition, the pheromone quantum will evaporate over time to decrease its influence on the other ants considering voiding the ants located in local optimization. Pheromone concept and colony optimization have been applied to the manufacturing system control.^28–33 Wang et al.²⁸ present that the pheromone quantum of manufacturing cell is calculated inversely proportional to the cost to guarantee a minimal cost to process the orders. But its definition and formulation are entirely different from the pheromone concept proposed in this article. Other references mostly use colony algorithm to handle the combination optimization problems in the manufacturing systems.^29–33

Tasks can be regarded as an active ant, and production processes can be viewed as foraging procedures. When the task arrives, an ant is created to look for the adequate resources according to the pheromone quantum. The higher the pheromone quantity, the higher the chance of selection. If a resource is selected, its pheromone quantity will be reduced to decrease the chance in the next resource selection. According to the actual production scheduling and the characteristics of VCMSs, pheromone concept should satisfy the following conditions:

The pheromone should be related to processing cost. It is obvious that the task should select the resources with lower costs. Some resources with lower costs perhaps will be queued later because they can handle other procedures. If a task arrives later, it can be selected rather than being taken up.

The pheromone should be related to utilization rate. The resources with high utilization rate should not be selected because overloading will cause congestions and possible shutdowns. The system requires a trade-off between FSD and utilization rate. The resources with high FSD should maintain middle utilization rate in order to deal with the conflicts and errors.

In summary, the pheromone quantum should be related to FSD, cost per time and utilization rate. However, if the pheromone quantum is always maintained, the manufacturing system will not perform better because the most selected resources only have medium processing cost and utilization rate. Hence, the pheromone should evaporate over time in order to decrease their influence on the resource selection decision. The formulation of pheromone quantum can be represented as follows

P_{j} = (1 - ρ) • \frac{FS D_{j}}{(U t_{j} • C_{j})}

(5)

ρ = f (t) • \frac{N S_{j}}{N}

(6)

where $P_{j}$ is the pheromone quantum of resource $j$ , $C_{j}$ is the cost that resource j processes per time, and $U t_{j}$ is the utilization rate of resource $j$ . $ρ$ is the evaporation factor which changes over time, and it is related to the probability of selection. $N S_{j}$ is the number of selection of resource $j$ and $N$ is the number of selection decisions.

Hybrid control architecture

Regardless of the modeling technology adopted in the CF problem, in the production scheduling phase, VCMSs tend to be so complicated that the current control mechanism cannot efficiently master the behaviors of the resources. In addition, although the resources are modeled using FGS approach and nonlinear relationship is transformed as linear relationship, demand conflicts may still exist with the multi-function resources. Therefore, easy-to-operate and efficient control mechanism is less time-consuming and more appropriate than the other formal and graph theories, particularly for real-time scheduling. As a prerequisite, a powerful and flexible control architecture is required.

Thus, a hybrid control architecture based on multi-agent technology, as shown in Figure 3, offers a promising way for coordinating and scheduling tasks and resources in VCMSs. In this figure, ECM and ICM represent explicit and implicit coordination mechanisms, respectively. In the proposed architecture, there are four types of agents, that is, Coordination agent, Task agent, VC agent, and Resource (Res.) agent, which correspond to the entities in VCMSs.

Figure 3.

The control architecture based on multi-agent technology.

In the control architecture, when a task begins its process, it first enters the buffer queue of the corresponding VC agent. In the queue, there are different task agents waiting to be processed. The coordination agent will rank the task agents according to their priorities in a task ranking procedure which calculates the processing times and order due dates. The coordination mechanism will be designed to ensure every task can be completed by the due date with the objective of maximizing the income.

Besides, resource conflicts may occur when more than one task require a VC at a given time. The manager will select the candidate resources to finish the process. The procedure is easy when there are many suitable candidates. However, the manager does not know whether the decision is positive in the long run because static processing plan is drafted only based on the current manufacturing system parameters. It is appropriate to keep the utilization rate of resources at a steady level in order to avoid production stoppages due to overloading. Thus, the procedure is called as resource load-balancing in which requests for re-selection are sent to the VC agents with the conflict resource when a conflict arises. The corresponding VC agents then send the details to the coordination agent which in turn would judge the pheromone quantum of all the alternative resource agents and decide the resource to be selected.

Coordination mechanism

In the section, the real-time scheduling problem is divided into two sub-problems, that is, task ranking and resource load-balancing. Using the revised RE approach proposed in the former section, the coordination mechanism can be designed to help select adequate tasks and solve the conflict errors either explicitly or implicitly.

Task ranking problem with the ECM

In the section, an ECM is proposed to solve the task ranking problem mainly considering the cost factors which are directly related to the performance of VCMSs. The exact total cost including processing cost, holding cost and penalty cost is hard to obtain because penalty cost is incurred only when a task is overdue, and the holding cost is negligible compared with the processing cost for a given task. In addition, this calculation procedure is improper and time-consuming in real-time scheduling. Thus, a calculation approach related to processing times and order due dates is introduced to determine the ranking priority of conflicting tasks.

$t_{i}^{due}$ : the due date of task i	$C_{j}^{i}$ : the unit cost that task i processed by the resource j
$t_{cur}$ : current time	$c_{j}^{i}$ : the unit cost per unit time that task i processed by the resource j
$t_{i, j}^{M}$ : the processing time that task i processed by the resource j	$C_{total}^{i}$ : the total production cost of task i
$r_{j}^{i}$ : the priority index that task i processed by the resource j.

where

C_{j}^{i} = c_{j}^{i} • t_{i, j}^{M}

(7)

C_{total}^{i} = \sum_{j = 1}^{n} (c_{j}^{i} • t_{i, j}^{M})

(8)

The calculation procedures are given as follows:

Calculate the remaining due date of tasks, represented as $t_{j}^{r}$

t_{j}^{r} = t_{j}^{due} - t_{cur}

(9)

Calculate the cost percentage of task i processed in machine j in the total processing cost, represented as ${CP}_{j}^{i}$

{CP}_{j}^{i} = \frac{C_{j}^{i}}{C_{total}^{i}}

(10)

Get the priorities of every task processed in machine j, represented as $r_{j}^{i}$

r_{j}^{i} = \frac{{CP}_{j}^{i}}{t_{r}} = \frac{c_{j}^{i} • t_{i, j}^{M}}{(t_{j}^{due} - t_{cur}) • \sum_{j = 1}^{n} (c_{j}^{i} • t_{i, j}^{M})}

(11)

Rank the tasks according to $r_{j}^{i}$ .

According to the priority calculation, the detailed coordination procedures shown in Figure 4 are explained as follows:

Step 1. Task agents first enter the buffer queue of the VC agent with the parameters including due date and processing cost.

Step 2. The buffer queue will trigger a calculation of the priorities with the help of coordination agent. The calculation will face all the task agents in the queue.

Step 3. The coordination agent sends the priorities to the buffer queue, which will rank the task agents based on their priorities.

Step 4. The highest priority task agent will be noticed for winning the selection. It should be noted that there are some parallel processes which can be manufactured earlier or later. It means that the task agent may be ranked in the queues of two or more VC agents. In view of this situation, the selected task agent should be locked for the VC agent to avoid the task agent being selected by other VC agents.

Step 5. The selected agent enters the VC agent to finish the process. In these steps, all the queues located in every VC agent will be calculated again when the new tasks arrive, and the queues will be refreshed sporadically.

Figure 4.

The explicit coordination mechanism.

With the ECM, every task can be completed by the due date with the objective of maximizing the incomes. Especially, the rank of the same task is different in the queues of different VCs because the parameters related to the priority calculation are dynamically changed.

Resource load-balancing problem with the ICM

The implicit mechanism improves VCMSs in an indirect way. For the resource load-balancing problem, the objective of ICM is to allocate tasks to the lower processing costs with few-function-shared resources, which are related to the pheromone quantum of resources. The objective is not directly related to the total cost but keep the utilization rate of resources at a steady level in order to avoid production stoppages during resource overloading and rush orders. Thus, the implicit coordination procedures shown in Figure 5 can be explained as follows:

Step 1. When the resource conflicts or error occur, the resource agent will send the notice to coordination agent. The information includes the error type, required maintain time, and the task agent affected.

Step 2. The coordination agent will judge which function is needed to finish the process of the task agent affected. The required function information will be send to all the resource agents with the representation of FGS.

Step 3. The resource agents will select the candidate agents through judging whether they include the FGS or not, in which the busy resources will be excluded.

Step 4. The pheromones of the resource agents are calculated according to the current utilization rate, processing cost per time unit, and FSD property with the help of coordination agent.

Step 5. The high-priority resource agent will be selected to finish the influenced task, and the information will be sent to coordination agent.

Figure 5.

The implicit coordination mechanism.

With the ICM, the resource conflict problem can be solved according to the real-time parameters of the production systems.

The integration coordination approach and communication mode

From the abovementioned presentation, the ICM and ECM handle the task ranking and resource load-balancing problems, respectively. The implicit mechanism considers improving the productivity of the resources, and the explicit mechanism assures that every task can be completed during the due date. Thus, a communication approach is proposed to integrate these two mechanisms to realize the real-time scheduling, in which there are two kinds of communication mode: Point-to-Point (P2P) and Subscribe/Publish (SP) mode (Figure 6):

All the task agents will enter in the task buffer in response to the real production task buffer according to the first-in first-out (FIFO) sequence rule. When the buffer accepts the message sent from the idle resources with the SP mode, the tasks in the buffer processed by the resource will be pushed into the ECM.

ECM calculates the priorities of tasks according to the aforementioned procedures and sends the winner task agents to the VC agents with the P2P mode.

The coordination agent monitors the operation of the VC agent collection. The monitor behavior includes operation completed, operation interrupted, and operation resumed.

When the interruption arises, the VC agent will notice the ICM with the interruption information including the interrupted resource and the interruption category with the P2P mode. ICM judges whether the resources can be maintained rapidly. If yes, the emergency information will be saved for the future reference and all the tasks waiting for the maintaining of the resource. If not, the ICM agent selects the adequate candidate resource according to the abovementioned ICM procedure with the SP mode. In the step, some ant agents are created to help calculate the pheromone quantity of the resource agents.

When the ECM or ICM operates one time, the coordination agent will update the states and parameters of resources and tasks for the next operation.

Figure 6.

The integrated communication mode.

The integration coordination approach and communication mode considers synthetically the task and resource information to realize the dynamic and real-time scheduling, especially rapid response to the operation interruptions. To the actual manufacturing system, the multiple objectives can be introduced to the priority calculation of ICM and ECM according to the system requirement in order to assure that the final priority assignment meets the overall need of the manufacturing system.

Illustrative examples

Production system definition

In this section, a factory producing automobile axles is introduced to demonstrate how the proposed coordination mechanism works. Because the latter processes of axles are finished in flow-shop floor which cannot represent obviously the performance of VCMSs, the former processes completed in the job-shop floor are used for the experiments. The detailed information about the machines and corresponding processing costs are shown in Table 2. The holding costs and rough arrival distribution of tasks are shown in Table 3. It should be stated that owing to seasonal demand, the regression of arrival distribution is not very accurate. Thus, in the simulation experiments, the real order data of a whole year are directly imported into the simulation platform.

Table 2.

The machines and corresponding processing costs (PC) per hour.

Name	Q	Symbol	PC	Name	Q	Symbol	PC
Mechanical Press 110T	1	M1	4	100T Hydraulic Press	1	M7	9
Mechanical Press 160T	1	M2	5	Shearing Machine 13*2500	1	M8	7
Mechanical Press 200T	1	M3	5.5	Shearing Machine 20*2500	2	M9,M10	9
2000T Hydraulic Press	2	M4,M5	11	Semi-auto Band Sawing Machine	2	M11,M12	13
1250T Hydraulic Press	1	M6	10.5	Band Sawing Machine	1	M13	15

Table 3.

Holding costs (Hc) and arrive distribution of tasks.

Name	Hc	Task arrive distribution per day
Task 1	0.02	30 + 168 * BETA(0.923)
Task 2	0.02	8 + WEIB(36.6, 1.67)
Task 3	0.01	4 + ERLA(20.8, 3)
Task 4	0.01	70 + WEIB(110, 1.75)

Using the CF approach proposed by Liang et al.,²⁵ the production system is initially divided as five VCs, which are shown in Table 4. Along with the arrival of new tasks, the VCs will change their members.

Table 4.

VCs and the corresponding manufacturing resources.

Name	Manufacturing resources
VC A	M1,M2,M3
VC B	M4,M5,M6,M7
VC C	M8,M9,M10
VC D	M11,M12
VC E	M13

VC: virtual cell.

All the information is used to model the simulation platform using the Simio software (Version 3.0). The layouts of interface of the factory including the job-shop floor and flow-shop floor are shown in Figure 7.

Figure 7.

The simulation interface of the factory.

After 30 iterations, the average throughput of the factory is shown in Table 5. Other indexes are shown and discussed in the next section.

Table 5.

The average throughput (TP) of the factory.

Tasks	Task 1	Task 2	Task 3	Task 4
TP (month)	5545	16,051	14,847	14,839

Performance analysis and discussions

In the section, the indexes obtained from the simulation platform will be compared with the current production indexes of the real factory to test the performance of the proposed mechanism.

Utilization rate and productivity

In traditional manufacturing systems, the utilization rates of manufacturing resources are calculated with the used time divided by the total time. To avoid overloading, the utilization rates should be maintained adequate. However, in the proposed mechanism, the utilization can be viewed as a collection of utilization rates of FGS, which is not only time-dependent but also function-related. For example, for manufacturing resource, its rate can be calculated as follows

U r_{k} = \frac{T_{used}}{T_{total}}

(12)

In the proposed mechanism, it can be calculated as

\begin{matrix} M_{k} = (m_{1 k} f_{1}, m_{2 k} f_{2}, \dots, m_{ik} f_{i}, \dots, m_{nk} f_{n}) \\ U r_{k} = \sum_{i = 1}^{n} m_{ik} \frac{T f_{used}}{T f_{total}} \end{matrix}

(13)

The same utilization rates to process Tasks 1 and 2 are different for the manufacturing resources, which may result in the different productivity or the total costs. So, when scheduling multi-function machines, some implicit production capacity can be mined with the proposed mechanism.

For example, in the traditional control mechanism, the utilization rate of resource $M_{i} (f_{1}, f_{2})$ is 70%, but in the proposed mechanism, the rate can be 80% which includes 50% contributed to $f_{1}$ and 30% contributed to $f_{2}$ .

It can be observed from the simulation result that using the proposed mechanism, average throughput increases by 1.14% as shown in Table 6, and the average utilization rate is improved from 34.2% to 47.3% as shown in Table 7. Especially for the multi-function resources, the utilization rates increase more remarkably.

Table 6.

The comparison of throughput per month.

Tasks	Before	After	Improved rate	Average rate
Task 1	5134	5545	1.08	1.14
Task 2	13,837	16,051	1.16
Task 3	12,373	14,847	1.2
Task 4	13,614	14,839	1.09

Table 7.

The comparison of utilization rates.

State	A1	A2	A3	B1	B2	B3	B4	Average
Before	40.80%	28.50%	19.40%	29.30%	15.30%	7.30%	0.00%	34.2%
After	56.60%	39.50%	26.90%	40.60%	21.20%	10.10%	0.00%	47.3%
State	C1	C2	C3	D1	D2	E
Before	58.70%	51.40%	44.70%	57.50%	51.90%	38.60%
After	81.40%	71.20%	61.90%	79.60%	71.90%	53.40%

The processing cost and holding cost

Iterative optimization during evolution is the inherent characteristics of ACO, thus pheromone is benefit for the continuous optimization of VCMSs. The trend of the processing cost per task is shown in Figure 8, in which the vertical axis represents the ratio of the cost per task of every month divided by the cost per task of first month, and horizontal axis expresses the months in a year. It can be observed that the ratio is keeping a falling trend, besides in some special month the seasonal orders leading it with slight fluctuations. In addition, the waiting time of the tasks is reduced by 12.6% and holding cost is reduced by 22.3%.

Figure 8.

The trend of the processing cost per task.

In the proposed mechanism, if some resource is free, the VC agent will send a signal to the buffer queue and allow the first task to enter the VC. Other tasks are not permitted to enter the VC if no resources are available. If the task enters VC in advance, it will wait in the buffer queue of some resource agents. When another resource agent finishes its task earlier before the waiting agent is ready, the task cannot be processed immediately, resulting in an increase in the holding cost.

In addition, in traditional control mechanism, the multi-function resources are fixed alternative of a resource. In the proposed approach, the production capacity of resources can be efficiently used, and especially if permitted and adequate, the multi-function resources can be flexible alternative for the different single-function resources. The potential Available-to-Promise (ATP) will be excavated to reduce the holding and processing costs when the resources conflicts arise, resulting in a reduction in total cost.

Rapid response to interruptions

Interruptions will influence the designed production planning and task assignment, resulting in a delay of sequential tasks and increase in the total costs. Thus, a rapid response to the interruptions can reduce the negative impacts and help the production system return the established mechanisms as soon as possible as shown in real-time scheduling.

Rapid response means timely identifying the interruption reason and deciding the adequate solution. For the first term, all the reasons have been defined in the knowledge-base. When an interruption occurs, the production system will identify the reason according to the features collected with the P2P communication mode of the coordination agent. For the second term, in the traditional production system, every resource has its fixed alternative resources determined in the process planning. The system will change its resources in the operation of processing, such as purchasing, scrapping, and assigning equipment to other cells. Hence, the resources must update the alternative collection and change the corresponding communication destination. With the proposed mechanism, if the production system changes its resources configuration, the resources including the FGS can be also sent to the information accurately with the SP communication mode not requiring updating the fixed alternative resources collection and the corresponding communication destination. In the floor shop, reasons of interruption can be roughly divided into six categories as shown in Table 8.

Table 8.

The reasons and successful solution times of interruption.

Reasons of interruption	Interruption times	Successful solution times
Operator fault	35	32
Task conflict	28	24
Design bug	49	27
Machine shutdown	19	16
Wrong material	17	14
Unexpected disturbance	8	4

With input from the manager, the successful solution is defined that the interruption can be identified and solved in 15 min. It can be observed that besides the interruptions from design bug and unexpected disturbances, most interruptions can be solved timely and their impacts are mostly reduced by identifying the reasons and selecting the adequate candidate resources on time. For the design bug, the objective of real-time scheduling is to rapidly identify the design reason. As for how to handle the interruption, it belongs to the product redesign period. For the unexpected disturbance, it is so hard to identify and solve it for all the scheduling approaches that the manager thinks that a 50% successful solution rate is acceptable and encouraging.

Furthermore, the tasks are permitted to enter into the VCs only after receiving the idle signal of resources instead of waiting in the buffer of the fixed resource. Some problems can be identified in advance in order to avoid the task entering into the wrong resources in future.

Conclusion

For the contents of VCMSs, most researchers focus on the CF and EE problems and few research has been carried out on real-time scheduling of VCMSs. In this article, a hybrid control architecture based on multi-agent technology is built to support the coordination mechanism in real-time scheduling of VCMSs. Using the revised RE approach with the pheromone concept, the real-time scheduling problem is divided into task ranking and resource load-balancing and solved by the ECM and ICM, respectively. The P2P and SP communication mode considers synthetically the task and resource information and rapid response to the production interruptions to realize the dynamic and real-time scheduling.

Illustrative examples shows that the proposed coordination mechanism performs more efficiently with reduced processing cost and holding cost and more timely response to the interruptions.

In this article, the machines are modeled and analyzed to improve the performance of VCMSs. However, human resources being the second most important resources in VCMSs should also be considered as an extension of this research to make the proposed real-time scheduling approach more rigorous to further improve the performance of VCMSs. In our article, only cost is considered as the optimal objective. In reality, multiple objectives should be adopted to improve priority calculation of ICM and ECM to yield optimal priority assignment in the overall interest of the entire manufacturing system.

Footnotes

Declaration of Conflicting Interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The work described in this article was substantially supported by Research Grants from National Natural Science Foundation of China (70801037, 71271122) and a grant from General Research Fund (GRF) from the Research Grants Council of Hong Kong (RGC # CityU 113609).

References

Kesen

Toksari

Güngör

. Analyzing the behaviors of virtual cells (VCs) and traditional manufacturing systems: ant colony optimization (ACO)-based metamodels. Comput Oper Res 2009; 36(7): 2275–2285.

Süer

Subramanian

Huang

. Heuristic procedures and mathematical models for cell loading and scheduling in a shoe manufacturing company. Comput Ind Eng 2009; 56(2): 462–475.

Safaei

Tavakkoli-Moghaddam

. An extended fuzzy parametric programming-based approach for designing cellular manufacturing systems under uncertainty and dynamic conditions. Int J Comp Integ M 2009; 22(6): 538–548.

Slomp

Chowdary

Suresh

. Design of virtual manufacturing cells: a mathematical programming approach. Robot Cim: Int Manuf 2005; 21(3): 273–288.

Bhandwale

Kesavadas

. A methodology to incorporate product mix variations in cellular manufacturing. J Intell Manuf 2008; 19: 71–85.

Wei

Mejabi

. A clustering approach for minimizing intercell trips in cell formation. J Intell Manuf 2008; 19(1): 13–20.

Fung

RYK

Liang

Jiang

. A multi-stage methodology for virtual cell formation oriented agile manufacturing. Int J Adv Manuf Tech 2008; 38(7–8): 798–810.

Hamedi

Esmaeilian

Ismail

. Capability-based virtual cellular manufacturing systems formation in dual-resource constrained settings using Tabu Search. Comput Ind Eng 2012; 62(4): 953–971.

Wortmann

Muntslag

Timmermans

PJM

. Customer-driven manufacturing. New York: Chapman & Hall, 1997.

10.

McLean

Bloom

Hopp

. The virtual manufacturing cell. In: Paper presented at the proceedings of fourth IFAC/IFIP conference on information control problems in manufacturing technology, Gaithersburg, MD, 26–28 October 1982.

11.

Gunasekaran

. Agile manufacturing, the 21st century competitive strategy. New York: Elsevier Science, 2001.

12.

Egbelu

. Virtual manufacturing cell formation. Int J Prod Res 2003; 41(11): 2365–2389.

13.

Praveen

Boppana

Deshmukh

. A new approach for formation of virtual cells. Int J Manuf Res 2009; 4(2): 171–188.

14.

Nitesh

Berna

Attila

. A methodology to design virtual cellular manufacturing systems. J Intell Manuf 2012; 22(4): 533–544.

15.

Mansouri

Moattar-Husseini

Zegordi

. A genetic algorithm to multiple objective dealing with exceptional elements in cellular manufacturing. Prod Plan Control 2003; 14(5): 437–446.

16.

Huang

. Solvability of f-complementarity problems with a new exceptional family of elements. Appl Math Lett 2008; 21(12): 1274–1280.

17.

Arikan

Güngör

. Modeling of a manufacturing cell design problem with fuzzy multi-objective parametric programming. Math Comput Model 2009; 50(3–4): 407–420.

18.

Mahdavi

Paydar

Solimanpur

. Genetic algorithm approach for solving a cell formation problem in cellular manufacturing. Expert Syst Appl 2009; 36(3): 6598–6604.

19.

Mak

Peng

Wang

. An ant colony optimization algorithm for scheduling virtual cellular manufacturing systems. Int J Comp Integ M 2007; 20(6): 524–537.

20.

. A clustering-based modeling scheme of the manufacturing resources for process planning. Int J Adv Manuf Tech 2008; 38(1–2): 154–162.

21.

Baykasoglu

Gindy

NNZ

Cobb

. Capability based formulation and solution of multiple objective cell formation problems using simulated annealing. Integrated Manuf Syst 2001; 12(4): 258–274.

22.

Baykasoglu

. Capability-based distributed layout approach for virtual manufacturing cells. Int J Prod Res 2003; 41(11): 2597–2618.

23.

Saad

Baykasoglu

Gindy

NNZ

. An integrated framework for reconfiguration of cellular manufacturing systems using virtual cells. Prod Plan Control 2002; 13(4): 381–393.

24.

Aksoy

Oztürk

. Simulated annealing approach in scheduling of virtual cellular manufacturing in the automotive industry. Int J Vehicle Des 2010; 52(1–2): 82–95.

25.

Liang

Fung

RYK

Jiang

. Modelling approach and behavior analysis of manufacturing resources in virtual cellular manufacturing systems using resource element concept. Int J Comp Integ M 2011; 24(12): 1168–1182.

26.

Mahdavi

Aalaei

Paydar

. Multi-objective cell formation and production planning in dynamic virtual cellular manufacturing systems. Int J Prod Res 2011; 49(21): 6517–6537.

27.

Gindy

NNZ

Ratchev

Case

. Component grouping for cell formation using resource elements. Int J Prod Res 1996; 34(3): 727–752.

28.

Wang

Tang

. Pheromone-based coordination for manufacturing system control. J Intell Manuf 2012; 23(3): 747–757.

29.

Peeters

Brussel

Valckenaers

. Pheromone based emergent shop floor control system for flexible flow shops. Artif Intell Eng 2001; 15(4): 343–352.

30.

Xiang

Lee

. Ant colony intelligence in multi-agent dynamic manufacturing scheduling. Eng Appl Artif Intel 2008; 21(1): 73–85.

31.

Jong

Lai

. Applying ant colony system algorithm in the navigation process for plastic injection mould manufacturing scheduling optimization. Int J Prod Res 2014; 52(9): 2530–2549.

32.

Yildiz

. A new hybrid artificial bee colony algorithm for robust optimal design and manufacturing. Appl Soft Comput 2013; 13(5): 2906–2912.

33.

Ajorlou

Shams

. Artificial bee colony algorithm for CONWIP production control system in a multi-product multi-machine manufacturing environment. J Intell Manuf 2013; 24(6): 1145–1156.

Coordination mechanism in real-time scheduling of Virtual Cellular Manufacturing Systems

Abstract

Keywords

Introduction

Literature review

The coordination mechanism–oriented real-time scheduling

Manufacturing resource modeling based on RE approach

Pheromone concept

Hybrid control architecture

Coordination mechanism

Task ranking problem with the ECM

Resource load-balancing problem with the ICM

The integration coordination approach and communication mode

Illustrative examples

Production system definition

Performance analysis and discussions

Utilization rate and productivity

The processing cost and holding cost

Rapid response to interruptions

Conclusion

Footnotes

Declaration of Conflicting Interests

Funding

References