A Hierarchical Temporal Planning-Based Approach for Dynamic Hoist Scheduling Problems

New industrial paradigms, such as smart factories and the Internet of Things, are becoming increasingly important with the developments of big data and artificial intelligence, greatly improving the efficiency of manufacturing production processes. These advances allow real-time data to be collected for solving different industrial problems, such as the scheduling of hoists widely used for plating processing, printed circuit boards, etc. Scheduling plays a very important role in automated industrial applications of artificial intelligence (Kallrath 2002; Parente et al. 2020), aiming to reduce time costs and increase production efficiency.

One mainstream way to handle hoist scheduling problems is to build optimization models according to constraints, and solve them based on mathematical algorithms, e.g., Mixed-Integer Linear Programming (MILP) (Amraoui and Elhafsi 2016; Feng, Chu, and Che 2018; Laajili et al. 2021a). However, the uncertainties and large scales let constructing and solving mathematical models time-consuming and tedious due to relying on expert knowledge.

Although plenty of approaches have been proven to be effective, there are gaps between current hoist scheduling problems and real-world industrial problems. For instance, cyclic hoist scheduling problems aim at computing fixed moving sequences for hoists with the goal of minimizing cyclic times. However, they (Che and Chu 2004; Che et al. 2014) assume all jobs are available at the loading station waiting for being processed in the beginning, neglecting unexpected arrivals and unfamiliar types of new jobs. Real-time and dynamic hoist scheduling approaches (Amraoui and Elhafsi 2016; Yan et al. 2017; Zhao, Fu, and Xu 2013) are proposed to plan out even if facing unexpected disruptions. However, they have troubles in handling large-scale tasks. Therefore, approaches (Zhao, Fu, and Xu 2013; Yan et al. 2018a) made some assumptions to let problems easier to be modeled, such as the locations of the loading and unloading stations, single-track production lines, and a small number of hoists. Nevertheless, those assumptions are not applicable to all real-world industrial scheduling problems. In other words, mathematical models have to be rebuilt and optimized as long as environments change, intensifying contradictions in real-time scheduling problems between states used for calculations and actual states after running time. Those limitations restrict their real-world application.

Similar to hoist scheduling problems, Automated Planning (AI planning) is adept at computing valid plans with correct logic based on domain knowledge and instance descriptions (Zhuo and Kambhampati 2017; Jin et al. 2022a). Differently, AI planning relies on universal descriptions of domains, including preconditions and effects, focusing on logical relations and rules of updating between actions. Therefore, given initial assignments and achievable goals, planners can compute valid action sequences to guide agents to achieve goals, different from constructing mathematical models based on specified constraints done by previous hoist scheduling approaches. It is, however, challenging to complete large-scale tasks of real-world industrial scheduling with off-the-shelf planning techniques. A potential effective way is to integrate planning techniques into mathematical models-based scheduling framework, with planning techniques dealing with high-level logical relations and mathematical models-abased scheduling techniques dealing with low-level detailed constraints, which benefit from each other in solving the industrial scheduling problem effectively and efficiently.

To do this, we need to deal with three main issues:

• •

  The first issue is that products are dynamically added into production lines, incurring uncertain conflicts.

• •

  The second is that environments may unexpectedly change since some tanks may be broken, which means solutions have to be rebuilt with respect to both previously executed actions and current changed environments.

• •

  The last one is since we need to rebuild new solutions based on a starting state $s_{0}$ (i.e., a snapshot of the environment) while the production line is running based on old solutions, we need to estimate the starting state $s_{0}$ in which the production line starts to execute new solutions (after new solutions are successfully rebuilt).

Considering the above-mentioned issues, we propose a planning-based approach, Hierarchical Industrial Temporal Planner, a.k.a., HIT, to handle real-world real-time hoist scheduling problems. We regard hoist scheduling problems as temporal planning problems, with concurrent and durative actions. We design the domain model according to real-world electroplating production lines, where each action is to operate a hoist, such as moving a hoist from a tank to another one. Specifically, we first generate skeleton schedules by neglecting “detailed” constraints. With the skeleton schedules, we compute action sequences to complete tasks with a temporal planner. To generate reliable guidance, we construct a hierarchical framework, which constructs sub-goals for planning and estimates the time of recomputing sub-goals by an inference mechanism. The hierarchical framework allows HIT to react quickly when unexpected disruptions happen, and handle large-scale searching space.

