# Optimal Scheduling for Automated Guided Vehicles (AGV) in Blocking Job-Shops

Jens Heger, Thomas Voss

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

## To cite this version:

Jens Heger, Thomas Voss. Optimal Scheduling for Automated Guided Vehicles (AGV) in Blocking Job-Shops. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2017, Hamburg, Germany. pp.151-158, 10.1007/978-3-319-66923-6_18. hal-01666164

HAL Id: hal-01666164

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

Submitted on 18 Dec 2017

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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>

Distributed under a Creative Commons Attribution 4.0 International License
Optimal scheduling for Automated Guided Vehicles
(AGV) in blocking job-shops

Jens Heger[0000-0002-4863-5000] and Thomas Voss[0000-0002-2929-954X]

¹ Institute for Product- and Process Innovation, Leuphana University,
Volgershall 1, 21339 Lüneburg, Germany
heger@leuphana.de, voss@leuphana.de*

*corresponding author

**Abstract.** Promising developments and further improvements of cyber physical logistics systems (CPLS) and automated guided vehicles (AGV) lead to broader application of such systems in production environments and smart factories. In this study a new mixed integer linear program (MILP) is presented for the scheduling of AGVs in a flexible reentrant job shop with blocking. Optimal solutions to small instances of the complex scheduling problem in a make-to-order production, minimizing the make span, are calculated. Different numbers of jobs are considered. Feasible schedules for the machines and the AGVs are generated from different sized instances to evaluate the limits of the mathematical model.

**Keywords:** MILP; job shop scheduling; AGV; cyber physical systems

# 1 Introduction

The application of cyber-physical systems (CPS) generate new possibilities and challenges for the production planning and scheduling. Thoben et al. [25] state, that establishing a cyber physical logistics system (CPLS) can increase efficiency and flexibility in the production environment. The combination of smart manufacturing and logistics will generate the optimal value stream to fulfill real-time demands. Supporting that statement Auffermann et al. [3] state, the transportation systems will play an important role in the integration of cyber physical systems. Every production systems needs a flexible and dynamic material handling component. By now forklift trucks are able to identify the transported good and establish a communication to exchange information on the destination where the product wants to go [1]. Due to this fact, new decentral approaches and innovative services need to be established for a one piece flow in a manufacturing environment, especially in small and medium sized businesses considering cellular logistics systems.

These businesses usually use a job shop layout with a number of jobs, each combining a set of operations. These are processed by assigned machines in a job specific sequence. In nearly all instances, material handling systems are used to move, buffer
and store raw material as well as work-in-progress. Those are called Job Shop Scheduling with Material Handling (JSSMH) or Job Shop Scheduling Problem with Transportation (JSPT). Taking into account the type and number of AGVs, picking up materials after an operation is completed and providing it to the next machine, the problem is called Job Shop Scheduling with Autonomous Guided Vehicles (JSP-AGV).

## 2 Problem Description

A job shop is given, if a set of *n* independent jobs *J* = {*J*₁, *J*₂, ..., *J*ₙ} has to be processed on a set of *m* machines with *M* = {*M*₁, *M*₂, ..., *M*ₘ}. Each job *J*ᵢ ∈ *J*, with index *i* for the job and *j* for the operation, can be described as a sequence of operations *o*ᵢⱼ on machine *µ*ᵢⱼ ∈ *M* with the processing time *p*ᵢⱼ. For every operation, a set of machines *A*(*j*) is assigned, which can possibly process it, representing optional parallel machines. The processing order will be called precedence constraint. Once an operation is started, it cannot be interrupted (called preemption) and only one operation can be processed on a machine at a time. Reentrant processes are also considered. They are typical for semiconductor manufacturers or similar production processes with extremely expensive machines. Operations are processed on the same machine twice, with at least one intermediate step in between. This situation occurs, if a product is tested after assembly, repaired and tested again or more than one layer of coating is applied to the product. Exemplarily, Fig. 1 shows the correct sequence of operations with *O*ᵢⱼ₂ on machine *M*ₖ after *O*ᵢⱼ₁ on Machine *M*ₖ₊₁ and *O*ᵢⱼ being processed on *M*ₖ earlier.

