# Agent Based Resources Allocation in Job Shop with Re-entrant Features: A Benchmarking Analysis

Matteo Mario Savino, Antonio Mazza

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

## To cite this version:

Matteo Mario Savino, Antonio Mazza. Agent Based Resources Allocation in Job Shop with Re-entrant Features: A Benchmarking Analysis. 19th Advances in Production Management Systems (APMS), Sep 2012, Rhodes, Greece. pp.350-358, 10.1007/978-3-642-40352-1_44. hal-01472262

HAL Id: hal-01472262

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

Submitted on 20 Feb 2017

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_2.png" /></figure>
# Agent Based Resources Allocation in Job Shop with Re-entrant Features: A Benchmarking Analysis

Matteo Mario Savino and Antonio Mazza

Department of Engineering, University of Sannio, Benevento, Italy

{matteo.savino, antonio.mazza}@unisannio.it

**Abstract.** Job shop production can be characterized by some unplanned event like re-entrant jobs at a certain stage of the production process. In this case a dynamic allocation management of the resources involved (machines, transporters, etc) can be key factor of success in optimizing some production parameter. The present work studies a multiple objective job shop in which the constraint that a workpiece visits a machine only once is relaxed. The production shop floor has been structured with a Multi Agent System (MAS) able to front dynamically these type of events. A benchmarking analysis is provided to compare the solutions found with other two main dynamic MAS-based systems present in literature.

**Keywords:** Re-entrant Job Shop, Multi-agent system, Resources Allocation Management, Production Scheduling

## 1 Introduction

Flexibility and re-configurability are crucial issues for modern manufacturing system to meet the demand of continuously changing market and customers' requirements. Reconfigurable manufacturing methodologies were proposed in recent years and considered as an effective approach to achieve flexibility and efficiency of manufacturing systems and related services (Brun et al, 2011). In order to implement re-configurability, intelligent manufacturing philosophies, such as Multi Agent Manufacturing, have been used. In such type of approaches the system is reconfigured through a cooperation and negotiation of distributed and autonomous intelligent entities. Agent-based systems technology has generated lots of excitement in recent years because of its promise as a new paradigm for conceptualizing, designing, and implementing software systems. In the Technoware organization to which firms are aiming (Ouzrout et al., 2012) this aspect is particularly attractive to create software operating in distributed and open environments in which problems are essentially of dynamic and stochastic nature. In such context the traditional methods or algorithms like Branch and Bound (BB) and Constrained Based Propagation (CBP) might not be very useful. The aim of the present work is to propose an approach dealing with a dynamic management of a job shop production system featured with re-entrant job possibilities. The cooperation among specific resource agents and a dedicated scheduler agent
has made possible the realization of a flexible approach, which effectiveness has
been benchmarked with other recent system present in literature. In the work, we
consider a variation of the classical job shop scheduling problem, the reentrant job
shop problem, in which it is relaxed the restriction that each job visits a machine only
once in the shop floor. In this context the management of this type of event has been
made with the aim to obtain a new local reschedule of the required resources.

## 2 Background

