# A Distributed Production Scheduling Method for Highly-Distributed Manufacturing Systems

Eiji Morinaga, Yuki Sakaguchi, Hidefumi Wakamatsu, Eiji Arai

► To cite this version:

Eiji Morinaga, Yuki Sakaguchi, Hidefumi Wakamatsu, Eiji Arai. A Distributed Production Scheduling Method for Highly-Distributed Manufacturing Systems. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2014, Ajaccio, France. pp.531-538, 10.1007/978-3-662-44739-0_65. hal-01388591

HAL Id: hal-01388591

https://inria.hal.science/hal-01388591

Submitted on 27 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Distributed Production Scheduling Method for Highly-Distributed Manufacturing Systems

Eiji Morinaga, Yuki Sakaguchi, Hidefumi Wakamatsu, and Eiji Arai

Division of Materials and Manufacturing Science, Osaka University
{morinaga,yuki.sakaguchi,wakamatu,arai}@mapse.eng.osaka-u.ac.jp

**Abstract.** Recent development of computer network technologies is realizing highly-distributed manufacturing systems from the hardware point of view, where each facility is computerized and manages itself autonomously by communicating with other facilities. For this new type of manufacturing systems, a new discrete event simulation paradigm has been discussed, in which sorting of events is performed by exchanging messages about their occurrence times among the facilities. To make this paradigm beneficial enough, it is desirable that re-scheduling process performed after the simulation is carried out in a similar paradigm. We have developed some production scheduling methods for flexible flow-shop production of only one kind of products with just one stage. This paper presents an improved method which can be applied to flexible flow-shop of multiple kinds of products with multiple stages.

**Keywords:** production scheduling, distributed method, agile manufacturing

## 1 Introduction

Production scheduling is one of the key issues for achieving sophisticated design, management and operation of manufacturing systems. Numerous works have been conducted for a long time and various approaches have been discussed such as mathematical programming [1], heuristic dispatching methods [2], and so on. For detailed evaluation of a production schedule, simulation needs to be performed. Simulation techniques for manufacturing has been also discussed and many methods has been proposed [3]. Most of those researches have been conducted with the centralized concept in which the whole manufacturing system is modeled and then the optimal schedule is generated or simulation is performed based on it.

These days, it has been desired to realize agile manufacturing, which can adapt to change of situation flexibly and quickly. The centralized concept should not meet this requirement, since it would be hard to re-model the whole system and find the optimal way of management and operation for each new situation. From this point of view, distributed manufacturing systems have been discussed, where each production area is managed by a computer and the whole system is controlled by communications among the computers. In the research field of production scheduling, distributed methods using auction mechanisms [4], active databases [5], etc. have been actively
discussed. Also in the simulation area, high-level architecture was proposed and dis-
tributed methods based on it have been discussed [6].

Recent development of computer and network technologies is achieving highly-
distributed manufacturing systems (HDMSs) from the hardware point of view, where
each facility is computerized and manages itself autonomously by communicating
with other facilities. This point has been discussed in the field of manufacturing simu-
lation, and a new discrete event simulation paradigm for HDMSs was proposed [7]. In
this paradigm, events, each of which is simulated in one of the facilities, are sorted by
their occurrence time and this sorting is performed by exchanging messages about the
occurrence times among the facilities. To make this paradigm beneficial enough, it is
desirable that re-scheduling process performed based on the simulation result is car-
ried out in a similar paradigm. From this point of view, we have proposed a highly-
distributed scheduling method [8-10] in which priority of each facility based on the
shortest processing time (SPT) rule is dynamically updated with indirect decision
making and information control performed by message exchanges. This method was
applied to an example and its fundamental feasibility was proven. However, this
method was developed only for a very simple flexible flow-shop production where
only one kind of products that require only one process are produced, and should be
enhanced so that the method can be utilized in real manufacturing. This paper pre-
sents an enhanced method which can be applied to flexible flow-shop production of
multiple kinds of products which require multiple processes.