In this section, we introduce related works from three aspects: (1) cyclic hoist scheduling problems, (2) dynamic hoist scheduling problems, and (3) planning-based scheduling problems. We will describe those aspects in detail below.

In this paper, we define a real-time dynamic hoist scheduling problem by $\mathcal{M}=\langle\mathcal{H},\mathcal{T},\mathcal{O},\rho,\phi,l^{\mathcal{H}},l^{\rho}\rangle$, aiming at computing plans to guide hoists $\mathcal{H}$ running on rails beyond tanks $\mathcal{T}$ to transport products $\rho$ between tanks.

$\mathcal{H}=\{\mathcal{H}_{0},\dots,\mathcal{H}_{m}\}$ is a set of hoists, each of which can perform three actions: move, load, and unload a product. Hoists run on rails beyond numbers of tanks. The location of $\mathcal{H}_{i}$ is denoted by $l^{\mathcal{H}}_{i}$, which is a symbol, either “+” or “-”, joint with a tank, where “+” indicates that the hoist is above a tank and “-” indicates that the hoist is at a bottom position. A hoist $\mathcal{H}_{i}$ is restricted to only move within $\mathcal{R}_{i}=\langle\mathcal{T}_{x},\dots,\mathcal{T}_{y}\rangle$ ($x<y$) including a sequence of neighboring tanks. We denote the transportation time for a hoist moving from $\mathcal{T}_{m}$ to $\mathcal{T}_{n}$ by $\mathbf{m}(m,n)$, and lifting time by $\breve{\mathbf{t}}$, respectively.

$\mathcal{T}=\{\mathcal{T}_{0},\mathcal{T}_{1},\dots,\mathcal{T}_{n}\}$ is a set of tanks, each of which belongs to one of the three types: loading, unloading, and processing tanks. Specifically, loading tanks are used to store products waiting for being processed, processing tanks are used to process products, and unloading tanks are used for storing products which have completed all required procedures. The usage of tank is defined by $\mathbf{P}(\mathcal{T}_{i})=\mathcal{O}_{x}$, where $\mathcal{O}_{x}\in\mathcal{O}$. $\mathcal{O}$ is a set of operations $\mathcal{O}=\{\mathcal{O}_{0},\mathcal{O}_{1},\dots,\mathcal{O}_{k}\}$, e.g., water washing, loading, and exchanging.

$\rho=\{\rho_{0},\dots,\rho_{z}\}$ is a set of products, which are in loading tanks, waiting for being dispatched to tanks according to their processing recipe. They will finally be put into unloading tanks after all procedures have been done. For a product $\rho_{i}$, we define its location by $l^{\rho}_{i}$, which can be a tank or a hoist, indicating a product is in a tank or grabbed by a hoist. The recipe is defined by $\phi_{i}=\langle\sigma_{i},\underline{\tau_{i}},\overline{\tau_{i}}\rangle$. $\sigma_{i}=\langle\sigma_{i}^{0},\sigma_{i}^{1},\dots\rangle$ is an operation sequence which requires to be executed in order, where $\sigma_{i}^{j}\in\mathcal{O}$. $\underline{\tau_{i}}$ and $\overline{\tau_{i}}$ are two sequences constraining processing time of $\sigma$, where processing time of $\sigma_{i}^{j}$ is required to be more than $\underline{\tau_{i}}^{j}$ and less than $\overline{\tau_{i}}^{j}$.

Given $\mathcal{M}$ as input, the goal in this paper is to compute a plan $\Pi$, guiding hoists to transport products between tanks such that products are processed according to their recipes within the required time limit. We define a plan $\Pi$ by a sequence of triples $\langle a,\gamma,\tau\rangle$, where $a$ is an action executed by hoist, including an action name and zero or more parameters. $\gamma\in\mathbf{R}^{0+}$ is a positive real-valued number indicating the starting time of action $a$ . $\tau$ is the duration of action $a$.