Resources allocation management involves several tasks related to the allocation of
jobs, or even workers on machines, over a time period to perform a certain manage-
ment tasks (Groover, 2003; Neubert, Savino, 2009). It is a decision-making process
that plays an important role in most manufacturing and service industries (Pinedo,
2005). The most common manufacturing system worldwide is the job shop, which
layout is associated with the production of small volumes/large variety products and
operates in make-to-order environment. A specific job shop problem is the Re-entrant
job shop, originally proposed by Kumar (1993) and considered as the third class of
manufacturing system distinguished from job shop and flow shop (Wang and Lin,
2009). The re-entrant job shop scheduling problem extends the classical model by
relaxing the restriction that each job visits a machine only once (Zoghby et al., 2004).
In this context Fattahi et al. (2011) proposed a bi-objective algorithm which uses the
simulated annealing algorithm for the re-entrant manufacturing systems, in order to
maximize the production rate of the system and minimize the work in process (NP-
Hard class). Wang and Lin, in 2009, proposed to solve the re-entrant job shop system
as an ant colony system, developing an agent based simulation platform. Vinod and
Sridharan (2009) focused on a simulation-based experimental study of scheduling
decision rules, while Zhou et al. (2008) proposed a model combining Discrete Event
System (DES) and Multi-Agent System (MAS) to simulate a real-time job shop work-
ing as a test bed to study the performance of control rules and algorithms in dynamic
job shop scheduling. MAS are characterized by the presence of two or more agents
which interact and work together to perform some set of tasks. An agent may be a
piece of software or a hardware that can perceive any changes in its environment and
act upon through actuators, as for example in the Microgrids (Logenthiran et al.,
2010). MAS have been used to handle both externally and internally driven events
disruptive for the planned allocation of manufacturing resources. Tan et al. (2008)
developed a MAS based Dynamic Resource Allocation Management (DRAM) Sys-
tem in which each agent is specialized in a sub domain. The system was tested and
demonstrated its efficiency in case of unforeseen events like work-pieces delays or
machines breakdown, but it was not tested against the problem of re-entrant jobs.
According to Deng et al. (2008), re-entrant line is considered as one of the most com-
plex manufacturing processes distinguished from job shop and flow shop. To front the
problem they proposed a new model of constructing swarm intelligence on multi-
agent system by applying an ant colony scheduling algorithm (ACSA). Wang and Lin
(2009) presented a simulation model of a re-entrant line which is based on MAS and
HLA (High Level Architecture) in which a new model of constructing an ant algo-
rithm on multi-agent system is proposed to find a satisfactory scheduling scheme.
## 3 Case Study and architecture

The work considers the shop floor of a firm producing power generators, with a job shop layout in which jobs need to be reworked after some external processing. Fig. 1 gives the layout of a part of the shop floor with a bridge crane as transportation resource.

<figure><img src="image_3.png" /><figcaption>Fig. 1. The shop floor</figcaption></figure>

The software agents communicate each other by a Service Oriented Architecture (SOA) and though the Contract Net Protocol (CNP) in order to perform the allocation of the jobs (Pasatcha and Sunat, 2008). CNP plays an important role in the dynamic characteristics of the agent-based system integration framework, providing a mechanism for agents to interact dynamically (Yun et al., 2009). CNP consists of two types of decision makers: i) managers and ii) contractors. A manager seeks a contractor to complete a task. It sends a request to all eligible contractors for getting bids of the task. After receiving the bids from the contractors, the manager awards the task to the best contractor based on certain criteria (Lau et al., 2006). The present Job allocation system uses the following five types of software agents: Job Agent (JA); Scheduler Agent (SA); Coordinator Agent (CA); Resource Agent (RA); Service Facilitator (SF). Fig. 2 shows the system the relationship between the JA, SA, CA, RA and SF.

<figure><img src="image_4.png" /><figcaption>Fig. 2. System architecture</figcaption></figure>