This paper is organized as follows: Section 2 provides a brief explanation about the
key concept of the simulation method and the conventional scheduling method for
HDMSs. Section 3 describes an enhanced scheduling method which can be applied to
flexible flow-shop production of multiple kinds of products that require multiple pro-
cesses. In Section 4, feasibility of the proposed method is shown through a case study,
and Section 5 presents conclusions.

## 2 Concept of the Conventional Scheduling Method for HDMSs

In the new discrete event simulation paradigm for HDMSs [7], the following sim-
ple algorithm was proposed for sorting events to be simulated in each simulation
model implemented on each facility. Let assume that there are *N* computerized facili-
ties (agents) each of which has its own simulation model. Each model has its own
event whose occurrence time and priority are *T*ᵢ and *O*ᵢ. Sorting of these events can be
performed by the following three steps:

1. Values of *O*ᵢ of all the events are set to 1, which means the highest priority.

2. Each agent (facility) broadcasts *T*ᵢ as a message.

3. When an agent $A_j$, receives a message from another agent $A_i$, $A_j$ compares its own value $T_j$ with the received value $T_i$. Next, $V_j$ is set to 1 if $T_j > T_i$, and to 0 otherwise. Then $O_j$ is updated to $O_j + V_j$.

Figure 1 shows an example with four agents, and proves that the initial priority se-
quence ($O_i = 1, i=1,...,4$) can be updated to the correct one by the proposed algorithm.
Since each model has several events and a new event is generated after the simulation for the prior event in the model, it is necessary to update the priority sequence. This dynamic determination can be also achieved by algorithms based on the same concept. Therefore the whole simulation can be performed just by message exchanges.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Example of event sorting by the sorting algorithm proposed in [7]</figcaption></figure>

To make this simulation method beneficial enough, it is desirable that re-scheduling process performed based on the simulation result is carried out in a similar way. A major approach for production scheduling is using heuristic dispatching rules. In this approach, a schedule is generated by determining the priority sequence of facilities by the given dispatching rule and then assign a material to the facility with the highest priority. This priority sequence determination is regarded as a sorting process of the facilities according to the rule. Therefore it is expected that a distributed method of production scheduling can be established by applying the above concept and sorting algorithm to this sorting process. We have developed some methods for simple flow-shop production of one kind of products which require only one process, and fundamental feasibility of those methods was proven [8-10]. In order to make those methods practical, it is necessary to develop them further so that they can be applied to real complex production. In the following sections, an enhanced method for flow-shop production of multiple kinds of products with several processes is discussed.

## 3 Enhanced Scheduling Method for Flow-Shop Production of Multiple Kinds of Products with Multiple Processes

In this paper, flexible flow-shop production of multiple stages shown in Fig. 2 is considered. Multiple kinds of materials are transported to the buffer (or automated storage/retrieval system) of the first area one-by-one at various time period. There are several same kind of machines in the area having different performance, and an arrived material is assigned to one of the machines by the shortest processing time (SPT) rule. The material whose first process has completed is transported to the second area and then assigned to one of the machines in the area in the same way.

Each assignment of materials to one of the machines by the SPT rule in each area can be achieved by sorting the machines according to the rule. Therefore, the assign-
ment can be performed by message exchanges among the buffer and the machines by applying the algorithm described in Section 2 to this sorting process (Fig. 3). We have proposed scheduling methods based on this idea by defining procedures for message exchanges among the buffer and the machines and also for updating internal states of them [8-10]. It is possible to enhance the conventional methods so that they can be applied to the production scenario shown in Fig. 2 by improving those procedures.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Considered production scenario</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Materials assignments by message exchanges</figcaption></figure>

The improved procedures for the buffer and each of the machines in each area are shown in Figs. 4 and 5, respectively. The parts described by red symbols and arrows are new components for applying this method to the production scenario in Fig. 2. Variables *P* and *S* were introduced so that each facility can distinguish received mes-
sages by the ID number of process and by the kind of materials, respectively. In addition, variables $B_i$ and $S_i$, which specify static and dynamic priority value of a machine, are defined for each kind of materials. Enhancement for considering multiple processing areas can be easily achieved just by introducing message filters so that a facility execute its own processes only if the received message is for the production process which the facility is in charge. Enhancement for considering multiple kinds of materials can be also achieved easily just by adding the same processes for arranging priority values for each kind of the materials. (Unfortunately, detailed explanations have to be omitted due to page limitation. To understand the processing flows, we would like the readers to read also [8-10].)