Figure 1 shows an example in electroplating lines. As shown in Figure 1(a), the example includes 8 tanks, 3 hoists and 6 products. There are 6 types of operations, including loading and unloading. Tanks can be unavailable, such as $\mathcal{T}_{3}$, which can not accommodate any products. Partial description of the example is shown in Figure 1(b), and the goal is to complete recipes of products following the time requirements. For example, $\mathcal{H}_{1}$ is going to put $\rho_{1}$ into $\mathcal{T}_{5}$, whose operation is $\mathcal{O}_{3}$, the processing time of the third procedure of $\rho_{1}$ is required to be less than 60 but larger than 45. An example plan in the form of action sequences is shown in Figure 1(c), where each action is composed of a starting time, an action with zero or more parameters, and a duration.

In this paper, according to the real application scenario, we assume the following requirements are satisfied:

1. 1.

   Tanks can be available or unavailable in the beginning.

2. 2.

   During scheduling, new products may be added to the task. Once they wait in loading tanks, their recipes and arriving time are known.

3. 3.

   A product only has one operation at a time.

4. 4.

   A processing tank only processes one product at a time, but loading and unloading tanks can contain several ones.

5. 5.

   A hoist only takes one product at a time.

6. 6.

   Tanks keep performing operations. Therefore, the duration of operation is timed as long the product is put into, and it stops when any hoist picks up the products.

7. 7.

   The lifting and transportation times are not negligible.

An overview of HIT is shown in Figure 2. We first compute skeleton schedules from the whole, ignoring some detailed constraints such as hoist collisions. We then generate sub-goals to divide large-scale scheduling problems into small-scale sub-problems. In this paper, we regard sub-problems as temporal planning problems. We manually construct the temporal planning domain model and problem descriptions to represent sub-problems, and exploit a planner, such as TPSHE (Celorrio, Jonsson, and Palacios 2015), to solve them. To solve large-scale problems, we cut the plan and estimate appropriate times by an inference mechanism to recompute sub-goals. We repeat generating sub-goals and computing sub-plans until all products are finished successfully.

In this paper, we ran all of our experiments on a machine with 4.400GHz CPU and 16GB RAM. We set the cut-off time to be 180 seconds, and $\alpha$ to be 2. In this section, we evaluate HIT with two state-of-the-art methods with different settings:

• •

  Feng, Che, and Chu (2015) constructed MIP models and solved them by CPLEX. We denote the approach by SHS and use the first computed feasible solutions.

• •

  We use SHS to compute locally optimal solutions within the cut-off time, denoted by SHS⁺.

• •

  TPP (Micheli and Scala 2019) is a planning-based temporal planner which models industrial problems by temporal planning problems.

In this paper, we evaluate approaches from four aspects: success rate, makespan, CPU time and waiting time. Success rate is the proportion of solved problems. Makespan is the time that elapses from the start of problems to all products completed. CPU time is the time of approaches computing solutions. Waiting time is the time of stopping production lines to wait for computation. We first define five recipes (“loading” and “unloading” are omitted), including operations and required processing time, as shown below:

A: $\langle\mathcal{O}_{1},25,55\rangle$, $\langle\mathcal{O}_{2},200,550\rangle$, $\langle\mathcal{O}_{3},80,150\rangle$, $\langle\mathcal{O}_{4},70,$

$200\rangle$, $\langle\mathcal{O}_{5},90,160\rangle$, $\langle\mathcal{O}_{6},200,400\rangle$.

B: $\langle\mathcal{O}_{1},30,60\rangle$, $\langle\mathcal{O}_{2},60,90\rangle$, $\langle\mathcal{O}_{3},200,400\rangle$, $\langle\mathcal{O}_{4},60,$

$120\rangle$, $\langle\mathcal{O}_{5},200,400\rangle$, $\langle\mathcal{O}_{6},30,120\rangle$, $\langle\mathcal{O}_{7},35,75\rangle$.

C: $\langle\mathcal{O}_{1},20,50\rangle$, $\langle\mathcal{O}_{2},400,800\rangle$, $\langle\mathcal{O}_{3},70,120\rangle$, $\langle\mathcal{O}_{4},90,$

$160\rangle$, $\langle\mathcal{O}_{5},100,120\rangle$, $\langle\mathcal{O}_{6},70,200\rangle$.

D: $\langle\mathcal{O}_{1},25,55\rangle$, $\langle\mathcal{O}_{2},90,160\rangle$, $\langle\mathcal{O}_{4},80,150\rangle$, $\langle\mathcal{O}_{5},70,$