CA receives new manufacturing orders and order changes from the ERP system. For orders where the quantity has been reduced, it reports the state of completion and
quantities of the WIP that are no longer required by the order. CA performs the fol-
lowing actions: 1. Generating a JA for each manufacturing order; 2. Passing relevant
manufacturing order information needed by the JA to manage the completion of the
manufacturing order; 2. Cancelling a JA when the manufacturing order is completed.
Each JA represents a single manufacturing order receiving the following information:
1. *Manufacturing order ID and due date*; 2. *Product quantity*; 3. *A listing of the pro-
cess steps and their corresponding manufacturing lead times*. JA submits a request for
the first process in the manufacturing routing of the product to the SF, which publish-
es the job or service requests. RAs of equipment and transporters that are in operation
requests for the job specifications from the SDF. Upon receiving the job specifica-
tions, each RA will evaluate if it can handle the job request. In the case of a process
job, RAs of process equipment prepare their bids and submit the request to the JA.
After the JA has awarded the process job, it will now submit a service request for
transportation to move the raw materials or Work in Process (WiP) to the process
work centre of the process RA that has just been awarded with the process job, to the
SF. RAs of equipment and transporters will request for the job specifications from the
SF. Upon receiving the job specifications, each RA will evaluate if it can handle the
job request. In this case, as the request is for transportation service, the RAs of pro-
cess equipment will ascertain and realize that they are not suitable for the job. RAs of
transporters will prepare and submit their bids. JA, upon receiving the bids, asks the
SF to remove its request, evaluate the bids, and award the job to the RA that has sub-
mitted the most favorable bid. When a re-entrant job occurs, the JA is informed by the
RA. The JA decides if the current process step should stay with the process equipment
until the equipment is serviced and brought back to operation to continue, or to initi-
ate a re-allocation of the current process step to other available equipment. When a
process equipment or transporter is switched on to start operation, the RA is created.
The RA is destroyed when the process equipment or transporter is switched off. A job
that is awarded to the RA of either a process equipment or transporter by a JA, will be
communicated to the sub-system controller for execution. The sub-system controller
essentially receives job instructions from the RA and periodically sends the job status
and the health condition to the RA. Negotiations are summarized in Fig. 3.

<figure><img src="image_5.png" /><figcaption>Fig. 3. Negotiations</figcaption></figure>
The Scheduler Agent (SA) is created to perform a scheduling rule defined according to a specific need of the firm. SA is used to give a precedence to the re-entrant job by associating a flag to each operation to indicate a manufacturing operation previously performed. Each RA sends its waiting queue of tasks to the SA, which arranges the list according to the scheduling rule assigned. Once applied the scheduling algorithm, the SA answers with the updated order of tasks to be executed on the machine. The full list of tasks of each machine is periodically collected and arranged by the SA. The list is dispatched by the machine creating in the meantime a parallel queue of waiting jobs to be ordered. In this way, it is avoided an undefined waiting of tasks characterized by heavy processing time. In the experimental campaign described in the next section, due to the features of the firm, the scheduling rule which has been applied is the shortest task first. The SA is able to collaborate and communicate with the equipments by the use of its two behaviors, named ReceiveQueue (RQ) and ApproveQueue (AQ). RQ receives the request made from the machine containing the list of tasks present in queue which must be ordered according to a scheduling rule. AQ and RQ can be used to establish the priority rule related to the re-entrant jobs, reducing the delay caused by new re-works. Once the list has been ordered, the SA sends the list to the equipment which made the request in order to allow tasks processing.

## 5 The experimental campaign

In order to test the system an experimental campaign has been conducted with five main scenarios. In this paper, due to space constraints, we present the most interesting one related to the presence of two re-entrant jobs and a fault on a transporter. The results obtained by the demonstrator are compared applying the DRAM of Luo et al (2009), and the Centralized Scheduling Optimization (CSP) function of Savino and Neubert (2009). The shop floor is composed of five machines typologies ($M_1...M_5$) for the execution of six jobs. Each job task $P_i$ is associated to the corresponding $M_i$ Machine. **Errore. L'origine riferimento non è stata trovata.**a and 1b shows a comparison between the three systems (SA, DRAM and CSP) for this first case. Process routing, and results concerning Makespan and Average Tardiness are reported for each system.