Regular job shops consider infinite buffer space between two intermediate operations, one on each side of the machine. In case of absence of the intermediate storage place, the problem can be considered as blocking environment. In the blocking scenario, machines cannot process any other operation until the last processed object has been cleared/unloaded from the machine. The operation of a processed job has to remain on the machine until the next machine is available. This situation is presented in Fig. 1, with *B*ᵢⱼ₊₁ (dashed red box) being the blocking time added to the process duration of *O*ᵢⱼ₊₁. These circumstances will delay the start of the next operation of the upcoming jobs. This situation is well known in industrial environments and commonly found in scheduling train-yards or surgeries in a hospital.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Empty travel times and blocking are considered in the new linear model.</figcaption></figure>

Different optimal solutions to the problem have been presented, for example graph based solutions improved by Branch & Bound (B&B) by Mascis et al. [21] solving a job shop environment with blocking. New approaches to solve the problem with B&B- Algorithms, considering
setup times [14] are known from literature and have been calculated without setup times
on a CPU-GPU combination [8]. A heuristic solution generating a schedule by particle
swarm optimization is provided by Zhao et al. [29]. Using a single criteria tabu-search
[6] or multi criteria tabu-search [20] seems to be promising as well.

Adding transport operations to the job shop problem, the formulation to classify the
environment used by Graham [13] must be enhanced by material transport opera-
tions T<sub>ij</sub>, representing the transportation when o<sub>ij</sub> is processed on machine μ<sub>ij</sub> and o<sub>ij+1</sub>
is processed on machine μ<sub>ij+1</sub>. Also empty travel operations T'<sub>ij</sub> (green dotted box)
have to be considered, subject to the same rules as T<sub>ij</sub>, seen in Fig. 1. Taking into ac-
count the transport operation of an AGV and the absence of a buffer at the machine,
there is a crucial dependency between the schedule of the machine and the AGV. These
can be solved by a nonlinear model provided by Zeng et al.[27], a linear problem con-
sidering assembly and batches [2] and a linear model with handover times reviewed by
Poppenborg et al. [23]. Other mathematical formulations are provided by Caumond et
al. [7] considering a single AGV with limited buffer and Fazlollahtabar considering
multiple AGVs and turning points for deadlock resolution [11]. Given that scheduling
AGVs in a job shop is considered NP-hard due to the simultaneous scheduling problems
(i) of the machines and (ii) the AGVs in the job shop [22] typical approaches are heu-
ristic algorithms. Scholz-Reiter et al. [24] presented a solution for general dual resource
constrained problems dynamically adjusting scheduling rules based on the environ-
ment, which can be adopted to AGVs. Another solution was presented by Ulusoy using
a Genetic Algorithms (GA) for the simultaneous scheduling of AGVs and a Flexible
Manufacturing System (FMS) with 4 workstations [26]. Different hybrid approaches
combining GA with other methods have been tested as well. Another approach pre-
sented by Baruwa is based on colored petri-nets which is providing a fast heuristic so-
lution [4]. Graphical solutions are provided by Lacomme using a memetic algorithm on
a non-oriented disjunctive graph and Zhang using a shifting bottleneck procedure based
on a disjunctive graph [19, 28].

Considering the possible optimization criteria in general, the minimization of the
make span is sufficient [22]. Fazlollahtabar et al. [10] presented the minimization of
the make span (Cmax) as a goal criterion, but considered (weighted) tardiness or the
mean flowtime as minimization criteria as well.

3 Scenario

