Integrated pallet retrieval and processing in warehouses under uncertainty

Buckow, Jan-Niklas; Goerigk, Marc; Knust, Sigrid Article — Published Version Integrated pallet retrieval and processing in warehouses under uncertainty OR Spectrum Provided in Cooperation with: Springer Nature Suggested Citation: Buckow, Jan-Niklas; Goerigk, Marc; Knust, Sigrid (2025) : Integrated pallet retrieval and processing in warehouses under uncertainty, OR Spectrum, ISSN 1436-6304, Springer, Berlin, Heidelberg, Vol. 47, Iss. 3, pp. 817-855, https://doi.org/10.1007/s00291-024-00806-7 This Version is available at: https://hdl.handle.net/10419/330561 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) OR Spectrum (2025) 47:817–855 https://doi.org/10.1007/s00291-024-00806-7 ORIGINAL ARTICLE Integrated pallet retrieval andprocessing inwarehouses underuncertainty Jan‑NiklasBuckow1· MarcGoerigk2· SigridKnust1 Received: 20 August 2024 / Accepted: 12 December 2024 / Published online: 17 February 2025 © The Author(s) 2025 Abstract We study the problem of integrated pallet retrieval and successive processing in warehouses motivated by a practical company setting. A set of pallets has to be retrieved in a warehouse having a single stacker crane and multiple input/outputpoints, and the goal is to minimize the makespan. Previous research focuses on minimizing stacker crane travel times, while subsequent pallet processing times at the input/output-points are neglected. A distinction is made between a blocking and buffering variant, in which either no or sufficient buffer space is available at the input/output-points to temporarily store pallets there before they are processed. To hedge against uncertainties in the pallet processing times, we additionally apply robust optimization with budgeted uncertainty sets. We develop dynamic programming algorithms for the worst-case evaluation, identify polynomially solvable cases when there is only a single input/output-point, and present mathematical models for the general case with an arbitrary number of input/output-points. Our extensive computational study reveals that the integrated models yield considerable benefits compared to either ignoring the stacker crane travel times or the pallet processing times. We propose heuristic algorithms that provide good solutions for large instances in a short amount of computational time. Keywords Warehouse· Stacker crane scheduling· Multiple input/output-points· Integrated pallet retrieval and processing· Robust optimization· Budgeted uncertainty * Jan-Niklas Buckow [email protected] Marc Goerigk [email protected] Sigrid Knust [email protected] 1 Institute ofComputer Science, Osnabrück University, Wachsbleiche27, 49090Osnabrück, Germany 2 Business Decisions andData Science, University ofPassau, Dr.-Hans-Kapfinger-Straße 30, 94032Passau, Germany 818 J.-N.Buckow et al. 1 Introduction In modern warehouses, automated storage/retrieval systems (AS/RS) are popular to increase the efficiency, where all items are packed into unit-load pallets that are stored and retrieved from the warehouse by an automated stacker crane via specific input/output-points (I/O-points). To obtain an overview of warehouses with AS/RS and different stacker crane scheduling problems therein, we refer to Roodbergen and Vis (2009) and Boysen and Stephan (2016). 1.1 Motivation Optimizing storage and retrieval operations in warehouses with AS/RS is important to minimize costs and ensure a smooth item flow in supply chains. While most publications in that field only deal with warehouses having a single I/O-point, Buckow etal (2024) studied a new stacker crane scheduling problem motivated by a practical setting in a company, where pallets are retrieved in a warehouse with multiple I/Opoints, and employees remove specific items from the pallets for a further production process. In their basic problem variant, both the pallet retrieval sequence and the assignment of pallets to I/O-points have to be determined, and the goal is to minimize the total travel time of the stacker crane to perform all retrievals. We extend the problem studied byBuckow etal (2024) by additionally taking pallet processing times at the I/O-points into account. Our setting is motivated by the same industrial company, where a given set of pallet retrieval requests has to be performed to prepare the next production shift. Their stacker crane starts at a specific depot I/O-point, and each retrieved pallet is allowed to be brought to an arbitrary I/O-point. At the I/O-points, there incur pallet processing times, mainly because removing items from the pallets by the employees takes some time. In addition, some items have to be sawn in half, with one half remaining in the pallet and the other half being needed in the next production shift. These pallet processing times thus vary between different retrieval requests, depending on the item type and quantity removed. To start the next production shift in time, the processing of the last pallet should be completed as early as possible. When the stacker crane reaches an I/O-point, it drops the pallet to be retrieved there and then picks up another pallet to be stored. This is possible because at each I/O-point, the pallet previously processed there is available as a storage request (there usually remain items in the pallets after their processing and they are thus returned to the storage). After reaching an I/O-point, the stacker crane moves to the next pallet to be retrieved and swaps it with that currently held on the stacker crane. Note that the company’s stacker crane can perform such pallet swaps as it has an additional buffer location. Due to these pallet swaps, the storage of the pallets that are returned to the warehouse is performed implicitly and does not need to be considered explicitly. Figure 1 exemplifies the processes in the warehouse of the mentioned company. On the one hand, an example storage layout with three I/O-points and 819 Integrated pallet retrieval andprocessing inwarehouses… possible stacker crane movements for retrieving two pallets are shown in Fig.1a. The leftmost I/O-point corresponds to the depot at which the stacker crane is initially located, and the numbers indicate the order of the stacker crane movements. Each cell represents a storage location and accommodates exactly one pallet. On the other hand, the process of retrieving and storing pallets is illustrated in Fig.1b. After a pallet is retrieved from its initial storage location, the stacker crane brings it to an I/O-point to remove items from it. Note that the I/O-points are placed at the border between the storage and production area. When the item removal is finished, the pallet is returned to the warehouse (but possibly to a different storage location than its initial one) as soon as the stacker crane next reaches the I/O-point after retrieving another pallet. The aforementioned company runs a large high-bay warehouse equipped with a single stacker crane that has an additional buffer location and is thus designed to perform pallet swaps. According to the stacker crane’s manufacturer, there are other industrial firms operating similar warehouses, with mainly metal processors as well as producers of windows and doors being among these firms. All these firms are processing long and heavy items, including rods and metal profiles. Hence, there also seem to be other companies facing a similar problem setting to ours in their distribution centers. Furthermore, note that due to the heaviness of their pallets, the stacker crane’s heightened capacity cannot be used to transport two pallets at once, meaning that pallet swaps are the preferred operating mode. The processing of a pallet at an I/O-point makes it temporarily unavailable and thus impacts the choices of the retrieval I/O-points. We address this setting more accurately by proposing an integrated problem considering both the stacker crane travel times as well as the pallet processing times. Although the approaches presented by Buckow et al (2024) provide feasible solutions for our new integrated problem, they completely neglect the pallet processing times, requiring more complex solution approaches to fully exploit the whole optimization potential. From discussions with planners at the aforementioned company, we know that the processing of some pallets may actually consume more time than originally expected, as unpredictable disruptions occasionally occur when removing items from the pallets at the I/O-points. For instance, the working speeds of the employees differ, and they occasionally take a short break. Moreover, a vehicle required Fig. 1 Exemplary warehouse overview and the processes therein 820 J.-N.Buckow et al. to further transport the removed items may not be available in time. Therefore, we additionally take uncertainties in the pallet processing times into account, handling them by applying robustoptimization. Our integrated problem can be viewed as a parallel machine scheduling problem with transportation considerations and uncertainties. The I/O-points correspond to the machines, the pallets are the jobs to be processed, and the stacker crane travel times are setup times needed to prepare the I/O-points before processing the pallets. Our problem is also related to hybrid/flexible flow-shop scheduling problems, where the stacker crane forms a first stage with a single machine, and the I/O-points correspond to a second stage with multiplemachines. 1.2 Literature Overall, our integrated problem is related to the three research fields of machine scheduling, warehousing problems, and robust optimization. In the following, we delimit our problem in relation to these three research fields, which intersect. There are several studies researching scheduling problems with setup times or transportation considerations (see the surveys by Allahverdi et al (1999, 2008), Allahverdi (2015) andHosseini etal (2024)). However, in contrast to the existing literature, our problem involves a single stacker crane with a transportation capacity of one. Therefore, the setup or transportation time to prepare the processing of a pallet depends not only on the pallet itself, its chosen retrieval I/O-point and its immediate predecessor there, but also on the scheduling decisions of all pallets previously retrieved, making our problem more difficult. In recent decades, supply chain scheduling has emerged as a new research field that links machine scheduling problems with supply chain management decisions (see the book by Chen and Hall (2022)). Several such problems also deal with transportation considerations, and it is usually assumed that goods are produced on machines in a factory and then transported to customers or warehouses. Nevertheless, these steps are reversed in our problem, since the transport of a pallet takes place before it is processed at an I/O-point. Furthermore, in these supply chain scheduling problems with transportation considerations, all machines within a factory are typically modeled as one location, while we assume that both the pallets and the I/O-points can take different arbitrary locations within the warehouse. In flow-shop scheduling problems, a distinction is made between blocking and buffering variants, depending on whether there is sufficient buffer space to temporarily store jobs when their next processing machine is busy (see the survey byMiyata and Nagano (2019)). In many warehouses with AS/RS, there is no buffer space at all at the I/O-points, meaning that the stacker crane must wait until the I/O-point is free again before it can drop off a pallet there (in this case, we call the stacker crane being blocked). Although there appears to be little research dealing with such buffer spaces in warehouses, de Koster etal (2012) and Jiang etal (2022) study manual pick-and-sort warehouses, where picked batches are buffered before they are sorted. While de Koster etal (2012) assume unlimited buffer space, Jiang etal (2022) suppose that the buffer capacity is limited and pickers are blocked if the buffer is full. 821 Integrated pallet retrieval andprocessing inwarehouses… Teck etal (2024) studied a warehouse scheduling problem with processing time variability, where multiple robots are lifting pods from the storage to workstations and stochastic optimization is used in order to protect against the uncertain processing times. Gong and de Koster (2011) conducted a survey on stochastic optimization in warehouse operations in general, and described different sources of uncertainty, which can be both within and external to the warehouse system or the supply chain. For example, the uncertainties within the warehouse include human factors such as labor absence or fluctuations in the working speed. Uncertainties in the supply chain may arise from failures in the shipping equipment like trucks or pallet jacks. As already noted by Gong and de Koster (2011), there remain academic blanks in the field of robust approaches for warehouse operations. Unlike stochastic optimization, the former does not require a probability distribution of the scenarios in the uncertainty set, making it applicable even without such knowledge. For in-depth discussions of the robust optimization paradigm, we refer to the books by Ben-Tal etal (2009), Bertsimas and den Hertog (2022), and Goerigk and Hartisch (2024). Ben-Tal etal (2004) introduced the concept of adjustable robust optimization and applied it to an inventory management problem with demand uncertainty, where some decisions must be made before the realization of the uncertain data, while other decisions can be made after the realization (see also the survey by Yanıkoğlu etal (2019)). Since the survey of Gong and de Koster (2011), there are some further studies on robust optimization in warehouses. Ang etal (2012) examined a robust storage assignment problem with variable supply and uncertain demand. Most papers dealing with robust warehouse operations considered inventory management problems with demand or lead time uncertainty (for instance, see Thorsen and Yao (2015), Jiu (2022), Qiu etal (2022) andSun etal (2024)). Nevertheless, instead of scheduling pallet retrievals, other decisions are optimized in these robust problems, mainly determining periodic inventory review policies. There seem to be no studies on robust optimization in warehouse operations that consider pallet retrieval optimization or uncertain processing times at the I/O-points. The type of robust problem we consider has some similarity to Bruni etal (2017) andBold and Goerigk (2021), who study a resource-constrained project scheduling problem, where the activity durations are subject to budgeted uncertainty. Handling the problem as a robust two-stage approach, the resource allocation decisions have to be made before the uncertain activity durations become known, but the activity start times can be fixed after the realization of the activity durations. 1.3 Contributions In this paper, we study the pallet retrieval and processing problem ( PRPP ), where a given set of pallets has to be retrieved and processed in a warehouse equipped with a single stacker crane and multiple I/O-points. The PRPP can be considered as an integrated problem, generalizing both existing pallet retrieval optimization as well as machine scheduling problems from the literature. Our goal is to minimize the makespan, which is defined as the completion time of the last pallet processed. 822 J.-N.Buckow et al. We also investigate the gain of having buffer spaces at the I/O-points to temporarily store pallets there before they are processed, and distinguish between two problem variants. In the first variant, the stacker crane temporarily blocks when approaching an occupied I/O-point (blocking variant), while in the second variant, sufficient buffer space always allows pallets to be dropped off even at occupied I/Opoints (buffering variant). To protect against uncertainties in the pallet processing times, we additionally incorporate robust optimization into our problem. We assume that nominal values and upper bounds on the possible processing time delays are known by the decision maker. As it seems unlikely that the processing times of all pallets take their worstcase values at the same time, we assume budgeted uncertainty sets, which limit the total number of deviating processing times. We identify special cases of the PRPP with only a single I/O-point, where the integrated problem becomes polynomially solvable (in the blocking case even the robust variant). For the general case with an arbitrary number of I/O-points, we develop mathematical models for the blocking and buffering variant with and without robustness, and present dynamic programming algorithms for the worst-case evaluation, i.e., finding the worst possible objective value under all considered scenarios. Our results show that the integrated consideration of pallet retrieval and processing is crucial to obtain good solutions. Moreover, schedules obtained by our robust models are considerably less vulnerable to delays in the pallet processing times. Having buffers at the I/O-points leads to clear reductions in the makespan. This paper is organized as follows. First, the PRPP and its variants are introduced and formally defined in Sect.2. Afterwards, in Sect.3, we theoretically study the special case with a single I/O-point for both the blocking and the buffering variant, and reveal variants that are solvable in polynomial time. In addition, the general multiple I/O-point case is tackled in Sect.4, for which we develop mathematical models and dynamic programming algorithms for the worst-case evaluation. In Sect.5, it follows a detailed computational study, in which we first investigate the benefits of the newly developed integrated mathematical models in both the nominal and robust cases. Besides, the benefits of having a buffer as well as some heuristics are evaluated. Eventually, Sect.6 concludes thepaper. 2 Problem definition The PRPP can be regarded as an integrated two-stage problem, where the first stage involves retrieving each pallet from its storage location and then moving it to one of the different I/O-points. Once the stacker crane has transported a pallet to an I/Opoint, the pallet is processed there in a second stage with a pallet dependent processing time. Note that the resulting makespan is impacted by both the stacker crane travel times to retrieve the pallets during the first stage, and the pallet processing times during the secondstage. Due to its stages, the PRPP is related to hybrid or flexible flow-shop scheduling problems, where a set of jobs must be processed successively in a series of stages, each stage consisting of one or more machines. In the PRPP , the stacker crane that retrieves 823 Integrated pallet retrieval andprocessing inwarehouses… the pallets forms the first stage with a single machine, while the I/O-points where the pallets are processed correspond to the second stage with multiple machines. However, the key distinction of the PRPP to traditional hybrid flow-shop scheduling problems is that we also tackle transportation considerations: the stacker crane travel times (corresponding to the processing times in the first stage) are not constant per pallet (corresponding to a job), but depend on both the pallet retrieval sequence and the assignment of pallets to I/O-points. As in the case of flow-shop scheduling problems, we consider two different variants for the PRPP . In the blocking variant ( PRPPBl ), the I/O-points have no buffer space, blocking the stacker crane when bringing a pallet to an I/O-point until the processing of the pallets previously brought to the same I/O-point is completed. The stacker crane can then drop off the new pallet and continue to retrieve the next pallet in the warehouse. On the other hand, in the buffering variant ( PRPPBu ), there is sufficient buffer space available at the I/O-points where pallets can be stored temporarily, avoiding idle times of the stacker crane, i.e., it is always possible to drop off a pallet immediately when the stacker crane arrives. Furthermore, the special cases with only a single I/O-point of these problem variants we examine in Sect.3 are denoted by 1PRPPBl and 1PRPPBu , respectively. More formally, the PRPP can be stated as follows. We are given a warehouse withn pallets P={p1,…,pn} ,m different I/O-points Θ={𝜃1,…,𝜃m} , and a stacker crane which is initially located at the depot I/O-point 𝜃Depot ∈Θ (note that our solution approaches can easily be adapted to handle the case of an arbitrary initial location). Moreover, each pallet p∈P is associated with a processing time t(p), where we later assume that these processing times are subject to uncertainty. In total, we have 𝜇=n+m locations L={𝓁1,…,𝓁𝜇} , i.e., a location 𝓁(p) for each pallet p∈P as well as a location 𝓁(𝜃) for each I/O-point 𝜃∈Θ . Note that each storage location corresponding to a pallet can accommodate only a single pallet. For all locations 𝓁i,𝓁j∈L , there are stacker crane travel times 𝜏[𝓁i,𝓁j] . In real warehouses, these stacker crane travel times typically result from a metric, i.e., they are symmetric and satisfy the triangle inequality. However, we do not impose any restrictions on these travel times, resulting in a more general problem setting. We denote by Π the set of all permutations of palletsP, and 𝜋=(𝜋1,…,𝜋n)∈Π corresponds to a specific sequence in which the pallets are retrieved. In addition, let 𝛼(p)∈Θ describe the selected I/O-point to which pallet p∈P is brought and then processed, and 𝛼=(𝛼(p1),…,𝛼(pn))∈Θ n represents an assignment of pallets to I/O-points. The goal of the PRPP is to find both a pallet retrieval sequence 𝜋∈Π and an assignment 𝛼∈Θ n of pallets to I/O-points such that the makespan Cmax∶Π×Θ n → ℝ+ is minimized, i.e., witht being the possibly uncertain processing times parameters and the objective function Cmax being definedas (1) min (𝜋,𝛼)∈Π×Θ n C max (𝜋,𝛼,t), (2) C max(𝜋,𝛼,t)= n max k=1 {sk(𝜋,𝛼,t)+t(𝜋k)} , 824 J.-N.Buckow et al. where for k=1, …,n the value sk(𝜋,𝛼,t) denotes the start time of processing thekth pallet retrieved by the stacker crane. The start time of processing the first pallet retrieved is givenby meaning the stacker crane has to move from its initial location 𝓁(𝜃Depot) to 𝓁(𝜋1) , where the first pallet is initially positioned, and bring it to the chosen target I/Opoint 𝛼(𝜋1) . In the following, for k=1, …,n , we use pred(k)∈{0, …,k−1} to denote the position in 𝜋 of the pallet previously processed at the same I/O-point as pallet 𝜋k , with pred(k)=0 if the pallet at positionk is the first one processed at its I/O-point, and we define s0(𝜋,𝛼,t)=0 and t(𝜋0)=0 . Then, for k=2, …,n , the start time values can be recursively calculatedby where the left term considers the completion time of the pallet previously processed at the same I/O-point, and rk(𝜋,𝛼,t) is the time when the stacker crane has retrieved thekth pallet and brought it to the chosen target I/O-point. Due to the missing buffer space in the case of PRPPBl , the stacker crane must wait at the chosen I/O-point when retrieving a pallet until the processing of the preceding pallet at the same I/O-point is completed. In this scenario, we call the stacker crane blocking, and for k=2, …,n , wehave However, in the case of PRPPBu , a sufficient number of pallets can be buffered at each I/O-point. Hence, the stacker crane can move without any interruptions until all pallets are retrieved, and we have to replace(5)by Example 1 Consider the example instance of the PRPP with n=6 pallets, m=2 different I/O-points and the depot I/O-point 𝜃Depot =𝜃1 as shown in Table1. The pallet processing times are displayed in Table1a, and the stacker crane travel times in Table1b. Assuming the pallet retrieval sequence 𝜋=(p1,p2,p3,p4,p5,p6) and the assignment of pallets to I/O-points 𝛼=(𝜃1,𝜃2,𝜃2,𝜃1,𝜃2,𝜃1) , the corresponding schedules for PRPPBl and PRPPBu are shown in Fig.2 and3. There, the activities of the stacker crane and the I/O-points are visualized, where idle times are represented as hatched area, and blocking times of the stacker crane are drawn as dotted area. In the case of PRPPBl , the stacker crane blocks and has idle times after the processing of the pallets p3 and p5 , since their target I/O-point keeps busy for a while, resulting in a makespan of Cmax =30 . In contrast, there are no stacker crane idle times in the case of PRPPBu , leading to a smaller makespan of Cmax =27 . (3) s1(𝜋,𝛼,t)=𝜏[𝓁(𝜃Depot),𝓁(𝜋1)] + 𝜏[𝓁(𝜋1),𝓁(𝛼(𝜋1))], (4) sk(𝜋,𝛼,t)=max{spred(k)(𝜋,𝛼,t)+t(𝜋pred(k)),rk(𝜋,𝛼,t)}, (5) rk(𝜋,𝛼,t)=sk−1(𝜋,𝛼,t)+𝜏[𝓁(𝛼(𝜋k−1)),𝓁(𝜋k)] + 𝜏[𝓁(𝜋k),𝓁(𝛼(𝜋k))]. (6) r k(𝜋,𝛼,t)=s1(𝜋,𝛼,t)+ k ∑ k � =2 (𝜏[𝓁(𝛼(𝜋k�−1)),𝓁(𝜋k�)] + 𝜏[𝓁(𝜋k�),𝓁(𝛼(𝜋k�))]) . 831 Integrated pallet retrieval andprocessing inwarehouses… at a first glance. In Lemma2, we demonstrate that for each of these resulting TSP instances, there exists an equivalent LTSP instance that can be solved efficiently. Lemma 2 Let I� TSP be a TSP instance with the specific arc costs for all (v,w)∈A and a constant 𝜆≥0 . Then, the LTSP instance I�� LTSP with a��(v)=a(v)+max{0, a(v)−𝜆} and b��(v)=b(v) for all v∈V is equivalent to the TSP instance I� TSP . Proof In the LTSP instance I�� LTSP , each arc (v,w)∈A has the costs It therefore remains to show that the arc costs c�(v,w) of I� TSP are the same as the arc costs c��(v,w) of I�� LTSP for all v,w∈V , which we do using a case distinction. • If b(w)<a(v) , we have • If b(w)≥a(v) and b(w)<a(v)+a(v) , we have where a(v)−𝜆 is equal to max{0, a(v)−𝜆} if a(v) ≥ 𝜆 , and both max{b(w),a(v)+a(v)−𝜆} as well as max{b(w),a(v)+max{0, a(v)−𝜆}} are equal tob(w) if a(v)<𝜆 . • If b(w) ≥ a(v)+a(v) , we have ◻ Recall that the nominal LTSP with 𝜂 nodes is solvable in O(𝜂⋅log 𝜂) , and thus Theorem1 follows by combining Lemmas1 and2. c� (v,w)=c(v,w)+max{0, c(v,w)−𝜆} =max{a(v),b(w)} + max{0, max{a(v)+a(v),b(w)} − max{a(v),b(w)} − 𝜆} c��(v,w)=max{a(v)+max{0, a(v)−𝜆},b(w)}. c� (v,w)=a(v)+max{0, a(v)+a(v)−a(v)−𝜆 } =a(v)+max{0, a(v)−𝜆} =c �� (v,w). c� (v,w)=b(w)+max{0, a(v)+a(v)−b(w)−𝜆} =max{b(w),b(w)+a(v)+a(v)−b(w)−𝜆 } =max{b(w),a(v)+a(v)−𝜆} =max{b(w),a(v)+max{0, a(v)−𝜆}} =c �� (v,w), c� (v,w)=b(w)+max{0, b(w)−b(w)−𝜆} =b(w) =max{b(w),a(v)+max{0, a(v)−𝜆 }} =c �� (v,w). 832 J.-N.Buckow et al. Theorem1 The LTSPR with 𝜂 nodes is solvable in O( 𝜂 3 ⋅ log 𝜂 ) . Proof According to Lemma1, an optimal solution for an LTSPR instance with 𝜂 nodes can be computed by solving at most 𝜂2+1 different nominal TSP instances with a specific cost structure, where according to Lemma 2 each one can be transformed to an equivalent nominal LTSP instance. The nominal LTSP with 𝜂 nodes is solvable in O(𝜂⋅log 𝜂) , resulting in an overall runtime of O(𝜂3 ⋅ log 𝜂) to solve LTSPR . ◻ Given Theorem1, we immediately conclude Corollary1 due to the equivalence of LTSPR and 1PRPPR Bl . Corollary 1 1PRPPR Bl is solvable in O(n3 ⋅ log n) . Overall, our results of the single I/O-point case from this section are summarized in Table3 (both the equivalent problems and their complexities), grouped by the blocking and buffering variant as well as the nominal and robust case. 4 Multiple I/O‑points This section deals with the two general variants PRPPR Bl and PRPPR Bu with an arbitrary number of I/O-points. The two corresponding nominal variants PRPPBl and PRPPBu are already NP-hard as will be demonstrated next, showing immediately that this is also the case for their robust counterparts. Both PRPPBl and PRPPBu involve finding a feasible stacker crane tour as well as a partition of the pallets to the I/O-points (making it impractical to enumerate all possible solutions even on very small instances as there are totally n!⋅mn different solutions). On the one hand, when ignoring the pallet processing times (i.e., t(p)=0 for all p∈P ), we obtain the Retrieval Optimization Problem ( ROP ) studied byBuckow etal (2024), which is a generalization of the TSP and thus already NP-hard. On the other hand, when ignoring the stacker crane travel times (i.e., 𝜏[𝓁i,𝓁j]=0 for all 𝓁i,𝓁j∈L ), only the pallet processing times on the I/O-points are relevant, resulting in the NP-hard scheduling problem P||Cmax . This stresses the complexity of even the nominal variants with multiple I/Opoints, given that they are generalizations of two strongly NP-hard problems. Table 3 Summarized results of the single I/O-point case Variant Nominal Robust Equivalent problem Complexity Equivalent problem Complexity Blocking F2|blocking|Cmax O(nlog n) LTSPR O ( n3log n) Buffering F2||Cmax O(nlog n) Open Open 833 Integrated pallet retrieval andprocessing inwarehouses… Subsections4.1 and4.2 deal with the blocking and buffering case when having multiple I/O-points, respectively. 4.1 Blocking variant We first reveal a mathematical model of the nominal blocking variant PRPPBl in Sect. 4.1.1, before presenting a dynamic programming algorithm for the worst-case evaluation of its robust counterpart PRPPR Bl in Sect. 4.1.2. Finally, in Sect. 4.1.3, a mathematical model of PRPPR Bl integrating the dynamic programming approach is presented. 4.1.1 Nominal case Next, we present a formulation of the nominal problem PRPPBl as mixed-integer linear program (MIP), extending the formulation introduced by Buckow etal (2024) for the ROP by additionally incorporating the pallet processing times. The way the stacker crane travel times are modeled is based on the MIP formulation presented by Goerigk etal (2013) for a bus evacuation problem. Our model has four different variable types. First, the binary position variables xjki receive the value1 if pallet pj∈P is retrieved at position k∈{1, …,n} at the I/O-point 𝜃i∈Θ , and0 otherwise. Second, for k=1, …,n , the variables dk to and dk from represent the stacker crane’s durations to approach thekth pallet retrieved, and bringing it from there to its assigned I/O-point, respectively. Moreover, for k=0, …,n , var iable sk indicates the starting time of the processing of the pallet at positionk at its assigned I/O-point, with k=0 meaning that no pallet is retrieved at all. Finally, variable Cmax corresponds to the makespan of the resulting schedule. ( MIP-PRPP R Bl) (21) min Cmax (22) s.t. n ∑ j=1 m ∑ i=1 xjki =1k=1, …, n (23) n ∑ k=1 m ∑ i=1 xjki =1j=1, …, n (24) d 1 to = n ∑ j=1 m ∑ i=1 (𝜏[𝓁(𝜃Depot),𝓁(pj)] ⋅xj1i ) 834 J.-N.Buckow et al. Given the four variable types presented above, we have the MIP formulation(21)- (33). The objective function (21) minimizes the resulting makespan. Furthermore, constraints(22) and(23) ensure that the stacker crane travel sequence is properly defined, i.e., exactly one pallet is processed at each position and each pallet has to be processed exactly once. Constraint (24) defines the stacker crane travel duration to move from the depot I/O-point 𝜃Depot to the initial location of the first pallet retrieved. Constraints(25) describe the stacker crane travel durations to move from the previous I/O-point visited to the initial location of each of the remaining pallets. Analogously, constraints(26) define the stacker crane travel durations to move from each pallet to its assigned I/O-point. Constraints(27) force the makespan to be larger than all pallet completion times. Additionally, constraints(28) and(29) ensure that the pallet starting times are defined correctly by considering for each pallet both the completion time of the predecessor pallet at the same I/O-point and the stacker crane travel duration. Finally, the variable domains are defined by(30)-(33). The big-M conditions ensure that constraints(28) are only active if both pallets involved are processed on the same I/O-point. Note that hereby all pallets previously processed on the same I/O-point are considered, instead of only using the direct (25) d k to ≥𝜏[𝓁(𝜃i),𝓁(pj)] ⋅ ( n ∑ j�=1 xj�,k−1,i+ m ∑ i�=1 xjki�−1 )k=2, …,n; j=1, …,n; i=1, …,m (26) d k from = n ∑ j=1 m ∑ i=1 (𝜏[𝓁(pj),𝓁(𝜃i)] ⋅xjki)k=1, …, n (27) C max ≥sk+ n ∑ j=1 m ∑ i=1 (t(pj)⋅xjki)k=1, …, n (28) s k≥sk�+ n ∑ j=1 (t(pj)⋅xjk�i)−M⋅ ( 2− n ∑ j=1 (xjki +xjk�i) )k=2, …,n; k�=1, …,k− 1; i=1, …,m (29) sk ≥s k−1 +d k to +d k from k=1, …, n (30) x jki ∈{0, 1} j,k=1, …,n; i=1, …,m (31) dk to ,d k from ≥0k=1, …, n (32) Cmax ≥0 (33) sk ≥ 0k=0, …,n 835 Integrated pallet retrieval andprocessing inwarehouses… predecessors. While this results in some redundant constraints, we need less big-M conditions. Overall, only constraints(28) controlling the objective value contain the big-M parameter. Therefore, the objective value of each feasible solution is always an upper bound for parameterM, and it can be set to 4.1.2 Dynamic programming For the worst-case evaluation of PRPPR Bl , we need to determine which pallets the adversary chooses to delay for a fixed stacker crane tour characterized by a pallet retrieval sequence 𝜋 and an assignment 𝛼 of pallets to I/O-points. For this purpose, we present a dynamic programming approach, where the key observation is that a pallet processing can only start after it is retrieved by the stacker crane and the processing of the previous pallet at the same I/O-point is completed. Due to the blocking condition, the stacker crane can only retrieve the current pallet after the processing of the pallet previously retrieved by the stacker crane (at any I/O-point) is started. From the resulting network withO(n) states, we then create Γ copies to incorporate the potential pallet delays, leading to a dynamic programming approach with a runtime of O(n⋅Γ) . The dynamic program has states z𝛾k∈ℝ+ corresponding to the processing start time of the pallet retrieved at position k∈{0, …,n} (where k=0 means that no pallet is retrieved at all) in the case that at most 𝛾∈{0, …,Γ} pallets can be delayed. In addition, states z𝛾,n+1 indicate the resulting makespan Cmax if at most 𝛾∈{0, …,Γ} pallets can take their worst-case processing times. In the following, let set Pred(n+1)⊆{1, …,n} contain the positions of all pallets that are processed last on any I/O-point. Moreover, for k=1, …,n , we denote by d(𝜋k) the stacker crane travel duration to retrieve pallet 𝜋k (i.e., the time to move from its previous location to the initial location of pallet 𝜋k and then to the assigned I/O-point 𝛼(𝜋k) ), which is fixed for given 𝜋 and 𝛼 . We initialize z𝛾0=0 for all 𝛾=0, …,Γ , and the recursion is given as follows. • For 𝛾=0 and k=1, …,n , we have z 0 k =max{z0, k −1+d(𝜋 k ),z0, pred ( k )+t(𝜋 pred ( k ) )} , because no pallet is delayed, and the processing of pallet 𝜋k can only start after it is retrieved by the stacker crane and its I/O-point predecessor is completed, respectively. • For 𝛾=1, …,Γ and k=1, …,n , we additionally have to consider the case that the predecessor pallet 𝜋pred(k) is delayed, leading to (34) M = ∑ p∈P t(p)+ ∑ 𝓁 i ,𝓁 j ∈L 𝜏[𝓁i,𝓁j] . z 𝛾k =max{z 𝛾,k−1 +d(𝜋 k ), z𝛾,pred(k)+t(𝜋pred(k)), z 𝛾−1, pred(k) +t(𝜋 pred(k) )+ t(𝜋 pred(k) )} . 836 J.-N.Buckow et al. • For 𝛾=0 and k=n+1 we have z0, n+1 =max k∈Pred(n+1) {z 0k +t(𝜋 k)} , as the makespan Cmax is defined as the largest completion time of a pallet processing. • For k=n+1 and 𝛾=1, …,Γ , we have z𝛾,n+1 =max k∈Pred(n+1) {z 𝛾k +t(𝜋 k ) , z𝛾−1, k +t(𝜋 k )+ t(𝜋 k)} to additionally incorporate the case that a pallet processed last on an I/O-point is delayed. Example 3 Recall the schedule displayed in Fig.2 for the PRPPR Bl instance with Γ=2 from Tables 1 and 2. The corresponding dynamic programming process for the worst-case evaluation is shown in Fig.7. The nodes represent the states, and the arcs correspond to the different values considered in the recursion. The stacker crane travel durations considered in the recursion are represented by dashed arcs, while the pallet processing times are illustrated by solid arcs. The dotted arcs thereby correspond to the case that the processing of a pallet is delayed. A longest path from Fig. 7 Example of dynamic programming for PRPPR Bl 837 Integrated pallet retrieval andprocessing inwarehouses… state z00 to z27 with a length of38 is highlighted in bold, and the adversary would delay pallets p2 and p4 . 4.1.3 Robust case To formulate the robust variant PRPPR Bl as MIP, we need to integrate the dynamic program for the worst-case evaluation as described in Subsection4.1.2 into the MIP for the corresponding nominal variant PRPPBl as specified in Subsection4.1.1. On the one hand, for all 𝛾=0, …,Γ and k=0, …,n+1 , we insert a variable z𝛾k representing the corresponding state in the dynamic program. On the other hand, we remove variable Cmax and the starting time variables sk for k=1, …,n , as these values are already represented by the inserted state variables. ( MIP-PRPP R Bl) (35) min zΓ,n+1 s.t. (22)−(26) (36) z 𝛾k≥z𝛾,k−1+dk to +dk from 𝛾=0, …,Γ; k=1, …,n (37) z 𝛾k≥z𝛾k�+ n ∑ j=1 (t(pj)⋅xjk�i)−M⋅(2− n ∑ j=1 (xjki +xjk�i)) 𝛾=0, …,Γ; k=2, …,n; k�=1, …,k− 1; i=1, …,m (38) z 𝛾k≥z𝛾−1,k�+ n ∑ j=1 ((t(pj)+ t(pj)) ⋅xjk�i) −M⋅(2− n ∑ j=1 (xjki +xjk�i))𝛾=1, …,Γ; k=2, …,n; k�=1, …,k− 1; i=1, …,m (39) z 𝛾,n+1≥z𝛾k+ n ∑ j=1 m ∑ i=1 (t(pj)⋅xjki)𝛾=0, …,Γ ; k=1, …,n (40) z 𝛾,n+1≥z𝛾−1,k+ n ∑ j=1 m ∑ i=1 ((t(pj)+ t(pj)) ⋅xjki)𝛾=1, …,Γ ; k=𝛾,…,n 838 J.-N.Buckow et al. By the modifications described above, the MIP formulation (35)-(43) results, where constraints (22)-(26) are copied from the nominal MIP. The objective(35) minimizes the makespan by considering variable zΓ,n+1 corresponding to the final state in the dynamic program. The dynamic programming recursion is implemented by constraints(36)-(40), where some cases of the maximum terms are summarized as they express the same. Constraints (36) ensure that the stacker crane travel durations d (𝜋 k )=d k to +d k from to retrieve pallet 𝜋k for k=1, …,n are properly considered in the recursion. The nominal and worst-case pallet processing times for the pallet predecessors at the I/O-points are taken into account by constraints(37) and(38), respectively. Due to the big-M conditions, these constraints are only active if the two considered jobs are processed on the same I/O-point. Similar to the nominal case, the objective value of each feasible solution serves as an upper bound for parameterM, since only constraints(37) and(38) which control the objective value contain big-M conditions, allowing it to be set to Constraints(39) and(40) guarantee that the makespan for each value 𝛾∈{1, …,Γ} is defined as the largest completion time of a pallet. Finally, the variable domains are defined by constraints(41)-(43). 4.2 Buffering variant This subsection tackles the buffering case with multiple I/O-points. Starting with a mathematical model of the nominal variant PRPPBu in Sect.4.2.1, the worst-case evaluation for the robust counterpart PRPPR Bu is solved by dynamic programming in Sect.4.2.2. Eventually, Sect.4.2.3 incorporates this dynamic programming approach into the mathematical model of the nominal case. 4.2.1 Nominal case By adapting the MIP formulation (21)-(33) of PRPPBl as described in Subsection4.1.1, we next derive the model(45)-(52) for PRPPBu . In this model, we keep the objective function(45), the constraints (22)-(26), as well as all four variable (41) x jki ∈{0, 1} j,k=1, …,n; i=1, …,m (42) dk to ,d k from ≥0k=1, …, n (43) z 𝛾k≥0𝛾 =0, …,Γ; k=0, …,n+1 (44) M = ∑ p∈P (t(p)+ t(p)) + ∑ 𝓁 i ,𝓁 j ∈L 𝜏[𝓁i,𝓁j] . 839 Integrated pallet retrieval andprocessing inwarehouses… types(49)-(52). Note that we also keep constraints(27) and(28) that are relevant for the makespan calculation and repeat them in(46) and(47) for better readability. Furthermore, we add constraints(48) to ensure that each pallet is only processed after the stacker crane has brought it to the assigned I/O-point, where no idle times are considered due to sufficient buffer space. Note that in constraints(52) defining the starting time variables, no variable s0 is needed compared to inequalities(33), as we have constraints(48) rather than constraints(29). Again, since only constraints(47) controlling the objective value contain big-M conditions, parameterM can also be set according to equation(34). 4.2.2 Dynamic programming In the following, we present a dynamic programming approach for the worst-case evaluation of PRPPR Bl , meaning to determine the pallets the adversary chooses to delay once the stacker crane movement characterized by 𝜋 and 𝛼 is fixed. Due to sufficient buffer space in the case of PRPPR Bl , a pallet p∈P is ready for processing (MIP-PRPPBu) (45) min Cmax s.t. (22)−(26) (46) C max ≥sk+ n ∑ j=1 m ∑ i=1 (t(pj)⋅xjki)k=1, …, n (47) s k≥sk�+ n ∑ j=1 (t(pj)⋅xjk�i)−M⋅ ( 2− n ∑ j=1 (xjki +xjk�i) )k=2, …,n; k�=1, …,k− 1; i=1, …,m (48) s k≥ k ∑ k � =1 (dk� to +dk� from)k=1, …, n (49) x jki ∈{0, 1} j,k=1, …,n; i=1, …,m (50) dk to ,d k from ≥0k=1, …, n (51) Cmax ≥ 0 (52) sk ≥ 0k=1, …,n 840 J.-N.Buckow et al. as soon as the stacker crane has brought it to its assigned I/O-point, and we denote this point in time as the pallet’s release dater(p). Due to the release dates and the objective function of minimizing the makespan Cmax that is determined only by one I/O-point, there always exists an optimal solution in which the adversary only delays pallets processed at one specific I/O-point. Therefore, the problem to compute the delayed pallets for given 𝜋 and 𝛼 in PRPPR Bl can be handled for each I/O-point independently and by taking one with the largest resulting makespan Cmax . Due to the discussion above, a dynamic programming approach considering only one I/O-point at a time is sufficient for the worst-case evaluation. Recall that problem PRPPBl with a single I/O-point is related to the two machine problem F2||Cmax , where the stacker crane forms the first machine, and the single I/Opoint corresponds to the second machine. To deal with the worst-case evaluation of problem F2||Cmax with budgeted uncertainty, Levorato etal (2022) present a dynamic programming approach. However, since they assume that the job processing times on both machines are uncertain, their approach is not directly applicable to our setting. In our case, the stacker crane travel times are certain, and only the pallet processing times at the I/O-points are subject to uncertainty. We therefore present an adapted variant of their dynamic programming approach to tackle our setting. In our approach, we have states z𝛾k∈ℝ+ that indicate the worst-case makespan when at most 𝛾∈{0, …,Γ} pallets can be delayed, and only the pallets processed at positions 0, …,k on the current machine are taken into account. Note that for a given 𝛾 , the number of states can be reduced by considering only the values k∈{𝛾,…,n−Γ+𝛾} because the remaining states are never part of a longest path in the resulting network. Our initialization is simply z00 =0 , since no pallet is processed for 𝛾=0 and k=0 . In the recursion, we distinguish the following three cases. • For 𝛾=0 and k=1, …,n−Γ , we have z0k =max{r(𝜋 k ),z 0,k−1 }+t(𝜋 k) , because no pallet can be delayed at all, and we need to consider both the release date r(𝜋k) of the pallet at thekth position as well as the completion time z0,k−1 of the pallet at the previous position k−1 . • For 𝛾=1, …,Γ and k=𝛾 , thekth pallet can always be assumed to be delayed, and we thus have z𝛾k =max{r(𝜋 k ),z 𝛾−1,k−1 }+t(𝜋 k )+  t(𝜋 k) . • For 𝛾=1, …,Γ and k=𝛾+1, …,n−Γ+𝛾 , we have to consider the two cases that the current pallet is delayed or not and take the maximum, leading to The presented dynamic programming approach has the overall runtime O(Γ ⋅n) , as we have states z𝛾k for 𝛾=0, …,Γ and k=𝛾,…,n−Γ+𝛾 . Since we have to apply the dynamic programming algorithm for each I/O-point independently and taking the maximum, the worst-case evaluation for PRPPR Bu has the runtime O(Γ ⋅n⋅m) . z 𝛾k=max{max{r(𝜋k),z𝛾,k−1}+t(𝜋k), max{r(𝜋k),z𝛾−1,k−1}+t(𝜋k)+  t(𝜋k )} =max{r(𝜋 k )+t(𝜋 k )+ t(𝜋 k ),z 𝛾,k−1 +t(𝜋 j ),z 𝛾−1,k−1 +t(𝜋 j )+ t(𝜋 k )}. 847 Integrated pallet retrieval andprocessing inwarehouses… results. Furthermore, the makespan increases are basically the same in the blocking and buffering case, apart from a few differences in some combinations. Since the results depicted in Fig.10 disclose that the robust models for the PRPP with budgeted uncertainty lead to considerably better results than the nominal models, we conclude that the robust case needs its own specific models to be tackled appropriately. To also investigate how sensitive our robust MIP models react to changes in the uncertainty budget Γ , we conducted a sensitivity analysis in another experiment. In that experiment, we distinguish between two types of Γ for the sake of clarity. On the one hand, we have Γal which is actually used in the algorithms to solve the models, and on the other hand, we have Γev for the worst-case evaluation of the resulting solutions using the dynamic programming algorithms. For all instances with n≤10 pallets, we evaluated the solutions obtained by both the nominal models ( Γal =0 ) and the robust models ( Γal =3 ) for different values of Γev ∈{0, 1, 2, 3, 4, 5} . Figure11 depicts for both the blocking and buffering variants the average ratios of the nominal to the robust objective values, differentiated by Γev . Ratios smaller than1.0 mean that the nominal models obtained better solutions, while ratios larger than1.0 indicate that the robust models generated superior solutions. It can be seen in Fig.11 that the ratios are below1.0 only for Γev =0 , meaning that the solution quality of the nominal models only exceeds the solution quality of the robust models if there is no uncertainty at all. Moreover, the solution quality of the nominal and robust models is nearly the same for Γev =1 , since the ratios are only a little above1.0. The ratios reach more than1.1 for Γev =2 , and continue to rise even more with growing Γev , with the ratios rising faster in the blocking case, while the buffering case reaches saturation earlier. The benefits of the blocking model thus seem to be moderately larger than those of the buffering model, as the ratios are generally a bit larger. However, the buffering model seems to be slightly more resilient to changes in Γev , as the increase in the ratios becomes rather small at a certain point. Overall, the robust models yield a stable gain compared to the nominal models for all different values of Γev except0, showing that our robust models are quite insensitive to changes in the uncertainty budget Γ . Fig. 11 Average ratios of the nominal ( Γal =0 ) to the robust ( Γal =3 ) makespans, separated by the blocking and buffering variant, and evaluated for different Γev 848 J.-N.Buckow et al. 5.4 Benefits ofbuffers In the next experiment, we examined the benefits of having a buffer at each I/Opoint by comparing the blocking variant PRPPBl with the buffering variant PRPPBu . Note that for any given instance, the optimal makespan in the buffering variant is at least as good as in the blocking variant, since the buffering variant relaxes the blocking constraint. The benefits of the buffer are measured by the resulting average percentage makespan increases of the blocking compared to the buffering variant, thus corresponding to the required makespan increases when having no buffer at all. Note that the higher the makespan increases, the larger the benefits of having buffers. To calculate these makespan increases, we used the results obtained from both the nominal models MIPPRPPBl and MIPPRPPBu (see Sects.4.1.1 and4.2.1) as well as the robust models MIPPRPPR Bl and MIPPRPPR Bu (see Sects.4.1.3 and4.2.3). For the nominal and robust case, the average percentage makespan increases are displayed in Fig.12 for all combinations of parametersn andm, separated by the nominal and robust case. It can be seen that most makespan increases are in the single-digit percentage range (remember that the larger the makespan increases, the bigger the benefits of the buffers), showing that having a buffer considerable reduces the makespan. These makespan increases become even larger in the robust case compared to the nominal case, caused by the fact that solutions for the blocking variant are more vulnerable to increases in the pallet processing times as these cannot be buffered. Generally, the results show that it is very worthwhile to use a buffer, particularly in the robust case. This shows practitioners that buffers should be installed at the I/O-points whenever possible. In preliminary experiments, we also analyzed the solution structure in the case of PRPPBu , showing that the buffer space is actually used regularly. For the smaller instances with n≤10 pallets, one or two pallets are often stored at one Fig. 12 Average percentage makespan increases of the blocking compared to the buffering variant, separated by the nominal and robust case and by parametersn andm 849 Integrated pallet retrieval andprocessing inwarehouses… I/O-point simultaneously. However, we also analyzed heuristic solutions for the larger instances with n≥50 pallets, where sometimes up to20 pallets are stored at one I/O-point simultaneously. Moreover, the better the solution quality is, the more often the buffer tends to be used, explaining why the resulting makespans for PRPPBu are on average much lower than for PRPPBl . 5.5 Heuristics Preliminary tests have shown that CPLEX without warm-start takes up to a minute to set up the mathematical models for the larger instances with n=100 pallets, meaning it cannot quickly find even feasible solutions. In order to also solve larger instances properly in a reasonable amount of computing time, we implemented some heuristics in the last experiment. These heuristics can be used for both PRPPR Bl and PRPPR Bu , as they work with the same solution representation consisting of both the pallet retrieval sequence 𝜋 and the assignment 𝛼 of pallets to I/O-points. Moreover, even if these heuristics are designed to handle the robust case, note that they can also be used to tackle the nominal case simply by setting Γ=0 . Overall, we implemented the following fourheuristics. • Greedy heuristic (GD). Starting with an empty solution, the pallets are greedily appended to it by checking all pairs of I/O-points and remaining pallets. In each step, a pair is chosen that leads to the smallest makespan of the resulting partial solution. Such partial solutions are evaluated by applying the dynamic programming algorithms presented in Sect.4. • Random heuristic (RA). By randomly choosing both the pallet retrieval sequence 𝜋 and the assignment 𝛼 of pallets to I/O-points, solutions are sampled until a computation time limit is reached. Finally, the best of all sampled solutions is returned. • Iterative improvement (II). Initially, a feasible solution is determined using the greedy heuristic presented above. This initial solution is then iteratively improved by searching two neighborhoods one after the other until a local optimum is reached. In the first neighborhood, two pallets in the retrieval sequence are swapped, and new best I/O-points are assigned to both swapped pallets by checking all possibilities. In the second neighborhood, three pallets in the retrieval sequence are reordered in a best possible way by checking all six permutations of these three pallets and also assigning them to best I/Opoints. In each iteration, the second neighborhood is searched only if the first neighborhood yields no further improvements. This procedure terminates prematurely even if no local optimum has been reached after a given computation timelimit. • Tabu search (TS). The tabu search also starts with an initial solution generated by the greedy heuristic. This solution is gradually altered using the first neighborhood described in the iterative improvement algorithm, i.e., two pallets are swapped in the retrieval sequence and new best I/O-points are chosen for them. 850 J.-N.Buckow et al. The first improving neighbor solution found is always taken, and if no improving neighbor solution exists, a best neighbor solution is taken for which the transition to it is not marked as tabu in the tabu list. The transition to a neighbor solution is considered as tabu if the triple consisting of the two positions of both pallets swapped and the objective value of the generated neighbor solution is already contained as an entry in the tabu list. New tabu list entries are appended to the end of the tabu list, and if hereby the maximum tabu list size 𝜓=500 (a value that appeared effective in preliminary experiments) is exceeded, the first entry in the tabu list is removed. The tabu search terminates after a given computation time limit and returns the best solution found sofar. Figure13 depicts the results of all four heuristics for the robust problem variants PRPPR Bl (left) as well as PRPPR Bu (right) and different numbers of palletsn. These results are reported by average percentage gaps to best known solutions (BKS) of the respective instances, which correspond to the best solutions found during all experiments performed, including our tests of the robust models MIPPRPPR Bl and MIPPRPPR Bu presented in Sects.4.1.3 and4.2.3. In particular, note that the BKS values for all instances with n≤8 correspond to optimal objective values. Furthermore, a computing time limit of one minute per run was imposed in this experiment, even if heuristicsGH andII required much smaller computing times on most instances. Overall, Fig.13 reveals that the differences in the heuristic results between the blocking and buffering case are generally rather small. Nonetheless, it is evident that heuristicTS performs best, as its average gaps are well below 1% in all tested combinations. What is particularly remarkable about these results is that heuristicTS reached gaps of almost 0% for all instances with n≤10 , showing that it solved these small instances nearly optimally. Heuristic II performs second best, having average gaps under 3% in all tested combinations. The results of heuristicRA are less Fig. 13 Average percentage gaps of the heuristics to BKS values, differentiated by the blocking and buffering variant and by parametern 851 Integrated pallet retrieval andprocessing inwarehouses… consistent, there are very small gaps for instances with n≤8 , while for the large instances there are considerable gaps of up to 20% . The construction heuristicGD performs worst with mostly double-digit percentage gaps even for small instances. However, this is mainly because construction heuristic GD required much less computing time than the other heuristics, taking less than one second on any given instance. Since heuristics II and TS have very small gaps in all tested combinations, the PRPP seems to be well solvable on instances for larger, practically relevant sizes of up to n=100 pallets as in the case of the aforementioned company. Although knowing that the pallet processing times are still relevant, the company concentrates on the stacker crane travel times in their current planning. Nevertheless, discussions with practitioners at the company revealed that they underestimated the optimization potential gained by additionally considering the pallet processing times. Note that preliminary tests showed that heuristicsII andTS are much superior in solving large instances compared to the MIP models presented in Sect.4 and using CPLEX without warm-start. As already mentioned above, heuristicII is hence used to warm-start the MIP models. For several larger instances with n≥50 pallets, heuristicII did not reach a local optimum within the one minute time limit. Nevertheless, for the smaller instances with n≤10 pallets which were also used to test the MIP models, heuristicII required very little computing time to reach a local optimum, taking less than one second on any of these instances. As heuristicII is able to find good solutions on the smaller instances in a very short amount of computing time, it appears to be best suited for MIP warm-starts. While the MIP models were only capable of solving some small instances with at most ten pallets, preliminary experiments also revealed that even heuristics II andTS reached their computational limits for instances with more than 100 pallets. For such large instances, the search for an improving neighbor solution takes considerable computing times, resulting in very few (if any at all) iterations being completed in a reasonable amount of time, highlighting how difficult the PRPP is to solve. 6 Conclusions In this paper, we studied and evaluated different variants of the PRPP , an integrated problem considering both the retrieval and processing of pallets in warehouses with multiple I/O-points. We differentiate between the blocking and buffering problem variant, depending on whether there is sufficient buffer space at the I/O-points for temporarily storing pallets or not. Additionally, to protect against uncertainties in pallet processing times, we apply robust optimization with budgeted uncertainty sets. When having just a single I/O-point, the blocking and the buffering variants are equivalent to well-known two-machine flow-shop scheduling problems, allowing to solve the single I/O-point case of these two variants without robustness in polynomial time. Moreover, we proved that even the robust single I/O-point blocking 852 J.-N.Buckow et al. variant can be solved in polynomial time, while the complexity of the robust buffering variant with only one I/O-point remains an open question. For the general case with an arbitrary number of I/O-points, mathematical models were presented for both the blocking and the buffering variant. Furthermore, dynamic programming algorithms for the worst-case evaluation of the variants with uncertainty were developed, which were then integrated into the nominal mathematical models to obtain robust models. The computational study disclosed that our new integrated models for the PRPP achieved much better results than existing models for pallet retrieval optimization or parallel machine scheduling problems. This shows that both the stacker crane travel times as well as the pallet processing times must be taken into account to solve the PRPP adequately. Compared to the nominal integrated models, our robust models turned out to be considerably better at hedging against uncertainties in the pallet processing times. The comparison between the blocking and buffering variants shows that in both the nominal and robust case the makespan can be reduced substantially by setting up buffer space at the I/O-points. To solve larger instances appropriately in a short amount of computing time, an iterative improvement procedure and a tabu search performed well. Finally, our integrated models have shown to be suitable for addressing the new complex problem involving both pallet retrieval and processing. The additional integration of robust optimization leads to more resilient schedules, hedging against uncertainties. In some solutions obtained in the buffering case on the larger instances, up to20 pallets are stored at one I/O-point simultaneously, where an infinite buffer capacity was presumed. Therefore, future research could explore a more general variant mixing the blocking and buffering case by assuming an arbitrary finite buffer capacity. Appendix A. Detailed MIP results Tables4 and5 show the results of the four mathematical models presented in Sect.4 obtained by CPLEX within an one hour computational time limit. The results in Table4 refer to the nominal integrated models MIPPRPPBl and MIPPRPPBu introduced in Sects.4.1.1 and4.2.1, while the results in Table5 refer to the robust integrated models MIPPRPPR Bl and MIPPRPPR Bu presented in Sects.4.1.3 and4.2.3. In both tables, the results are differentiated by the parametersn andm as well as the blocking (left) and buffering case (right). For each given combination, the number of solutions verified as optimally solved, the average optimality gaps reported by CPLEX, and the average computational times required arelisted. It can be seen in Tables4 and5 that all instances with n≤8 pallets were verified as optimally solved, whereas some instances with n≥9 pallets could not be verified within the time limit. Overall, the computing times rise substantially with increasing numbers of palletsn and I/O-pointsm. The general trends are the same in the nominal and robust case, but the computing times and optimality gaps increase a bit faster in the robust case. Overall, an instance size of around n=10 pallets seems 853 Integrated pallet retrieval andprocessing inwarehouses… Table 4 Nominal MIP results n m Blocking Buffering #Opt Avg. gap [%] Avg. time [s] #Opt Avg. gap [%] Avg. time [s] 5 1 10 0.0 0.0 10 0.0 0.0 2 10 0.0 0.1 10 0.0 0.1 3 10 0.0 0.1 10 0.0 0.1 6 1 10 0.0 0.0 10 0.0 0.0 2 10 0.0 0.2 10 0.0 0.2 3 10 0.0 0.4 10 0.0 0.3 7 1 10 0.0 0.1 10 0.0 0.1 2 10 0.0 1.4 10 0.0 1.3 3 10 0.0 4.6 10 0.0 2.7 8 1 10 0.0 0.4 10 0.0 1.0 2 10 0.0 13.0 10 0.0 12.4 3 10 0.0 292.9 10 0.0 165.9 9 1 10 0.0 1.4 10 0.0 4.0 2 10 0.0 54.5 10 0.0 119.4 3 9 0.6 682.5 9 1.3 773.4 10 1 10 0.0 14.8 10 0.0 47.5 2 8 1.6 1307.3 6 2.3 1842.6 3 6 3.0 2452.6 8 2.5 1919.8 Table 5 Robust MIP results n m Blocking Buffering #Opt Avg. gap [%] Avg. time [s] #Opt Avg. gap [%] Avg. time [s] 5 1 10 0.0 0.0 10 0.0 0.0 2 10 0.0 0.1 10 0.0 0.1 3 10 0.0 0.2 10 0.0 0.2 6 1 10 0.0 0.1 10 0.0 0.1 2 10 0.0 0.6 10 0.0 0.4 3 10 0.0 1.4 10 0.0 0.9 7 1 10 0.0 0.2 10 0.0 0.2 2 10 0.0 2.5 10 0.0 2.2 3 10 0.0 10.6 10 0.0 8.0 8 1 10 0.0 0.6 10 0.0 0.4 2 10 0.0 23.0 10 0.0 17.5 3 10 0.0 188.3 10 0.0 177.3 9 1 10 0.0 3.3 10 0.0 2.3 2 10 0.0 444.1 10 0.0 219.9 3 8 1.6 1329.1 9 1.8 1132.3 10 1 10 0.0 23.5 10 0.0 16.2 2 3 8.0 3013.6 5 4.5 2563.4 3 1 17.7 3354.6 3 7.5 2969.1 854 J.-N.Buckow et al. to be the computational limit beyond which instances can no longer be solved well using the given MIP models. Acknowledgements The authors are grateful to the editors and two anonymous referees for their helpful and constructive comments. Funding Open Access funding enabled and organized by Projekt DEAL. Data Availibility All instances and results can be found at http:// www2. infor matik. uos. de/ kombo pt/ data/ rop/. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/ licenses/by/4.0/. References Allahverdi A (2015) The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research 246(2):345–378 Allahverdi A, Gupta J, Aldowaisan T (1999) A review of scheduling research involving setup considerations. Omega 27(2):219–239 Allahverdi A, Ng C, Cheng T etal (2008) A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187(3):985–1032 Ang M, Lim Y, Sim M (2012) Robust storage assignment in unit-load warehouses. Management Science 58(11):2114–2130 Ben-Tal A, Goryashko A, Guslitzer E etal (2004) Adjustable robust solutions of uncertain linear programs. Mathematical Programming 99(2):351–376 Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization, vol 28. Princeton University Press Bertsimas D, den Hertog D (2022) Robust and adaptive optimization. Dynamic Ideas LLC Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Mathematical Programming 98(1):49–71 Bertsimas D, Sim M (2004) The price of robustness. Operations Research 52(1):35–53 Bold M, Goerigk M (2021) A compact reformulation of the two-stage robust resource-constrained project scheduling problem. Computers & Operations Research 130:105232 Boysen N, Stephan K (2016) A survey on single crane scheduling in automated storage/retrieval systems. European Journal of Operational Research 254(3):691–704 Bruni M, Di Puglia Pugliese L, Beraldi P etal (2017) An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations. Omega 71:66–84 Buckow JN, Goerigk M, Knust S (2024) Retrieval optimization in a warehouse with multiple input/output-points. OR Spectrum. https:// doi. org/ 10. 1007/ s0029102400775-x Chen ZL, Hall N (2022) Supply chain scheduling, International Series in Operations Research & Management Science, vol 323. Springer de Koster R, Le-Duc T, Zaerpour N (2012) Determining the number of zones in a pick-and-sort order picking system. International Journal of Production Research 50(3):757–771 Gilmore P, Gomory R (1964) Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. Operations Research 12(5):655–679 Goerigk M, Hartisch M (2024) An introduction to robust combinatorial optimization, International Series in Operations Research & Management Science, vol 361. Springer 855 Integrated pallet retrieval andprocessing inwarehouses… Goerigk M, Grün B, Heßler P (2013) Branch and bound algorithms for the bus evacuation problem. Computers & Operations Research 40(12):3010–3020 Gong Y, de Koster R (2011) A review on stochastic models and analysis of warehouse operations. Logistics Research 3(4):191–205 Hosseini A, Otto A, Pesch E (2024) Scheduling in manufacturing with transportation: Classification and solution techniques. European Journal of Operational Research 315(3):821–843 Jiang X, Sun L, Zhang Y etal (2022) Order batching and sequencing for minimising the total order completion time in pick-and-sort warehouses. Expert Systems with Applications 187:115943 Jiu S (2022) Robust omnichannel retail operations with the implementation of ship-from-store. Transportation Research Part E: Logistics and Transportation Review 157:102550 Johnson S (1954) Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1(1):61–68 Levorato M, Figueiredo R, Frota Y (2022) Exact solutions for the two-machine robust flow shop with budgeted uncertainty. European Journal of Operational Research 300(1):46–57 Miyata H, Nagano M (2019) The blocking flow shop scheduling problem: A comprehensive and conceptual review. Expert Systems with Applications 137:130–156 Qiu R, Sun Y, Sun M (2022) A robust optimization approach for multi-product inventory management in a dual-channel warehouse under demand uncertainties. Omega 109:102591 Reddi S, Ramamoorthy C (1972) On the flow-shop sequencing problem with no wait in process. Journal of the Operational Research Society 23(3):323–331 Roodbergen K, Vis I (2009) A survey of literature on automated storage and retrieval systems. European Journal of Operational Research 194(2):343–362 Sun Y, Qiu R, Sun M (2024) A robust optimization approach for inventory management with limitedtime discounts and service-level requirement under demand uncertainty. International Journal of Production Economics 267:109096 Teck S, Dewil R, Vansteenwegen P (2024) A simulation-based genetic algorithm for a semi-automated warehouse scheduling problem with processing time variability. Applied Soft Computing 160:111713 Thorsen A, Yao T (2015) Robust inventory control under demand and lead time uncertainty. Annals of Operations Research 257(1):207–236 van Dal R, van der Veen J, Sierksma G (1993) Small and large TSP: Two polynomially solvable cases of the traveling salesman problem. European Journal of Operational Research 69(1):107–120 Yanıkoğlu İ, Gorissen B, den Hertog D (2019) A survey of adjustable robust optimization. European Journal of Operational Research 277(3):799–813 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.