<table><caption>Tab. 1a. Benchmarking - Routings</caption><thead><tr><th colspan="3">J<sub>1</sub></th><th colspan="3">J<sub>2</sub></th><th colspan="3">J<sub>3</sub></th><th colspan="3">J<sub>4</sub></th><th colspan="3">J<sub>5</sub></th><th colspan="3">J<sub>6</sub></th></tr><tr><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th></tr></thead><tbody><tr><td colspan="18" style="text-align: center; font-weight: bold;">Product Process Routing (seconds)</td></tr><tr><td>P1</td><td>P1</td><td>P3</td><td>P1</td><td>P5</td><td>P1</td><td>P1</td><td>P2</td><td>P5</td><td>P1</td><td>P1</td><td>P1</td><td>P1</td><td>P5</td><td>P2</td><td>P1</td><td>P5</td><td>P4</td></tr><tr><td>50</td><td>50</td><td>80</td><td>50</td><td>50</td><td>50</td><td>40</td><td>50</td><td>60</td><td>50</td><td>50</td><td>50</td><td>10</td><td>10</td><td>10</td><td>20</td><td>20</td><td>10</td></tr><tr><td>P3</td><td>P3</td><td>P1</td><td>P2</td><td>P2</td><td>P5</td><td>P4</td><td>P1</td><td>P4</td><td>P3</td><td>P5</td><td>P3</td><td>P2</td><td>P1</td><td>P1</td><td>P4</td><td>P1</td><td>P1</td></tr><tr><td>80</td><td>80</td><td>50</td><td>100</td><td>100</td><td>50</td><td>30</td><td>40</td><td>30</td><td>80</td><td>20</td><td>80</td><td>10</td><td>10</td><td>10</td><td>10</td><td>20</td><td>20</td></tr><tr><td>P5</td><td>P4</td><td>P4</td><td>P5</td><td>P1</td><td>P2</td><td>P5</td><td>P4</td><td>P1</td><td>P5</td><td>P3</td><td>P5</td><td>P5</td><td>P5</td><td>P5</td><td>P5</td><td>P4</td><td>P2</td></tr><tr><td>60</td><td>60</td><td>60</td><td>50</td><td>50</td><td>100</td><td>60</td><td>30</td><td>40</td><td>20</td><td>80</td><td>20</td><td>10</td><td>10</td><td>10</td><td>20</td><td>10</td><td>10</td></tr><tr><td>P4</td><td>P2</td><td>P5</td><td>P2</td><td>P4</td><td>P4</td><td>P2</td><td>P3</td><td>P3</td><td>P4</td><td>P2</td><td>P4</td><td>P1</td><td>P4</td><td>P4</td><td>P2</td><td>P3</td><td>P5</td></tr><tr><td>60</td><td>60</td><td>60</td><td>100</td><td>100</td><td>100</td><td>50</td><td>50</td><td>50</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td></tr><tr><td>P2</td><td>P5</td><td>P2</td><td>P4</td><td>P2</td><td>P2</td><td>P3</td><td>P5</td><td>P2</td><td>P2</td><td>P4</td><td>P2</td><td>P4</td><td>P1</td><td>P1</td><td>P3</td><td>P2</td><td>P3</td></tr><tr><td>60</td><td>60</td><td>60</td><td>100</td><td>100</td><td>100</td><td>50</td><td>60</td><td>50</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td><td>10</td></tr></tbody></table>
An additional analysis has been focused on the evaluation of the WiP by considering the average size of each buffer which characterizes a machine. In this case the WiP value represents the number of tasks waiting to be processed in the buffer queue of the machine (Luo et al, 2009).