<figure><img src="image_5.png" /><figcaption>Fig. 4. Processing flow of a buffer for material assignment</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Fig. 5. Processing flow of a machine for material assignment (This flow is for the case the number of machines in the area is 3.)</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Fig. 5. Continued</figcaption></figure>

## 4 Case Study

The proposed method was applied to an example of flexible flow-shop production of three kinds of materials with two processes. There are three machines in each area and their performance are given as in Table 1. The number of materials is 3 for A, 4 for B, and 3 for C. These materials arrive at the buffer in the first area in each 2 minutes with the order of “AABCCBBBAC”. Figure 6 shows the Gantt chart of the schedule obtained by the SPT rule. The method was implemented on one computer by coding in the C language and performed by using interprocess communication, due to equipment constraints. The same schedule as in Fig. 6 was successfully generated.
<table><caption>Table 1. Processing times of the machines (unit is min.)</caption><thead><tr><th></th><th>1-1</th><th>1-2</th><th>1-3</th><th>2-1</th><th>2-2</th><th>2-3</th></tr></thead><tbody><tr><th>Product A</th><td>5</td><td>6</td><td>7</td><td>5</td><td>6</td><td>7</td></tr><tr><th>Product B</th><td>7</td><td>5</td><td>6</td><td>7</td><td>5</td><td>6</td></tr><tr><th>Product C</th><td>6</td><td>7</td><td>5</td><td>6</td><td>7</td><td>5</td></tr></tbody></table>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 6. Gantt chart of the schedule for the example obtained by the SPT rule</figcaption></figure>

## 5 Conclusion

In this paper, the conventional production scheduling method for HDMSs have been enhanced so that it can be applied to flexible flow-shop production of multiple kinds of materials with multiple processes. Its feasibility was proven by an example. In future works, validness and advantage of this method will be discussed further by illustrations with complex scenario and comparison with conventional methods.

## References

1. Cheng, T.C.E., Gupta, M.C.: Survey of Scheduling Research Involving Due Date Determination Decisions, European Journal of Operational Research 38, 156-166 (1989)

2. Panwalker, S.S., Iskander, W., A Survey of Scheduling Rules, Oper. Res. 25, 45-61 (1977)

3. Carrie, A.: Simulation of Manufacturing Systems, John Wiley & Sons (1988)

4. Kaihara, T., et al.: Optimization Method using Combinatorial Auction for Production Scheduling with Batch Processing, J. Adv. Mech. Design, Sys. Manuf. 4, 588-596 (2010)

5. Matsumoto, T., Kato, Y., et al.: Advanced Autonomous Distributed Manufacturing System Using Active Database, Trans. the Japan Society of Mech. Eng. Ser. C 65, 837-843 (1999)

6. Inukai, T., Hibino, H., et al., Enhanced distributed-simulation using orin and hla, Mechatronics for Safety, Security and Dependability in a New Era, 261-264, Elsevier (2007)

7. Fujii, S., et al.: A Basic Study on A Highly Distributed Simulation of Manufacturing Systems Under The Ubiquitous Environment, Proc. Int. Symp. Flex. Auto., 7208 (2012)

8. Morinaga, E., et al.: A Basic Study on Highly Distributed Production Scheduling, Adv. in Production Management Sys. Competitive Manuf. for Innovative Products and Services, 638-645, Springer Berlin Heidelberg (2013)

9. Morinaga, E., Takagi, A., et al.: A Basic Study on Production Scheduling for Highly-Distributed Manufacturing Systems, Proc. the 22nd Int. Conf. Production Res., 417 (2013)

10. Morinaga, E., Takagi, A., et al.: Basic Study on Production Scheduling Method for Highly-Distributed Manufacturing Systems, J. Adv. Mech. Design, Sys. Manuf., Submitted