The considered environment in this paper is a J6, R2|prec, t<sub>jk</sub> = t<sub>kj</sub>, t'<sub>kl</sub> |C<sub>Max</sub> using Graham's notation enhanced by Knust [18]. The scenario and slight variations are commonly used for benchmarking [9] as well as the RoboCup Logistics League (reference http://www.robocup-logistics.org/ for more information). Four machine groups (MG 1-4) with 2 parallel identical machines in MG 1 and MG 3 as well as 2 single machines in MG 2 and MG4 are feed by two AGVs (R1-R2), used for material movements. Each
order consists of 5 transport operations, executed by the 2 AGVs, and 4 machine oper-
ations (one on each group). The considered scenario is depicted in Fig. 2. Scenarios
closely related to this one have been proposed for AGV schedule comparison by [5]
and used by [4, 27]. Instead of combining the load and unload station in one location,
different locations, similar to [23], have been considered for this contribution.

<figure><img src="image_4.png" /><figcaption>**Fig. 2.** In this example the 2 jobs take simple routes through the system, including 5 transport operations.</figcaption></figure>

The products take a certain route (grey and black lines represent different orders), defined by the product type given at the first entrance into the shop. Due to the operation sequence of the given orders, proceeding constraints are assumed. If a machine has processed an operation, it is blocked until the next transport operation unloads the machine. No operation can be substituted by another machine and no operation can be skipped. Machine breakdown and maintenance are not considered. The first operation of each robot is the pickup of a product from a transfer station and making it available to the first machine. As mentioned before, the transport time depends on the layout of the machines. In Fig. 2, transport operations with solid lines are processed by Robot M2 and dashed lines are taken care of by Robot M1. The optimal assignment has to be calculated, see Section 4. The last operation is delivering the final product to the sink (transfer station M9), disposing the product from the shop floor. The movement of the AGV is not bound by any loop or network. The AGV takes the shortest path, calculated on a given map. A transport operation contains the pickup, the transport and the drop off of a product. The loading capacity of the AGV is one object per transport operation. In this paper, the transportation time is considered to be a given amount of time, depending on the position of the machines. Once an AGV has completed the operation and is idle, it stays where it finished the task. Dwell and idle points are not considered in this study. Enhancing the notation of Gröflin [15] with the ideas of Poppenborg [23], leads to a model with reentrant processes, blocking and transfer times as well as the possibility to consider set-up times for each order. The model divides every operation into multiple steps and synchronizes the start of a step with its predecessor's steps. This mixed integer linear model has been used for all following calculations.
## 4 Experimental results

All calculations are done for a static scenario, where all jobs are known prior to the start. For both models, the same set of jobs was considered. Calculation in this case were done on Intel® Core i7-2600 and solved with Gurobi 7.0.2 [16] modelled with AMPL [12]. In Fig. 3 the CPU Calculation times are presented for instances with increasing number of jobs. It can be seen, that with an increasing number of jobs the calculation time increases drastically, as expected.

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** The calculation time increases drastically with the addition of jobs, especially from 5 to 6 orders, resulting in more than 48 h calculations without an optimal solution.</figcaption></figure>

Taking into account the fact that the solver did not find an optimal solution for 6 and more orders after 48 Hours, the solver time limit for all further calculations was set to 120 minutes. During that time, the solver should be able to find a feasible solution but not the optimal answer. This holds up to 10 jobs of the new model, but not for the reference model. After 120 minutes the solver was not able to calculate a feasible solution for 8 and more orders in the reference model. In Fig. 4 the best solution for Cmax is pre-

sented. For all instances with more than 5 orders the feasible solution after 120 minutes (7200 seconds) calculation time and its gap are displayed. The gap is the difference from the last feasible solution to the lower bound, being zero proving an optimal solution. Still these results proof optimal solutions for small instances up to 5 orders.

<figure><img src="image_6.png" /><figcaption>**Fig. 4.** Calculations for more than 5 orders are aborted after 120 minutes, resulting in a gap.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>**Fig. 5.** The larger the instance the longer the first feasible solution takes to calculate.</figcaption></figure>

The development of the gap over time can be seen in Fig. 5. In the figure it can be seen that the time to calculate the first feasible solutions seems to depend on the size of the problem. Increasing the number of AGVs, machines or operations will lead to rising calculation times as well, but the impact has not been tested so far. The detailed convergence behavior will be looked at in the future. The effect of applying dynamical influences to process- and transport times has not been evaluated so far. The different feasible solutions and gaps due to the different notation of the models, which can be seen in Fig. 4, have to be analyzed as well.

# 5 Outlook and Conclusion

Considering a small process like a flexible manufacturing system with no more than 4 machine groups and 2 AGVs, the developed MILP provides an optimal near real time solution for online applications, up to 4 orders in the system. Considering 5 to 10 orders, feasible but not optimal solutions can be presented within reasonable time frames. This shows the amount of orders as a crucial variable to the problem. The usage of powerful solvers and the use of cloud infrastructure can improve the results to a certain extent. It has to be taken into account, that real complex production systems can contain multiple FMS being supplied by more than two AGVs. This leads to the fact, that this approach can no longer be used for the efficient scheduling of large systems. Concluding, the small amount of orders which can be calculated motivates the search for faster algorithms which can cope with larger amounts of orders.

In further research, it has to be evaluated how the program behaves on a rolling time horizon base, to be able to represent the dynamic behavior of a plant, for example, machine failure or priority order. Moreover, in further research other approaches to the larger instances of BJS-AGV problem, such as dynamic rule-based dispatching of AGV's, have to be considered, developed and evaluated. These new approaches, e.g. Heger et al. [17], can be assessed in comparison to the optimal solution provided by this model.
References

1. Acatech Study: Industrie 4.0 Maturity Index. Managing the Digital Transformation of Companies (2017)

2. Anwar, M.F., Nagi, R.: Integrated scheduling of material handling and manufacturing activities for just-in-time production of complex assemblies. In: International Journal of Production Research 36, 653–681 (1998), doi:10.1080/002075498193624.

3. Auffermann, C., Kamagaev, A. Dr., Nettsträter, A., ten Hompel, M. Prof. Dr., Alex, V. Prof. Dr., Verbeek, K. and Wolf, O.: Cyber Physical Systems in der Logistik. Clustermanagement IKT.NRW. Mülheim an der Ruhr (2013)

4. Baruwa, O.T., Piera, M.A.: A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles. In: International Journal of Production Research 54, 4773–4792 (2016), doi:10.1080/00207543.2015.1087656.

5. Bilge, Ü., Ulusoy, G.: A Time Window Approach to Simultaneous Scheduling of Machines and Material Handling System in an FMS. In: Operations Research 43, 1058–1070 (1995), doi:10.1287/opre.43.6.1058.

6. Bouibede, K., Lakehal, M., Abdelhakim, A.I.: A Tabu Search for the Bicriteria Scheduling Problem of Job-Shop with Blocking (2016), doi:10.1109/ISPS.2015.7244978.

7. Caumond, A., Lacomme, P., Moukrim, A., et al.: An MILP for scheduling problems in an FMS with one vehicle. In: European Journal of Operational Research 199, 706–722 (2009), doi:10.1016/j.ejor.2008.03.051.

8. Dabah, A., Bendjoudi, A., El-Baz, D., et al.: GPU-Based Two Level Parallel B&B for the Blocking Job Shop Scheduling Problem. In: 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 747–755 (2016), doi:10.1109/IPDPSW.2016.14.

9. Deroussi, L., Norre, S.: Simultaneous scheduling of machines and vehicles for the flexible job shop problem. In: International conference on metaheuristics and nature inspired computing, pp. 1–2 (2010)

10. Fazlollahtabar, H., Saidi-Mehrabad, M.: Methodologies to Optimize Automated Guided Vehicle Scheduling and Routing Problems. A Review Study. In: J Intell Robot Syst 77, 525–545 (2015), doi:10.1007/s10846-013-0003-8.

11. Fazlollahtabar, H., Saidi-Mehrabad, M., Masehian, E.: Mathematical model for deadlock resolution in multiple AGV scheduling and routing network. A case study. In: Industrial Robot 42, 252–263 (2015), doi:10.1108/IR-12-2014-0437.

12. Fourer, R., Gay, D.M., Kernighan, B.: AMPL. A Mathematical Programming Language. Boyd & Fraser Danvers, MA (1993)

13. Graham, R.L., Lawler, E.L., Lenstra, J.K., et al.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of Discrete Mathematics 5, 287–326 (1979), doi:10.1016/S0167-5060(08)70356-X.

14. Gröflin, H., Klinkert, A.: A new neighborhood and tabu search for the blocking job shop. In: Discrete Applied Mathematics 157, 3643–3655 (2009), doi:10.1016/j.dam.2009.02.020.

15. Gröflin, H., Pham, D.N., Bürgy, R.: The flexible blocking job shop with transfer and set-up times. In: J Comb Optim 22, 121–144 (2011), doi:10.1007/s10878-009-9278-x.

16. Gurobi Optimization, I.: Gurobi Optimizer Reference Manual, http://www.gurobi.com (2016)

17. Heger, J., Branke, J., Hildebrandt, T., et al.: Dynamic adjustment of dispatching rule parameters in flow shops with sequence-dependent set-up times. In: International Journal of Production Research 54, 6812–6824 (2016), doi:10.1080/00207543.2016.1178406.

18. Knust, S.: Shop scheduling problems with transportation (1999)
19.Lacomme, P., Larabi, M., Tchernev, N.: Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles. In: International Journal of Production Economics 143, 24–34 (2013), doi:10.1016/j.ijpe.2010.07.012.

20.Lakehal, M., Aissani, A., Bouibede, K.: New algorithm of scheduling based on priority rules on machines to solve bi-criteria blocking job shop scheduling problem. In: 12th International Symposium on Programming and Systems (ISPS), pp. 1–8 (2015), doi:10.1109/ISPS.2015.7244978.

21.Mascis, A., Pacciarelli, D.: Job-shop scheduling with blocking and no-wait constraints. In: European Journal of Operational Research 143, 498–517 (2002), doi:10.1016/S0377-2217(01)00338-1.

22.Nouri, H.E., Driss, O.B., Ghédira, K.: A Classification Schema for the Job Shop Scheduling Problem with Transportation Resources: State-of-the-Art Review. In: Silhavy, R., Senkerik, R., Oplatkova, Z.K., Silhavy, P., Prokopova, Z. (eds.) Artificial Intelligence Perspectives in Intelligent Systems, 464, pp. 1–11. Springer International Publishing, Cham (2016), doi:10.1007/978-3-319-33625-1_1.

23.Poppenborg, J., Knust, S., Hertzberg, J.: Online scheduling of flexible job-shops with blocking and transportation. In: EJIE 6, 497 (2012), doi:10.1504/EJIE.2012.047662.

24.Scholz-Reiter, B., Heger, J., Hildebrandt, T.: Analysis of Priority Rule-Based Scheduling in Dual-Resource-Constrained Shop-Floor Scenarios. In: Machine Learning and Systems Engineering, doi:10.1007/978-90-481-9419-3_21.

25.Thoben, K.-D., Wiesner, S., Wuest, T.: "Industrie 4.0" and Smart Manufacturing. A Review of Research Issues and Application Examples (Mini Special Issue on Smart Manufacturing). In: International journal of automation technology 11, 4–16 (2017), doi:10.20965/ijat.2017.p0004.

26.Ulusoy, G., Sivrikaya-Şerifoğlu, F., Bilge, Ü.: A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles. In: Computers & Operations Research 24, 335–351 (1997), doi:10.1016/S0305-0548(96)00061-5.

27.Zeng, C., Tang, J., Yan, C.: Scheduling of no buffer job shop cells with blocking constraints and automated guided vehicles. In: Applied Soft Computing 24, 1033–1046 (2014), doi:10.1016/j.asoc.2014.08.028.

28.Zhang, Q., Manier, H., Manier, M.-A.: A modified shifting bottleneck heuristic and disjunctive graph for job shop scheduling problems with transportation constraints. In: International Journal of Production Research 52, 985–1002 (2013), doi:10.1080/00207543.2013.828164.

29.Zhao, F., Tang, J., Wang, J., et al.: An improved particle swarm optimisation with a linearly decreasing disturbance term for flow shop scheduling with limited buffers. In: International journal of computer integrated manufacturing 27, 488–499 (2013), doi:10.1080/0951192X.2013.814165.