<table><caption>Tab. 2b. Benchmarking – Delay, Makespan, Tardiness</caption><thead><tr><th colspan="3">J<sub>1</sub></th><th colspan="3">J<sub>2</sub></th><th colspan="3">J<sub>3</sub></th><th colspan="3">J<sub>4</sub></th><th colspan="3">J<sub>5</sub></th><th colspan="3">J<sub>6</sub></th></tr><tr><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th><th>SA</th><th>DRAM</th><th>CSP</th></tr></thead><tbody><tr><td colspan="2">MaxDelay</td><td></td><td colspan="2">MaxDelay</td><td></td><td colspan="2">MaxDelay</td><td></td><td colspan="2">MaxDelay</td><td></td><td colspan="2">MaxDelay</td><td></td><td colspan="2">MaxDelay</td><td></td></tr><tr><td colspan="2">30 sec</td><td></td><td colspan="2">50 sec</td><td></td><td colspan="2">40 sec</td><td></td><td colspan="2">60 sec</td><td></td><td colspan="2">50 sec</td><td></td><td colspan="2">20 sec</td><td></td></tr><tr><td colspan="2">Quantity=1 product</td><td></td><td colspan="2">Quantity=2 product</td><td></td><td colspan="2">Quantity=3 product</td><td></td><td colspan="2">Quantity=2 product</td><td></td><td colspan="2">Quantity=1 product</td><td></td><td colspan="2">Quantity=1 product</td><td></td></tr><tr><td colspan="15">Makespan (sec)</td></tr><tr><td>300</td><td>315</td><td>280</td><td>450</td><td>490</td><td>410</td><td>250</td><td>270</td><td>240</td><td>200</td><td>220</td><td>205</td><td>70</td><td>75</td><td>60</td><td>100</td><td>110</td><td>95</td></tr><tr><td colspan="15">Average Tardiness (sec)</td></tr><tr><td>15</td><td>14</td><td>12</td><td>20</td><td>25</td><td>17</td><td>18</td><td>20</td><td>16</td><td>25</td><td>26</td><td>22</td><td>23</td><td>25</td><td>20</td><td>11</td><td>13</td><td>10</td></tr></tbody></table>

Tab. 3 shows the results obtained with respect to the buffer of Machine 1.