$200\rangle$, $\langle\mathcal{O}_{6},90,160\rangle$, $\langle\mathcal{O}_{7},150,300\rangle$.

E: $\langle\mathcal{O}_{1},25,55\rangle$, $\langle\mathcal{O}_{2},200,500\rangle$, $\langle\mathcal{O}_{3},80,150\rangle$, $\langle\mathcal{O}_{4},70,$

$200\rangle$.

Then we use $\mathcal{N}_{\mathcal{H}},\mathcal{N}_{\mathcal{T}},\mathcal{N}_{\rho}$ to denote the number of hoists, tanks, and products, respectively. Next. we define operations of tanks by $\mathbf{P}(\mathcal{T}_{i})=\mathcal{O}_{i}$, except for $\mathcal{T}_{0}$ and $\mathcal{T}_{\mathcal{N}_{\mathcal{H}}-1}$, which are regarded as the loading and unloading tanks. At last, we define lifting time $\breve{\mathbf{t}}=5$, and transportation time $\mathbf{m}(\mathcal{T}_{i},\mathcal{T}_{j})=|j-i|+4$.

• •

  To evaluate the performance of four methods, we first compared them on problems with different numbers of products based on recipe A.

• •

  To evaluate flexibility when facing unexpected events, we evaluated them on problems with new products randomly joining in. The experiments are built based on Feng, Che, and Chu (2015). We generated problems with $\mathcal{N}_{\mathcal{T}}\in\{8,10,12,14\}$ and $\mathcal{N}_{\mathcal{H}}=1$. We first define $n=U(y_{1},y_{2})$ to randomly selected an integer from $y_{1}$ to $y_{2}$. As for each $\mathcal{N}_{\mathcal{T}}$, we randomly generated 10 problems, including two sets of products: $\rho$ and $\rho^{\prime}$. $\rho$ is a set of products waiting at the loading tank in the beginning, where $\mathcal{N}_{\rho}=U(K/2,K)$. $\rho^{\prime}$ is a set of products joining during running production lines, $\mathcal{N}_{\rho^{\prime}}=U(K/2,K)$. The time to put $\rho^{\prime}$ at the loading tank is defined by $U(0,T_{0})$, where $T_{0}$ is the makespan of finishing $\rho$ computed by SHS. The number of operations is computed by $U(K/2,K)$ and we randomly match operations to tanks, the upper and lower bounds of duration requirements computed by randomly selecting one of the following cases: (1)$\underline{\tau}_{i}^{j}=U(30,90),\overline{\tau}_{i}^{j}=\underline{\tau}_{i}^{j}+U(0,90)$; (2)$\underline{\tau}_{i}^{j}=U(90,150),\overline{\tau}_{i}^{j}=\underline{\tau}_{i}^{j}+U(0,60)$; (3) $\underline{\tau}_{i}^{j}=U(150,270),\overline{\tau}_{i}^{j}=\underline{\tau}_{i}^{j}+U(0,150)$.

• •

  To analysis the limitations, we compared makespan and running time on small-scale problems. We built 8 groups of problems with different $\mathcal{N}_{\mathcal{H}},\mathcal{N}_{\mathcal{T}}$, and $\mathcal{N}_{\rho}$, where each group included 20 random generated problems. Recipes were randomly selected from recipes B, C, D and E.

• •

  At last, to evaluate the performance of HIT in real-world industry, we did experiments with two recipes used in real-world electroplating production lines.

In this paper, we present a novel approach, HIT, to solve large-scale real-time dynamic hoist scheduling problems in reality. Specifically, we first generate skeleton schedules as a guide to compute sub-goals, aiming at dividing large-scale problems into small sub-problems. Then we utilize an off-the-shelf temporal planner to compute detailed sub-plans. Next, we compute appropriate times to recompute sub-goals and plan out for real-world industry. Finally, the hierarchical framework allows HIT to handle large-scale problems and rapidly respond to unexpected events. By conducting experiments on problems with different settings, the experimental results show the superiority of HIT. Currently, the domain model is built by domain experts. In the future, it would be interesting to investigate automatically learning domain models (Zhuo et al. 2010; Zhuo and Yang 2014; Zhuo, Muñoz-Avila, and Yang 2014; Jin et al. 2022b) from historical data collected from industry. Besides, it would be also interesting to consider combining skeleton schedules with more mathematical constraints to get less resource usage.