<table><caption>Tab. 3. Average WIP comparison</caption><thead><tr><th rowspan="2">Buffer number</th><th colspan="3">Average WIP [# of tasks]</th></tr><tr><th>SA</th><th>DRAM</th><th>CSP</th></tr></thead><tbody><tr><td>Machine 1</td><td>2.11</td><td>2.43</td><td>2.05</td></tr></tbody></table>

The introduction of the SA allows to reduce of a considerable amount the average WIP with respect to DRAM system: the reduction is around 13%. The scheduling rule aims to give execution priority to those tasks characterized by a low completion time, avoiding an increasing of the tasks in queue. We note also that the centralized structure of CSP allows to obtain a better result by reducing WiP of around 3% with respect to the modified version of DRAM. Fig. 4 shows the trend of the WIP with respect to the execution time of all the jobs for Machine 1.

<figure><img src="image_6.png" /><figcaption>Fig. 4. WIP machine 1</figcaption></figure>
SA scheduler provides good results in terms of WIP level by placing in an intermediate situation and reducing the WIP obtained by the application of DRAM scheduler. A further analysis has been conducted in order to evaluate Makespan distribution obtained by the application of the three schedulers. Fifteen simulation runs have been conducted in order to perform this analysis. The average and the standard deviation of the 15 samples are shown in Tab. 3.

<table><caption>Tab. 3. Makespan - Average and standard deviation</caption><thead><tr><th></th><th>SA</th><th>DRAM</th><th>CSP</th></tr></thead><tbody><tr><td>Average [sec]</td><td>726</td><td>721</td><td>727</td></tr><tr><td>Std deviation [sec]</td><td>20</td><td>33</td><td>18</td></tr></tbody></table>

In spite of the small difference obtained for the average value, SA and CSP allow to obtain an important result concerning the standard deviation which is now reduced of around 50%. This result indicates that the use of SA and CSP schedulers introduce an uniformity of execution times, i.e. a lower time dispersion. In Fig. 8 we show the trend of execution times by subdividing Makespan range into five classes and associating to each of them the occurrences fitting into the same class. The use of SA and CSP reduce time dispersion and allow to thicken values within some grouping classes. The time necessary to complete the negotiation phase is usually very low (few seconds). The simulations conducted allowed to note that in a negotiation phase, when we have minor products but more jobs, this time takes only the 3% on the total time, instead when we have more products but minor jobs it is slightly higher, with a value maximum equal to 9.5%.

## 6. Conclusions

In this paper a MAS model has been applied for the job shop scheduling in a dynamic manufacturing system with the problem of re-entrant job, in order to give to the system the possibility to react to the events occurring in the real scenario. The model has been created first of all by identifying the agents involved in the system. In the systems developed a scheduler Agent determines the order for the execution of requests requiring the use of a specific resource. An analysis on the results of a case study has been conducted to test the behavior of the model under specified conditions and a combination of events. The results showed a good functionality of the system, highlighted by the improvement the main performance indicator, represented the max tardiness, WiP and Makespan. Good results have been obtained also considering job routing, especially if compared with the other two algorithm present in literature which with the benchmarking has been conducted.

## References

1. Deng K., Lin J., Wang F., (2008), *Scheduling of Re-entrant Line Based on Swarm Intelligence*, International Symposium on Knowledge Acquisition and Modeling, KAM '08, pp. 323-328

2. Fattahi P., Tavakoli N., Jalilvand-Nejad A., Jolai F., (2011), *A hybrid algorithm to solve the problem of re-entrant manufacturing system scheduling*,
CIRP Journal of Manufacturing Science and Technology, Vol. 57, No.3, pp.175-197.

3. Groover, M.P. (2003), *Automation, production systems, and computer integrated manufacturing*, Prentice Hall of India Pvt Ltd, New Delhi, India

4. Kutanoglu E. & Sabuncuoglu I. (1999), *An analysis of heuristics in a dynamic job shop with weighted tardiness objectives*, International Journal of Production Research, Vol. 37, No.1, pp.165-187.

5. Logenthiran T., Srinivasan D., Khambadkone A. M. and Aung H. N. (2010), *Multi-Agent System (MAS) for Short-Term Generation Scheduling of a Microgrid*, IEEE ICSET, Kandy, Sri Lanka.

6. Neubert G., Savino M.M., (2009), *Flow shop operator scheduling through constraint satisfaction and constraint optimisation techniques* – International Journal of Productivity and Quality Management 2009 - Vol. 4, No.5/6 pp. 549-568

7. Ouzrout Y., Savino M.M., Mazza A. (2012), *PLM maturity model: A multi-criteria assessment in southern Italy companies*, International Journal of Operations and Quantitative Management, Vol 18 (3), pp. 160-177

8. Pinedo M.L. (2005), *Planning and scheduling in manufacturing and services*, Springer, New York

9. Savino M.M., Brun A. and Riccio C. (2011) *Integrated system for maintenance and safety management through FMECA principles and fuzzy inference engine*, European Journal of Industrial Engineering, Vol. 5, No. 2, pp.132–169.

10. Tan C. H., Luo M., and Zhao Y. Z., (2010), *Multi-agent approach for dynamic resource allocation*, SIMTech technical reports, Singapore.

11. Vinod, Sridharan (2009), *Development and analysis of scheduling decision rules for a dynamic flexible job shop production system: a simulation study*, International Journal of Business Performance Management - Vol. 11, No.1/2 pp. 43-71

12. Wong M. M., Luo M., Savino M. M and Meoli E. (2010), *Dynamic batch scheduling in a continuous cycle-constrained production system*, International Journal of Services Operations and Informatics, Vol. 5, No. 4, pp. 313-329

13. Wang F., Lin J., (2009), *A Multi-Agent Architecture for Re-entrant Manufacturing Line*, IEEE Global Congress on Intelligent Systems pp.3-10.

14. Zhou, Lee, Nee (2008), *Simulating the generic job shop as a multi-agent system*, International Journal of Intelligent Systems Technologies and Applications - Vol. 4, No.1/2 pp. 5 – 33

15. Zoghby J., Barnes J., Hasenbein J., (2004), *Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches*, European Journal of Operational Research, Volume 167, Issue 2, 1, pp 336-348