Foundations of Neuroeconomic Analysis, by Paul W. Glimcher, New York: Oxford University Press, 2010, 467 + xix pp., $69.95 (hardback), Forthcoming in the Journal of Economic Methodology "Subjective values are real numbers ranging from 0 to 1,000. They take action potentials [bioelectrical pulses in neurons] as their natural units." (p. 398): this exemplifies how far Paul Glimcher, a professor at NYU, wants you to follow him in his new book, Foundations of Neuroeconomic Analysis. Can he be possibly serious?

Searching for the physiological substrate of subjective value is like re-opening a very cold case -almost a taboo, for several reasons. During most of the twentieth century, it was an undisputable premise that the investigation of cultural and social behaviour was the exclusive province of the social sciences and the humanities. Call it "emergence", "complexity" or "ontological disconnect", but there was no question that higher cognitive functions, such as judgment and decision-making, could not be explained by lower level biological processes (of course there is also the heavy hand of the historical context -the reactionary politics which drew their inspiration from biosocial theories of human traits, such as "intelligence" or "race", contributed to make any biosocial theory controversial from the start).

In economics, this is a Chinese wall of a special sort which was erected against choice theory explanations emerging from natural sciences. Samuelsonian economics established the orthodoxy that "revealed preference is choice is observed behaviour", in an explicit move away from the -at the timeintractable problem of what processes govern an individual's choice. Psychology and biology did progress on this front especially since the 1970s, but once isolated most economists never caught up with the developments taking place in these fields, to the point of deeming them a priori irrelevant to their own research object. As Geoffrey Hodgson, Jack Vromen and others have amply shown, this is not to say that economics and biology parted ways completely. But their relationships unfolded through analogies (exchange of concepts and models, such as "Darwinian competition" or "maximization of fitness-utility"), not on a common experimental ground -with some noteworthy exceptions, such as John Kagel, Raymond Battalio and Howard Rachlin's series of experiments on the demand curves for "animal consumers" published in the 1970s and 1980s. By all accounts, an insular attitude still characterizes the majority of the profession of economists today. Many economists suspect that contacts with biology are encouraged by the hype and easy successes coming with interdisciplinary projects and by the marvel caused by machines like fMRI, but at the cost of a degradation of academic standards (an opinion developed by Glenn Harrison in the journal Economics and Philosophy, but which is also voiced through more informal channels: http://www.econjobrumorsarchive.com/topic.php?id=10327#post-202562).

Even closer to the interests of the readers of this journal, the post-modern turn in the methodology of science possibly provides the strongest case to doubt that economic theories will ever be grounded in neuroscience. If it is indeed the case that methodologies are historically situated and contextualized, as Foucault or Kuhn hammered, so that one would be incapable to pronounce a verdict on the truth value of a theory for all times, then it follows that a piece of theory can hardly be "discovered" to be embodied in our timeless human nature. This point may be made more clearly: after Philip Mirowski's More Heat Than Light, which demonstrated that "utility" in the version developed by the marginalists was a circumstantial (and wobbly) development in their larger effort to emulate the achievements of contemporary physics -how is it conceivable that this "utility" can ever be later "discovered" or "measured" in the brain as an objective product of eons of biological evolution, as Glimcher seems to proclaim? If it ever happens, the presumption will be strong that the biologist simply realigned nature (here, the brain) with the categories and concepts most dominant in the intellectual atmosphere of his time (here, homo economicus). This would be a forceful criticism of neuroeconomics, reminiscent of other judgments passed in similar circumstances: in a letter to Engels, Marx famously derided Darwin's reading of the economy of nature in tooth and claw as reflecting the values of contemporary British industrial capitalism, while more recently anthropologist Marshall Sahlins pointed that the fitness maximizers populating Edward Wilson's sociobiology were capitalist neoclassic agents in disguise.

And yet, this is precisely why Foundations of Neuroeconomic Analysis is intensely thought provoking.

Despite the reasons just enumerated, it succeeds at making a strong case for neuroeconomics -and arrived at page 398, the reader has no trouble accepting the definition of subjective value in a cardinal and physiological sense which seemed so inconceivable before one had opened the book. Glimcher achieves this result by suggesting a new methodological approach to interdisciplinarity, and then using it to reinterpret a large body of recent theoretical and empirical work. His strategy consists in presenting a theory of choice which meets the constraints of three bodies of knowledge: it has to be physiologically plausible (e.g., neural representations of value must be cardinal), psychologically plausible (empirical regularities such as anticipation and regret should be accommodated in the axiomatization of choice, not discarded as "errors" or "biases"), and economically plausible (a physiological theory of choice should explain what leads individuals to exhibit choices coherent with axioms of expected utility, and why they diverge in specific circumstances nonetheless).

Though neuroeconomics is mostly known for its fMRI studies, Glimcher relies very little on them and refers mostly to results obtained in electrophysiology, following a procedure reminiscent of reverse engineering: in a classic experimental setting, monkeys are trained to indicate their preferred of two options by directing their gaze at a specific visual target. Hence, the very last step of this decision process is the movement of the eyes in the direction of the target. This allows investigating the choice performed by the monkey by reverse engineering it, starting from the very last step of the decision: what caused the movement of the eyes, which happens to be a very well-known neural circuitry. This certainly is not where the origin of the decision process will be identified, but Glimcher shows that a great deal of information can already be gleaned: how is the choice set involved in the decision represented in this brain region?, how is the value of each choice option instantiated?, and how can the degree of randomness inherent to behaviour be reconciled with the causal mechanisms of choice? -all these fundamental questions find fascinating answers by observing the electrophysiological properties of the motor control circuitry responsible for the eyes's movements. The same strategy is used for arms movements in decision tasks, allowing Glimcher to compare structures and functions in both cases and establish what are probably the common, universal mechanisms involved in choice.

The result is a causal account of how decisions between competing choice options are processed in our brains and transpose into behaviour. By necessity, the book is a difficult read: biologists will be asked to seize the logic of WARP and Von Neumann-Morgenstern utility and prospect theory, while economists will be challenged to follow discussions on cerebral architecture and the modelling of neuronal spike rates (though as always, familiarity with statistics and modelling does make it easier to grasp the logic of an argument, even formulated in a totally unfamiliar disciplinary context). More surprisingly maybe, this exercise in interdisciplinary dialogue has for effect to provide insight also into one's discipline -and this might require some cognitive effort as well. A good example is Glimcher's discussion of economists Faruk Gul and Wolfgang Pesendorfer's work on the cost of self-control and random utility theory: one of Glimcher's central arguments is that this kind of theoretical work, which redefines the classic axiomatization of choice to account for basic empirical psychological and behavioural regularities, shows the way forward for the integration of economics with psychological and neurological accounts of decision making. It is certainly food for thought for Gul and Pesendorfer, who not long ago authored a widely circulated indictment of neuroeconomics as a valid scientific project for economists. In the same vein, Glimcher's discussion of the fit of behavioural economics in a neuroeconomic theory of choice, focusing on the importance of the reference point, outlines a much more promising research program than the common view in (methodology of) economics that neuroeconomics is behavioural economics in the scanner. I would not be surprised if neurobiologists and psychologists found their own methodological assumptions productively challenged as well in the parts of the book focusing on their respective disciplines.

At the index of past ambitious attempts to account for traits of human behaviour by making economics and biology dialogue, Foundations of Neuroeconomic Analysis stands out by the breadth of the comprehension of vastly different intellectual traditions, by the degree of integration achieved, and by the solidity of the empirical material presented. This is a truly important book, which raises many questions. One of the most interesting is certainly: in what sense is "decision" explained by this account? In a very narrow sense, obviously. As Glimcher is the first to point out, he has a very detailed story for the very last stages of the decision (when the decision is about to be enacted in behaviour), but the antecedent, more fundamental stages are still very much unknown: how is the number of options balanced in a given choice, and their respective subjective values, determined? What makes an individual take a decision in the first place? Notwithstanding the methodological doubts and headaches it will give to its most postmodernist readers, Foundations of Neuroeconomic Analysis gives confidence that these questions can in principle be answered by the field Glimcher contributed to create.

Clement Levallois

Erasmus University Rotterdam.


Bipan Zou

Xianhao Xu

Yale Gong
email: gong@em-lyon.com

De Koster
email: rkoster@rsm.nl

René De Koster

Modeling parallel movement of lifts and vehicles in tier-captive vehicle-based warehousing systems

Keywords: Logistics, warehousing, AVS/RS, analytical and simulation modelling, performance analysis

This paper models and analyzes tier-captive autonomous vehicle storage and retrieval systems.

While previous models assume sequential commissioning of the lift and vehicles, we propose a parallel processing policy for the system, under which an arrival transaction can request the lift and the vehicle simultaneously. To investigate the performance of this policy, we formulate a fork-join queueing network in which an arrival transaction will be split into a horizontal movement task served by the vehicle and a vertical movement task served by the lift. We develop an approximation method based on decomposition of the fork-join queueing network to estimate the system performance. We build simulation models to validate the effectiveness of analytical models. The results show that the fork-join queueing network is accurate in estimating the system performance under the parallel processing policy. Numerical experiments and a real case are carried out to compare the system response time of retrieval transactions under parallel and sequential processing policies. The results show that, in systems with less than 10 tiers, the parallel processing policy outperforms the sequential processing policy by at least 5.51%. The advantage of parallel processing policy is decreasing with the rack height and the aisle length. In systems with more than 10 tiers and a length to height ratio larger than 7, we can find a critical retrieval transaction arrival rate, below which the parallel processing policy outperforms the sequential processing policy.

A C C E P T E D M A N U S C R I P T

Highlights

• We propose a parallel policy for autonomous tier-captive storage/retrieval systems.

• A fork-join queueing network is formulated to analyze the system performance.

• The parallel policy has advantages in small size systems.

• The parallel policy has advantages below a critical transaction arrival rate.

Introduction

Autonomous vehicle-based storage and retrieval systems (AVS/RSs) can store and retrieve goods stored on unit loads with high operational efficiency and flexibility. These systems have been adopted by many distribution centers in their high density storage areas, since the introduction by Savoye Logistics at the beginning of the 20th century [START_REF] Cai | Modeling and evaluating the avs/rs with tier-to-tier vehicles using a semi-open queueing network[END_REF]), Roy et al. (2015)).

Depending on the assignment of the vehicles to the tiers, AVS/RSs can be classified as tier-to-tier AVS/RSs where the vehicle can visit all tiers, and tier-captive AVS/RSs where the vehicle is captive to its designated tier [START_REF] Heragu | Analytical models for analysis of automated warehouse material handling systems[END_REF]). The tier-to-tier configuration is more suitable for handling palletized unit-loads with expensive vehicles (see Savoye Logistics).

In such a system, the movement of loads should be matched with a vehicle until the completion of the transaction [START_REF] Ekren | Simulation based experimental design to identify factors affecting performance of as/rs[END_REF]). The tier-captive configuration is more suitable for handling small-size unit loads, such as totes, with inexpensive vehicles (see KNAPP (2016)).

In such a system, each vehicle can only move in its designated aisle (Marchet et al. (2012)).

Fig. 1 presents a typical tier-captive AVS/RS for product totes. It consists of three components: a rack system containing single-deep storage racks, lifts that are mounted along the periphery of the racks and autonomous vehicles that move in aisles. The input/output point (I/O) of the system is located at the first tier of each aisle. The first storage positions at each side of the aisle are buffer locations. One is the inbound buffer which holds the loads to be stored, and the other is the outbound buffer which holds the loads that have been retrieved. In the tier-captive configuration, each vehicle is dedicated to an aisle and it provides horizontal load movement. The lift is discrete and it holds one load once time. It provides not only the vertical load movement for the storage and retrieval transactions, but also the load transfer to and from the buffer at each tier.

Previous researches of tier-captive AVS/RSs follow a sequential processing policy [START_REF] Heragu | Analytical models for analysis of automated warehouse material handling systems[END_REF]), Marchet et al. (2012), Marchet et al. (2013), [START_REF] Lerher | Travel time model for double-deep shuttle-based storage and retrieval systems[END_REF], Lerher et al. (2015a) and Lerher et al. (2015b)). In this policy, a storage transaction first requests the lift and then, sequentially, the vehicle, while a retrieval transaction requests the lift and vehicle in a reverse order. For a retrieval transaction, the vehicle in the designated tier transports the retrieval load to the outbound buffer and then the transaction requests the lift. For a storage transaction, the lift transports the load to be stored from the I/O point to the inbound buffer of the designated tier, and then the transaction requests the vehicle. However, since the vehicle in a tier-captive configuration can only move in its designated tier, a parallel processing policy under which the transactions request the lift and the vehicle simultaneously, may perform better. Under such a policy, for a retrieval transaction, the vehicle transports the load to be retrieved to the outbound buffer and meanwhile, the lift moves to the designated tier. For a storage transaction, the lift transports the load to be stored to the inbound buffer of the designated tier. Meanwhile, the vehicle moves to the inbound buffer. [START_REF] Hu | Travel time analysis of a new automated storage and retrieval system[END_REF] have examined such a policy for a special type of automated storage/retrieval system-Split-Platform AS/RS (SP-AS/RS), in which the S/R machine consists of one vertical platform and N horizontal platforms. These systems differ from AVS/RSs, since the S/R machine can travel inside the aisles and take care of the vertical transport as well. In addition, it does not have a buffer area where the storage and retrieval loads can be hold temporarily. While [START_REF] Hu | Travel time analysis of a new automated storage and retrieval system[END_REF] use deterministic models, we formulate stochastic models to estimate the performance of tier-captive AVS/RSs, thereby taking into account the effect of waiting for the different resources.

To analyze the system performance under the parallel processing policy, we formulate a forkjoin queueing network (FJQN) where a transaction will be split into a horizontal movement task served by the vehicle and a vertical movement task served by the lift. Based on the

A C C E P T E D M

A N U S C R I P T decomposition method of fork-join queueing networks presented in [START_REF] Bolch | Queuing networks and markov chains, modeling and performance evaluation with computer science applications[END_REF], we develop an approximation method to estimate the system performance. We validate the effectiveness of our fork-join queueing network using simulation. The results show that our analytical model is accurate for performance estimation. The results of the numerical experiments show that the system performance under the parallel processing policy is sensitive to the rack structure and the transaction arrival rate.

The remainder of this paper is organized as follows: Section 2 presents related literature.

Section 3 describes the system. In Section 4, we model the FJQN and introduce the methods applied for performance estimation. Section 5 contains the simulation validation and numerical experiments. Section 6 presents conclusions and future works.

Literature Review

In this section, we first present literature on models of tier-to-tier configurations, followed by literature on tier-captive AVS/RSs models. Finally, we discuss the parallel processing policy.

AVS/RSs with tier-to-tier configurations are widely used and studied. Malmborg (2002) is the first one to study tier-to-tier AVS/RSs, using continuous markov chain models for both Application of the framework shows that tier-to-tier systems prefer a large number of short aisles and tier-captive systems prefer a small number of long aisles. Lerher et al. (2015a) study shuttle-based storage and retrieval systems (one lift tier-captive AVS/RS). They consider acceleration and deceleration of lifts and vehicles, and derive closed-form expression of both horizontal and vertical loads movement. Subsequently, [START_REF] Lerher | Travel time model for double-deep shuttle-based storage and retrieval systems[END_REF] extends this work to shuttle-based storage and retrieval systems with double-deep storage racks.

Our literature review shows that, previous studies of tier-captive configurations follow a sequential processing policy, under which the transfer time involving a vehicle and a lift, is the sum of the vertical movement time, the horizontal movement time, and the waiting time.

A C C E P T E D M

A N U S C R I P T However, since the vehicle and the lift can work as parallel servers (Marchet et al. (2012)), the transfer time will be the sum of the maximum of these two movement times and the waiting time. The impact of the parallel processing policy may be substantial, which justifies explicit inclusion in the models.

System Description and Modeling Preparations

We present the operational process of the tier-captive AVS/RSs under the parallel processing policy in Section 3.1. Section 3.2 summarizes the notations and the assumptions used in this paper. Section 3.3 describes the components of the transaction cycle time related to the lift and the vehicle.

In a tier-captive AVS/RS (see Fig. 1), a discrete lift (consisting of one lifting table) transports unit loads between the tiers. Each aisle has a tier-captive vehicle (a dedicated shuttle) that transports loads into and out of individual storage positions and inbound/outbound buffers.

The lift and the vehicles can move in parallel, as the loads are transferred via buffers (one for inbound loads and one for outbound loads in each aisle at each tier). Based on the system structure, the lift and the parts served by the lift can be considered as one unit of the system.

This paper investigates the efficiency and advantages of parallel processing policy in tier-captive AVS/RSs. To this end, we examine one unit of the system (one lift system), which is equivalent to analyze the whole system (multiple lifts system). The storage and retrieval operations of the tier-captive AVS/RSs under the parallel processing policy can be described as follows. The flowcharts of the operational processes can be found in Appendix A.

For a storage transaction:

(1) The lift moves from its dwell point to the ground-floor tier, i.e., the I/O point of the system. Then, the lift picks up the storage load and goes to the designated tier. When the lift reaches its destination, it releases the load in the inbound buffer. Meanwhile, the vehicle in the designated tier moves from its dwell point to the inbound buffer.

(2) If the vehicle reaches the inbound buffer and the storage load is in the inbound buffer, the vehicle picks up the load. If either the vehicle or the storage load reaches the inbound buffer first, it has to wait for the other. After the vehicle has picked up the load, the vehicle brings it to the designated storage position and releases it.

A C C E P T E D M A N U S C R I P T

If the storage position is at the ground-floor tier, the lift should only move to the groundfloor tier, picks up the load at the I/O point and then releases the load in the inbound buffer of the ground-floor tier.

For a retrieval transaction:

(1) The vehicle in the designated tier moves from its dwell point to the retrieval load, picks up the load, and goes to the outbound buffer. Then, the vehicle releases the load in the outbound buffer. Meanwhile, the lift moves from its dwell point to the designated tier.

(2) If the lift reaches the designated tier and the retrieval load is in the outbound buffer, the lift picks up the load. If either the lift or the retrieved load reaches the outbound buffer first, it has to wait for the other. After the lift has picked up the load, it moves to the I/O point and releases the load.

If the storage position of the retrieval load is at the ground-floor tier, the lift should only move to the ground-floor tier, picks up the load from the outbound buffer of the ground-floor tier and then releases the load at the I/O point.

For both the storage and retrieval transactions, we call the operations of step (1) that are related to the lift the "vertical task", and those related to the vehicle the "horizontal task". We call the operations of step (2) the "remaining task". Under the parallel processing policy, the lift carries out the vertical task, while meanwhile, the vehicle carries out the horizontal task.

After the completion of these two tasks, either the lift picks up the load and carries out the remaining task for a retrieval transaction, or the vehicle picks up the load and carries out the remaining task for a storage transaction.

Since the inbound/outbound buffers are the first storage locations of each aisle, they can hold the same number of loads as other storage locations, i.e., one load. To avoid the waiting of the vehicle for the buffers, we assume that the state of the vehicle is determined by the state of its buffers. Namely, the vehicle is unavailable for storage transaction if its inbound buffer is occupied, and unavailable for retrieval transaction if its outbound buffer is occupied.

In the system described above, the transactions to be performed at the first tier need the lift. This study also considers the system that the transactions to be performed at the first tier do not need the lift, i.e., the vehicle transports the loads into and out of the ground-floor tier.

A C C E P T E D M

A N U S C R I P T

Main notations and assumptions

We define main notations used throughout the paper as follows:

A: Width of the tier, in the number of storage positions (see Fig. 1(b)).

T : Height of the rack, in the number of tiers. Because we investigate one basic unit of the tier-captive AVS/RS, the system examined in this paper consists of one lift and T vehicles.

C: Storage capacity, expressed in the number of storage positions served by one lift. We have C = 2AT .

h: Height of one tier (m).

w: Width of one storage position (m).

l: Length of one storage position (m).

v h : Maximum velocity of the vehicle (m/s).

v v : Maximum velocity of the lift (m/s).

a h : Acceleration/deceleration of the vehicle (m/s 2 ).

a v : Acceleration/deceleration of the lift (m/s 2 ).

λ s , λ r : Arrival rates of storage and retrieval transactions (per second). We assume that the arrival of transactions follows a Poisson distribution, so the average inter-arrival time of storage/retrieval transactions is λ -1 s , and λ -1 r , respectively. c h : Time for picking up or releasing a load by the vehicle (s). c v : Time for picking up or releasing a load by the lift (s). Without loss of generality, we assume that both c h and c v are constant.

T r : System response time for retrieval transactions (s). W r : Expected waiting time of retrieval transactions at external queue of the system. ρ l : Utilization of the lift. ρ v : Utilization of the vehicles.

We make the following assumptions for the tier-captive autonomous vehicle storage/retrieval systems:

1. We use the random storage policy, based on a space-conserving consideration [START_REF] Heragu | Facilities design[END_REF]). Under this policy, the storage load will be stored in any tier with the same probability 1/T , and each empty location has the same probability to be filled by the storage load.

A C C E P T E D M A N U S C R I P T

2. We only consider retrieval transactions in this study. This is based on the following observations. First, retrieval transactions represent the most critical activities of the system, as they directly influence the service level of the warehouse. Second, our model can be easily extended to the case of storage transactions.

3. The lift and the vehicles follow a Point-of-Service-Completion (POSC) dwell point policy.

Since we only consider retrieval transactions, the lift will dwell at the I/O point of the rack, and the vehicle will dwell at the outbound buffer at its storage tier.

4. The lift and the vehicles all follow a First-Come-First-Served (FCFS) service rule.

5. We only consider single-command cycles.

Components of transaction cycle times related with the lift and the vehicle

Since we only consider retrieval transactions in this study, we calculate the components of the retrieval transaction cycle time related to the lift and the vehicle. We call the retrieval transaction the customer of the system, and the retrieval transaction carried out at tier t as a class t customer, t = 1, 2, • • • , T . As a result of the random storage policy, the probability of retrieving a load from tier t is P (t) = 1/T , and the vehicle in tier t faces customer demand with a rate of λ t r = λ r /T . We index the storage locations in the aisle by distance to the outbound buffer, and denote the location of the retrieval load in the aisle by a. Then, the probability of the retrieval load being in storage position a is:

P (a) = 1 A , a = 1, 2, • • • , A.
Following the POSC dwell point policy, the vehicle will dwell nearby the outbound buffer.

To retrieve load a, the vehicle will move from the outbound buffer to the location of load a, pick it up, then return to the outbound buffer. The horizontal travel distance for the vehicle to move from its dwell point to the location of the retrieval load a is

H(a) = aw.
Considering the effect of acceleration and deceleration on the movement of the vehicle, we obtain the service time of the horizontal task, corresponding to the vehicle moves to the retrieval

A C C E P T E D M A N U S C R I P T
location, picks up the load, drives to the outbound buffer and releases it in the outbound buffer

T v (a) =      2 * [2v h /a h + (H(a) -v 2 h /a h )/v h + c h ], H(a) > v 2 h /a h 2 * [2 H(a) a h + c h ], H(a) ≤ v 2 h /a h . (1)
The vehicle will reach its maximum velocity v h in the first case of Eq.( 1). In this case, the one way travel time includes three parts: the accelerating time v h a h , the rapid travel time (H(a)v2 h /a h )/v h and the decelerating time v h a h . The vehicle cannot reach v h in the second case. Therefore, the one way travel time includes two parts: the accelerating time H(a) a h and the decelerating time H(a) a h . In this study, we model all service time distributions as general Coxian distributions. This allows analytical tractability, while such distributions can be fit to two moments of any distribution (see [START_REF] Jia | Solving semi-open queuing networks[END_REF]). For the approximation of a general service time distribution by a Coxian distribution, one can refer to Appendix D. We denote the mean value and the squared coefficient of variation scv of T v (a) by τ v and cv 2 v , respectively. We obtain τ v by Eq.( 2),

τ v = A a=1 P (a)T v (a). (2)
The retrieval transaction cycle time related to the lift can be divided into two parts (one part is the vertical task and the other is the remaining task). The first part corresponds to the vertical movement from the dwell point of the lift, i.e., the I/O point, to the designated tier t, the second part corresponds to the lift picks up the retrieval load from the outbound buffer, moves from tier t to the I/O point and then releases the load. Both parts have identical travel times, and the one-way travel distance is

V (t) = (t -1)h.
Considering the effect of acceleration and deceleration on the movement of the lift, the service time of the vertical task, corresponding to the movement from the I/O to the retrieval tier, equals

T l 1 (t) =      2v v /a v + (V (t) -v 2 v /a v )/v v , V (t) > v 2 v /a v A C C E P T E D M A N U S C R I P T
We approximate the distribution of T l 1 (t) based on its first two moments, its mean value τ l 1 and its scv cv 2 l 1 , by a phase-type Coxian distribution. We obtain τ l 1 by Eq.( 4)

τ l 1 = T t=1 P (t)T l 1 (t). ( 4
)
Since we adopt the POSC dwell point policy for the lift, the service time of the remaining

task is T l 2 (t) = T l 1 (t) + 2 * c v .
Thereby, we can get the mean value and the scv of T l 2 (t), denoted by τ l 2 and cv 2 l 2 , respectively.

4. Fork-Join Queuing Network for Tier-Captive AVS/RSs

In this section, we model the operational process of the tier-captive AVS/RSs under the parallel processing policy as a fork-join queueing network. Then, we develop an approximation method to estimate the performance measures of the system, since the fork-join queueing network is non-product form, because both the vehicle service time and the lift service time are generally distributed.

Fig. 2 shows the fork-join queueing network formulated for the tier-captive AVS/RSs. In this queueing network, the retrieval transactions arrive at the fork node with arrival rate λ r , leading to arrival rates at different tiers λ 1 r , λ 2 r , • • • , λ T r . A retrieval request for the t-th tier simultaneously requests the lift and the vehicle at the t-th tier. This operation corresponds to the fork node where the transaction is split into a horizontal task served by the t-th vehicle and a vertical task served by the lift. The finished horizontal task waits in the join queue of the horizontal tasks, denoted by Q J h , and the finished vertical task waits in the join queue of the vertical tasks, denoted by Q J v . After the completion of these two tasks, they depart their join queues and join at the join node. Then, the transaction goes to the station µ l 2 where the lift picks up the retrieval load, and then transports it from the designated tier to the I/O point of the system and releases the load. Since the lift will go with the transaction from the fork-join node to the µ l 2 node, the transaction gets service at µ l 2 node without waiting. Therefore, we model the µ l 2 node as a node with an infinite server.

In the queueing network, µ vt is the service rate of the t-th vehicle for the horizontal task.

As a result of the random storage policy, the service rates of all vehicles are the same and we have To simplify expressions, we define µ v := µ vt .

µ vt = 1 τ v , t = 1, 2, • • • , T. A C C E P T E D M A N U S C R I P T µ v 1 µ v 2 µ v T . . . µ l 1 λ 1 r λ 2 r λ T r λ r µ l 2 Q J h Q J v Poisson Arrivals Sink
The components of the retrieval transaction cycle times related with the lift are divided into two parts, T l 1 and T l 2 . We denote the service rate of the lift for its first part operation by µ l 1 .

Then we have

µ l 1 = 1 τ l 1 .
Let µ l 2 be the service rate of the lift for its second part operation. Then we have

µ l 2 = 1 τ l 2 .
Note that although no lifting is involved at the first tier, the lift is still required to transfer the load into or out the buffer area. Therefore, the horizontal task at the first tier is also included in the fork-join node of Fig. 2. For the system that the storage and retrieval transactions at the first tier do not need the lift, we model the service process of the first tier as an independent M/G/1 queuing system and the service process of the other tiers as a FJQN (see Appendix

C).

In order to examine the efficiency of the parallel processing policy, we need to estimate the performance of the fork-join queueing network, including the system response time for retrieval transactions, the expected waiting time of retrieval transactions in the external queue, and the lift utilization and the vehicle utilization. To this end, we develop an approximation method based on the decomposition principle of the fork-join queueing network (see [START_REF] Allen | Probability, statistics and queueing theory with computer science applications[END_REF][START_REF] Bolch | Queuing networks and markov chains, modeling and performance evaluation with computer science applications[END_REF]). The principle is that we consider the FJQN as an open queuing network and replace the subnetwork that contains the fork-join construct by a composite load-dependent node. The approximation method includes the following steps:

A C C E P T E D M A N U S C R I P T 1.

Estimation of load-dependent service rate of the fork-join node

We estimate the load-dependent service rate of the fork-join node in two steps: First, we build a closed queueing network that only contains the fork-join construct in Section 4.1.1.

Second, we approximate the state probabilities of the closed queueing network in Section 4.1.2.

With the approximated state probabilities, we calculate the service rate of the fork-join node based on the idea that the throughput of the closed queueing network equals the service rate of the fork-join node.

A closed queueing network for the fork-join node

We build a closed queueing network by short-circuiting the fork-join node (see Fig. 3). The number of customers, i.e., retrieval transactions, in this queueing network is constant, K r .

Based on the random storage policy, we assume that the K r customers are each randomly drawn as a retrieval from one of the T tiers. So, each customer in the closed queueing network represents a request for the t-th vehicle with probability 1/T .

A C C E P T E D M A N U S C R I P T

The aim of building this closed queueing network is that its throughput equals the service rate of the fork-join node. When a customer goes through the Fork node, it will be splitted into a horizontal task that requests the vehicle in designated tier and a vertical task requests for the lift. The joining of the horizontal and the vertical tasks at the join node represents the service completion of a customer. Let Q h be the number of waiting horizontal tasks in the join queue of the horizontal tasks Q J h , and Q v be the number of waiting vertical tasks in the join queue of the vertical tasks Q J v . Then, we define the state variable of this closed queueing network as follows:

µ v 1 µ v 2 µ v T . . . µ l 1 λ 1 r λ 2 r λ T r Q J h Q J v Fork Join Vehicle Fleet Lift Horizontal task Vertical task K r
s k = (Q h , Q v ), where k = Q v (m + 1) + Q h .
(

) 5
Where m = min(T, K r ) is the maximum number of waiting tasks in the join queue of the horizontal tasks Q J h . Since the system examined in this study has one discrete lift with a capacity of one load only, T vehicles, and the outbound buffer of each tier can hold only one load, the state space is

Q v + Q h < m + 1, Q v = 0, 1, Q h = 0, 1, 2, • • • , m. (6)
Note that Q v + Q h = m + 1 is not possible, since then immediately a horizontal task and a vertical task would be joined.

We note that a successful join of a horizontal task and a vertical task includes two cases:

The completion of the vertical task when Q h > 1, which means the lift reaches the target tier to access the waiting load, corresponding to a transition rate µ l 1 . The completion of the

A C C E P T E D M A N U S C R I P T horizontal task when Q v = 1
, which means the vehicle reaches the outbound buffer to release the load, corresponding to a transition rate µ v . Based on this observation, we can calculate the throughput of the closed queueing network with K r customers, which equals the load-dependent service rate of the fork-join node, by Eq.( 7),

λ f j (K r ) = m Q h =0 µ l 1 π(Q h , 0) + m-1 Q h =0 µ v π(Q h , 1), (7)
where π(s k ) is the state probability of state s k . We denote the number of phases of the Coxian distributions for the vehicle service time and the lift service time by n v and n l , respectively, denote the phase-type representation of these two Coxian distributions by (α v , T v ) and (α l , T l ). Then, we have

α v = [1 0 • • • 0] 1×nv , α l = [1 0 • • • 0] 1×n l ,
and we obtain the phase transition matrixes T v and T l by Eq.(D.1) or Eq.(D.3).

Additionally, we have an absorbing rate matrix T o v for T v and an absorbing rate matrix T o l for T l . They represent the rates of the customer being absorbed from each phase, and we obtain their expressions by Eq.(D.2) or Eq.(D.6).

After the approximation of the distributions of the vehicle service time and the lift service time, the state variable of the closed queueing network becomes (s k , i, j), where i, j is the current phase of the service process of the vehicle and the lift

(i = 0, 1, • • • , n v , j = 0, 1, • • • , n l ),
respectively. Since the state variable of the join queues, i.e., (Q h , Q v ), is independent of i and j, we can use s k in the transition matrix instead of (s k , i, j). But we should note that the phase state variable (i, j) is still contained in the transition matrix of the state variable s k .

We denote the vector of the state probabilities with Q v = 0 as π 0 , the vector of the state probabilities with

Q v = 1 as π 1 . Specifically, π 0 = [π(s 0 ), π(s 1 ), • • • , π(s m )] and π 1 = A C C E P T E D M A N U S C R I P T [π(s m+1 ), π(s m+2 ), • • • , π(s 2m )]
. Then, we have the following transition matrix of the state variable s k ,

Q =   B 00 B 01 B 10 B 11   . (8)
In the transition matrix Q, B 00 corresponds to the transition rates from the state of π 0 to the state of π 0 , and we have

B 00 =            s 0 s 1 • • • s m-1 s m s 0 T l ⊕ T v T o v α v ⊗ I l s 1 I v ⊗ T o l α l T l ⊕ T v -To l T o v α v ⊗ I l . . . . . . . . . . . . s m-1 I v ⊗ T o l α l T l ⊕ T v -To l T o v ⊗ I l s m T o l α l ⊗ α v T l           
, where I v is an identity matrix with n v × n v size, I l is an identity matrix with n l × n l size, ⊕ is Kronecker sum and ⊗ is Kronecker product, To

l = I v ⊗ To l and To l =            µ l 1 (1 -b l 1 ) . . . 0 . . . µ l n l            n l ×n l .
B 01 corresponds to the transition rates from the state of π 0 to the state of π 1 , and we have

B 01 =               s m+1 s m+2 s m+3 • • • s 2m s 0 I v ⊗ T o l s 1 I v ⊗ T o l s 2 I v ⊗ T o l . . . . . . s m-1 I v ⊗ T o l s m 0 0 0 0 0               . A C C E P T E D M A N U S C R I P T
B 10 corresponds to the transition rates from the state of π 1 to the state of π 0 , and we have

B 10 =            s 0 s 1 s 2 • • • s m-1 s m s m+1 T o v α v ⊗ α l 0 s m+2 T o v α v ⊗ α l 0 s m+3 T o v α v ⊗ α l 0 . . . . . . 0 s 2m T o v α v ⊗ α l 0            .
B 11 corresponds to the transition rates from the state of π 1 to the state of π 1 , and we have

B 11 =               s m+1 s m+2 s m+3 • • • s 2m-1 s 2m s m+1 T v -To v T o v α v s m+2 T v -To v T o v α v s m+3 T v -To v T o v α v . . . . . . . . . s 2m-1 T v -To v T o v α v s 2m T v              
, where

To v =            µ v 1 (1 -b v 1 ) . . . 0 . . . µ v nv            nv×nv .
In the steady state of [π 0 , π 1 ], we have,

[π 0 π 1 ]Q = 0. (9)
Additionally, the normalization condition holds,

[π 0 π 1 ]e = 1, ( 10
)
where e is a vector of ones. Combining Eq.( 9) and Eq.( 10), we can obtain the state probabilities π 0 and π 1 . Substituting π 0 , π 1 into Eq.( 7), we can obtain the load-dependent service rate of the fork-join node λ f j (K r ).

A C C E P T E D M A N U S C R I P T

Maximum Entropy Method for the open queueing network

According to the MEM reference (see [START_REF] Kouvatsos | Maximum entropy methods for general queueing network[END_REF]), the approximate state probabilities of the open queueing network are given by Eq.( 11),

π(k 1 , k 2 ) = π 1 (k 1 ) * π 2 (k 2 ), (11)
where k 1 , k 2 are the numbers of customers in the first and second node of the network, respectively. π 1 (k 1 ) is the marginal probability of the first node, and π 2 (k 2 ) is the marginal probability of second node.

For the first node, we can obtain its marginal state probabilities after recognizing its underlying Markov process,

π 1 (0) = 1 1 + +∞ k 1 =1 k 1 i=1 λr µ F ES (i) , π 1 (k 1 ) = π 1 (0) * k 1 i=1 λ r µ F ES (i) . ( 12
)
For the second node, the MEM provides its marginal probabilities as Eq.( 13) [START_REF] Kouvatsos | Maximum entropy methods for general queueing network[END_REF]),

π 2 (k 2 ) =      1 G 2 , k 2 = 0 1 G 2 • a 2 • b k 2 2 , k 2 > 0, (13)
where

a 2 = ρ 2 2 (1 -ρ 2 )( K2 -ρ 2 ) , b 2 = K2 -ρ 2 K2 , G 2 = 1 1 -ρ 2 . (14)
In Eq.( 14), ρ 2 is the utilization and K2 is the mean number of jobs at node 2. We can obtain ρ 2 by ρ 2 = λ r /µ l 2 . The MEM approximates K2 as a function of the utilization ρ 2 , the scv of the service time of node 2 cv 2 2 and the scv of the inter-arrival times of customers at node

2 cv 2 A2 . K2 = ρ 2 2 (1 + cv 2 A2 + ρ 2 cv 2 2 1 -ρ 2 ). ( 15
)
In Eq.( 15), the scv of the inter-arrival times of customers at node 2, i.e., cv 2 A2 , is computed by the following procedures,

cv 2 D1 = ρ 1 (1 -ρ 1 ) + (1 -ρ 1 )cv 2 A1 + ρ 2 1 cv 2 1 , ( 16
) A C C E P T E D M A N U S C R I P T c 2 1,2 = 1 + p 1,2 (c 2 D1 -1), ( 17
)
c 2 A2 = -1 + [ λ r p 0,2 λ 2 • (c 2 0,2 + 1) + λ 1 p 1,2 λ 2 • (c 2 1,2 + 1) ] -1 . ( 18
)
In Eq.( 16), cv 2 D1 is the scv of inter-departure times of customers at node 1, cv 2 A1 is the scv of inter-arrival times of customers at node 1 and cv 2 1 is the scv of service times at node 1. Since the customer arrival process follows a Poisson distribution and the service time of node 1 is exponential distributed and load-dependent, we have cv 2 A1 = 1 and cv 2 1 = 1. In Eq.( 17), p 1,2 is the routing probability of a customer from node 1 to node 2 and p 1,2 = 1. In Eq.( 18), p 0,1 and p 0,2 are separately the routing probabilities of a customer from outside to node 1 and 2, and p 0,1 = 1, p 0,2 = 0. λ 1 and λ 2 are the arrival rates of customers at node 1 and 2, respectively.

We have λ 1 = λ r p 0,1 and λ 2 = λ 1 p 1,2 .

Based on the observation above, we obtain the scv of the inter-arrival times of customers at node 2 c 2 A2 = 1. Further, we can obtain the marginal probabilities of node 2 by Eq.( 13). With the marginal probabilities of node 1 and node 2, we can obtain the state probabilities of the open queueing network, i.e., π(k 1 , k 2 ), by Eq.( 11). Then, we can calculate the mean service rate of node 1 by Eq.( 19).

μ1 = +∞ k 1 =1 π 1 (k 1 ) • µ F ES (k 1 ). ( 19
)
The expected number of customers at node 1 and node 2 can be calculated by Eq.( 20) and Eq.( 21), respectively.

K1 = +∞ k 1 =1 k 1 • π 1 (k 1 ), ( 20
) K2 = +∞ k 2 =1 k 2 • π 2 (k 2 ). ( 21
)
According to Little's Law, the system response time is given by Eq.( 22),

T r = K1 λ r + 1 µ l 2 . ( 22
)
The expected waiting time of retrieval transactions in external queue can be calculated by Eq.( 23),

W r = K1 λ r - 1 μ1 . ( 23
) A C C E P T E D M A N U S C R I P T
The expected external queue length is calculated by Eq.( 24),

L eq = λ r W r . ( 24
)
Since we only consider retrieval transactions and each vehicle faces a demand with λr T arrival rate, we can calculate the vehicle utilization by Eq.( 25),

ρ v = λ r T • µ v . ( 25
)
We obtain the lift utilization by Eq.( 26),

ρ l = 1 -π 1 (0) • π 2 (0). ( 26
)

Analytical Model Validation and Numerical Experiments

In Section 5.1, the fork-join queueing network formulated in this study is validated with simulation. Then, we carry out a series of numerical experiments to compare the performance of sequential and parallel processing policies in Section 5.2. In Section 5.3, we investigate a real case.

Validation with simulation

We develop a simulation model based on Arena(Version 14.0). Appendix E presents the details of simulation models, including the main events and processes, the process flowchart and the simulation validation results. Table 1 presents the system scenarios in simulation model. We consider a tier-captive AVS/RS (with one lift and T vehicles) used for storing standard euro-size totes of 60×40×40cm (l×w×h) net, or 60×50×80cm gross. 6 scenarios are examined based on the variation of T and A. Other assumptions are the same as the analytical models, i.e., random storage policy, POSC dwell point policy for the lift and vehicles and only retrieval transactions are considered. To validate the analytical models under different resource utilizations, the retrieval transaction arrival rate takes 6 levels, λ r = 50, 75,100,125,150,175,200 per hour.

For each examined case, first a warm-up period of 100 hours is run to eliminate the initial bias, followed by 100 replications of 1000 hours simulation. This leads to a 95% confidence interval where the half-width is less than 2% of the average. We take four performance metrics to validate the analytical models: the system response time for retrieval transactions T r , the expected waiting time of retrieval transactions in the external queue W r , the lift utilization ρ l 1 Notes: S means system scenarios. l = 0.6m, w = 0.5m, and the vehicle utilization ρ v . The analytical and simulation results are denoted by R a , R s , respectively. The accuracy of analytical models is measured by absolute relative error ε (Eq.( 27)).

A C C E P T E D M A N U S C R I P T
h = 1.2m, v v = 4m/s, v h = 2m/s, a v = 3m/s 2 , a h = 1m/s 2 , c v = 3s, c h = 2s
ε = | R a -R s | R s × 100%. ( 27
)
We present the simulation results, analytical results and relative error in Table 5 and Table

A C C E P T E D M

A N U S C R I P T 6. The average relative error of analytical results to simulation results is ε Tr = 4.91%, ε Wr = 11.77%, ε ρ l = 1.82% and ε ρv = 0.96%. The frequency of the relative error is presented in Fig. 5.

The simulation validation results show that the analytical models can accurately estimate the system response time for retrieval transactions, the expected waiting time in the external queue and the utilizations of the lift and vehicles.

Comparison of sequential and parallel processing policies

The motivation of proposing the parallel processing policy is that it may outperform the sequential processing policy for tier-captive AVS/RSs. We carry out numerical experiments to compare the performance of sequential and parallel processing policies. Based on the simulation validation results, we use the fork-join queueing network as the performance estimation tool of parallel processing policy. For sequential processing policy, we choose the open queueing network formulated by Marchet et al. (2012) as the performance estimation tool, which is identical to Fig. 2, except that the lift station with processing rate µ l 1 precedes the tiers station with parallel tiers. To compare the system response time of retrieval transactions for sequential and parallel processing policies in more detail, we vary T and A, i.e., T ranges from 6 to 13 and A T takes the values 5,7 and 9. The retrieval transaction arrival rate varies from 50 to 200 per hour with a stepsize of 10. We divide the scenarios and their results into two parts: small and large systems. The small systems correspond to T = 6, 7, 8, 9 and A T = 5, 7, 9 and the large systems correspond to T = 10, 11, 12, 13 and A T = 5, 7, 9 (Table 2). For each system scenario, we calculate the average system response time improvement percentage of the parallel processing policy over the sequential processing policy by Eq (28),

I = 1 16 200 λr=50 T s r -T p r T s r • 100%, (28)
where T s r and T p r are the system response time for retrieval transactions under sequential and parallel processing policies, respectively.

The system response times of retrieval transactions for small and large systems are presented in Fig. 6 and Fig. 7, respectively. The average improvement percentages I are presented in Table 3.

Table 3 shows that, in small systems, the parallel processing policy always outperforms the sequential processing policy in terms of system response time for retrieval transactions. For both small and large systems, the average improvement percentage I decreases with both the rack height T and the aisle length A. In systems with T ≤ 10, the parallel processing policy outperforms the sequential processing policy and the minimum average improvement percentage is 5.51%. 32 10.41 4.35 13.81 -1.02 -25.88 12.15 -5.61 -44.43 For large systems, we have: Comparing with small size systems, the performance of parallel processing policy becomes poorer in large size systems. In systems with T > 10 and A/T ≥ 7, there exists an intersection point between the curves of the sequential processing policy and the parallel processing policy, denoted by ( λr , Tr ) (For scenario 17, λr is larger than 200 per hour). We call λr as the critical retrieval transaction arrival rate. When λ r < λr , the parallel processing policy outperforms the sequential processing policy. The situation reverses when λ r > λr . Moreover, λr decreases with both the rack height T and the aisle length A. Although it might seem odd that the sequential policy outperforms the parallel policy for large systems The parallel processing policy reduces the total processing time, since it allows the lift and the vehicle to operate simultaneously. Specifically, the total processing time under the parallel processing policy is the maximum of the lift processing time and the vehicle processing time, while it is the sum of these two time under the sequential processing policy. However, for large systems with large transaction arrival rates, the parallel processing policy increases waiting time due to a heavier work load for the lift, in addition, the lift may also have to wait for the loads.

A C C E P T E D M A N U S C R I P T

In systems with a low rack, the capacity of the lift is sufficient such that the increase of waiting time is dominated by the reduction of total processing time. The parallel processing policy therefore outperforms the sequential processing policy in terms of system response time for retrieval transactions. However, in systems with a tall rack and (λ r > λr ), loads have to queue at all tiers for the common lift and the reduction of the total operational time cannot offset the increase of the waiting time. So, the parallel processing policy outperforms the sequential processing policy when λ r ≤ λr , and the situation reverses when λ r > λr .

Investigation of a real case

In this section, we investigate the efficiency of both sequential and parallel processing policies in a real case (an OSR shuttle system of KNAPP). The system consists of 10 single-deep storage 4. the system throughput can be improved by 2.11% by using the parallel processing policy. The critical retrieval transaction rate is λr = 155 per hour, the parallel processing policy outperforms the sequential processing policy in terms of system response time when λ r ≤ 155, the situation reverses when λ r > 155. This result coincides with the findings obtained in Section 5.2, i.e., the system should follow the parallel processing policy under a low service load. Otherwise, the sequential processing policy is better.

Conclusions and Future Work

This paper models and analyzes tier-captive autonomous vehicle-based storage and retrieval systems (tier-captive AVS/RSs), in which the vehicle can only visit its designated tier. Different from the tier-to-tier autonomous vehicle-based storage and retrieval systems (tier-to-tier AVS/RSs) in which the vehicle can visit all tiers, the tier-captive AVS/RSs are usually applied for handling small size loads, such as totes. In a tier-captive AVS/RS, the vehicle in the aisle processes the horizontal movement of the load, the lift mounted at the periphery of the rack processes the vertical movement of the load. Due to the variability of the vehicle fleet scale and the independence of the lifts and the vehicles, the system can process storage and retrieval transactions with high flexibility and responsiveness.

Current studies assume sequential commissioning of the lift and vehicles. We propose a parallel processing policy for tier-captive AVS/RSs, under which the lift and the vehicles can serve a transaction simultaneously. To investigate the performance of the parallel processing policy, we formulate a fork-join queueing network in which a transaction will be split into a vertical task served by the lift and a horizontal task served by the vehicle. Then, we develop an approximate method based on the decomposition of fork-join queueing network to estimate the performance of the system, including the system response time for retrieval transactions, the expected waiting time of retrieval transactions in the external queue, the utilizations of the lift and vehicles.

We build simulation models to validate the analytical model. The results show that the analytical model can accurately estimate the performance of tier-captive AVS/RSs under the parallel processing policy. We carry out numerical experiments to compare the system response time of sequential and parallel processing policies. The results show that the parallel processing policy outperforms the sequential processing policy in small size systems. Specifically, the number of tiers is less than 10. In such a system, the average improvement in system response time is at least 5.51%. The advantage of the parallel processing policy decreases with increasing rack height and aisle length.

In large size systems, i.e., the number of tiers is larger than 10 and the ratio of the aisle length to the rack height is larger than 7, we can find a critical point of the retrieval transaction

A C C E P T E D M A N U S C R I P T
arrival rate. When the retrieval transaction arrival rate is less than this critical level, the tiercaptive AVS/RS should follow the parallel processing policy. Otherwise, it should follow the sequential processing policy. We also investigate the performance of both sequential and parallel processing policies in a real case. Under the current retrieval transaction arrival rate, the system throughput can be improved by 2.11% by using parallel processing policy.

In future work, it is interesting to investigate the performance of the parallel processing policy in tier-to-tier AVS/RSs. We can also examine storage transactions and investigate the effect of dwell point policies on the system performance.

A C C E P T E D M

A N U S C R I P T is D, the maximum velocity of the traveler is v max and the accelerating/decelerating rate is a. Based on whether the traveler can reach v max or not, we have two kinds of velocity-time A

v(t) v max t 0 t p T -t p T (a) D > v 2 max /a v(t) √ aD t 0 D a 2 D a (b) D ≤ v 2 max /a
C C E P T E D M A N U S C R I P T µ v 2 µ v 3 µ v T . . . µ l 1 λ 2 r λ 3 r λ T r λ r -λ 1 r µ l 2 Q J h Q J v Poisson Arrivals Sink Fork Join Vehicle Fleet Lift Horizontal task Vertical task µ v 1 λ 1 r Poisson Arrivals Sink
Figure 12: Queuing network for tier-captive AVS/RS that the first tier does not need the lift use a Coxian-m (C m ) distribution with m = 1 cv 2 to approximate it. If a Coxian-2 distribution is adopted (Fig. 13 presents a typical Coxian-2 distribution), a customer starts in the first phase, and then enters the second phase with probability b 1 or gets absorbed with probability 1b 1 .

The phase-type representation of the Coxian-2 distribution is a pair (α, T). α = [1 0] is the initial state probability vector. T is the phase transition matrix of the underlying absorbing Markov process of the Coxian-2 distribution, and

T =   -µ 1 b 1 µ 1 0 -µ 2   , (D.1)
where µ 1 = 2/τ, µ 2 = 1/(τ * cv 2 ) and b 1 = 1/(2cv 2 ). Additionally, we have an absorbing rate matrix T o representing the rate of the customer being absorbed from each phase, which is shown as

T o =   µ 1 (1 -b 1 ) µ 2   . (D.2) 1 m 2 m 1 b 1 1 b - Figure 13: A typical Coxian-2 distribution
If the cv 2 < 0.5, a Coxian-m distribution (m > 2) is adopted, with m = 1 cv 2 (Fig. 14 presents a typical Coxian-m distribution). A customer starts in the first phase, then goes to the second phase with probability b 1 or gets absorbed with probability 1b 1 . After the The absorbing rate matrix T o is

T o =            µ 1 (1 -b 1 ) 0 . . . 0 µ 2            m×1 . (D.6) Appendix E
The following are the main events and processes in the simulation model: simultaneously. The simulation model captures this process by a "split" module, where the retrieval transaction is split into a horizontal task that requests the vehicle at the retrieval tier and a vertical task that requests the lift.

3. Transportation of a retrieval load from its storage position to the outbound buffer: After the vehicle is seized by the horizontal task, the vehicle moves from the entrance of the aisle to the retrieval position, picks up the load, moves with the load to the outbound buffer and unloads it in the buffer area. The service time depends on the storage position of the retrieval load.

4. Movement of lift from I/O to the target tier: After the lift is seized by the vertical task, the lift platform moves from the I/O of the system to the target tier. The lift is modeled as a server; the service time depends on the tier of the retrieval item. The lift is not be released after this operation.

5. Waiting of the lift for the retrieval load or of the load for the lift: If the lift reaches the target tier first, it will wait for the retrieval load. Otherwise, the retrieval load will wait for the lift at the outbound buffer. The simulation model captures this by a "match" modular that contains two queues. The lift waits for the retrieval load in one queue and the retrieval load waits for the lift in another. When both the lift and the retrieval load are in position, they will join into a retrieval transaction.

6. Transportation of the retrieval load from the retrieval tier to the I/O point: The lift loads the retrieval load from the outbound buffer, moves to the I/O point and then unloads the load. The service time depends on the retrieval tier. Note that the lift was already seized in the fourth event.

7. Departure of the retrieval transaction: The retrieval transaction is finished when the lift releases the load at the I/O of the system.

Figure 1 :

 1 Figure 1: Tier-captive AVS/RSs for product totes

  horizontal and vertical material flows to calculate the expected S/R cycle time (weighted sum of single and dual-command cycle times).Malmborg (2003a) takes cost factors into consideration and formulates an analytical model aiming at developing useful system designs.Malmborg (2003b) proposes a state equation model to predict the proportion of dual-command cycles for systems with opportunistic-interleaving, i.e., combining storage and retrieval transactions on S/R cycles on an opportunistic basis.Due to the impact of queuing in the system on performance, many papers have emerged using queuing models.[START_REF] Kuo | Design models for unit load storage and retrieval systems using autonomous vehicle technology and resource conserving storage and dwell point policies[END_REF] examine the random storage policy and the point-ofservice-completion (POSC) dwell point policy in tier-to-tier AVS/RS. They model the vehicle service process as an M/G/V queue and the lift service process as a G/G/L queue. Fukunari & Malmborg (2008) consider both single and dual-command cycles and model the lift service process as an M/G/L queue nested within an M/G/V queue modeling the vehicle service process. They derive the transaction cycle time by iteratively calculating the percentage of dual-command cycles until convergence of the waiting time in these two queuing systems. Fukunari & Malmborg (2009) extend this work and formulate a closed queueing network for A C C E P T E D M A N U S C R I P T tier-to-tier AVS/RSs, including the maintenance and repair of vehicles. Zhang et al. (2009) propose an approximation method based on the variance of the transaction inter-arrival times, which can accurately estimate the transaction waiting time. Since modeling the vehicles as an additional resource may be a better approach to capture the effect of the number of vehicles on system performance, recent studies model tier-to-tier systems as semi-open queueing networks (SOQN). Roy et al. (2012) build a multi-class SOQN with class switching for a single-tier AVS/RS, and design a decomposition method to estimate the system performance. Ekren et al. (2014) develop a matrix-geometric method to analyze the SOQN model built for tier-to-tier AVS/RSs. Cai et al. (2014) model a tier-to-tier system as a multi-class multi-stage SOQN, and use matrix-geometric methods to analyze it. Roy et al. (2015) investigate the position of the load/unload, the POSC dwell point policies and the location of cross-aisles in a single-tier AVS/RS. They also model the system as a SOQN. Tappia et al. (2016) study shuttle-based compact storage systems (AVS/RS with multi-deep storage lanes), considering both specialized and generic shuttles and both discrete and continuous lifts. They build multi-class SOQNs for both single and multi-tier systems and use matrix-geometric methods to analyze the SOQNs. Different from tier-to-tier configurations, tier-captive configurations have drawn little attention. Heragu et al. (2011) formulate an open queueing network to estimate the performance of tier-captive AVS/RS and investigate the advantages of AVS/RS over traditional AS/RS. Also, Marchet et al. (2012) build an open queueing network to estimate the response time of a tier-captive AVS/RS used for product totes, considering acceleration and deceleration of lifts and vehicles. Marchet et al. (2013) design a comprehensive design framework for AVS/RSs.

Figure 2 :

 2 Figure 2: The fork-join queuing network for tier-captive AVS/RSs

Figure 3 :

 3 Figure 3: The short-circuited fork-join node

4. 1 . 2 .

 12 Approximated state probabilities and throughput of the closed queueing networkTo derive the load-dependent throughput of the closed queueing network λ f j (•) from Eq.(7), we need to calculate the state probabilities of the closed queueing network π(s k ). To this end, we first approximate the general distributions of the vehicle service time and the lift service time by Coxian distributions (see[START_REF] Altiok | On the phase-type approximations of general distributions[END_REF],[START_REF] Jia | Solving semi-open queuing networks[END_REF],[START_REF] Cai | Modeling and evaluating the avs/rs with tier-to-tier vehicles using a semi-open queueing network[END_REF] Tappia et al. (2016)). Then we derive the transition matrix of s k , denoted by Q. For the approximation of general distributions by Coxian distributions, one can refer to Appendix D.

  Estimation of the performance measures of the fork-join queueing networkTo estimate the performance of the tier-captive AVS/RSs under the parallel processing policy, we have two steps: First, we build an open queueing network by replacing the fork-join node by a flow equivalent server with the service rates obtained in Section 4.1 (see[START_REF] Jia | Solving semi-open queuing networks[END_REF],[START_REF] Cai | Modeling and evaluating the avs/rs with tier-to-tier vehicles using a semi-open queueing network[END_REF],[START_REF] Ekren | Matrix-geometric solution for semi-open queuing network model of autonomous vehicle storage and retrieval system[END_REF] Tappia et al. (2016)). Then, we use the MEM to analyze the open queuing network since it is non-product-form.4.2.1. An open queueing network for the fork-join queueing networkWith the load-dependent service rate of the fork-join node obtained in Section 4.1, we replace the fork-join node of Fig.2by an F ES. We assume that the flow equivalent server has exponentially distributed load-dependent service times, and its service rates are given byµ F ES (•) = λ f j (•).Then we obtain an open queueing network depicted in Fig.4. An open queueing network for the fork-join queueing network The customer arrival process of this open queueing network follows a Poisson distribution with arrival rate λ r . An arrival customer first gets service of the F ES at node 1, whose service rate µ F ES (K r ) depends on the number of customers in it. Then, it gets service at node 2 without waiting, since node 2 contains a server with infinite service capacity. The service time of node 1 is exponentially distributed and load-dependent, and the service time of node 2 follows a general distribution with mean value τ l 2 and squared coefficient of variation cv 2 l 2 . So, the open queueing network depicted in Fig.4 is a non-product-form open network. Based on this observation, we apply the MEM for the analysis of the open queueing network (see Bolch (2006)), since this method can get the state probabilities of the open queueing network and the squared coefficients of variation by little computational efforts. The term entropy comes from information theory and is a measure of the uncertainty in the predictability of an event.

Figure 5 :

 5 Figure 5: Relative errors of the analytical results to the simulation results

Figure 6 :

 6 Figure 6: Comparison of parallel and sequential processing policies in small systems

  ,parallel policy T=13,A=65,sequential policy T=13,A=91,parallel policy T=13,A=91,sequential policy T=13,A=117,parallel policy T=13,A=117,sequential policy (d) T = 13 7: Comparison of parallel and sequential processing policies in large systems

  S C R I P Ttiers and each tier has a tier-captive shuttle that transports loads horizontally. The storage capacity of one tier is 144 totes. One discrete lift moves loads vertically (including the first tier). The current retrieval transaction arrival rate is 118 per hour. Other system parameters are presented in Table

Figure 8 :

 8 Figure 8: System response times for retrieval transactions under the sequential and parallel processing policies in the OSR case

Figure 11 :

 11 Figure 11: Velocity-time relationship based on traveling distance

Figure 14 :

 14 Figure 14: A typical Coxian-m distribution

  of retrieval transactions: The arrival process at each tier follows a Poisson distribution with arrival rate λ r /T . 2. A retrieval transaction requests the lift and the target vehicle: Under the parallel processing policy, a retrieval transaction requests the lift and the vehicle at the retrieval tier,

Fig. 15

 15 Fig.15 is the flowchart of the simulation process.

  The first step is the estimation of the load-dependent service rate of the fork-join node

	(Section 4.1), including two sub-steps.
	(a) We build a closed queueing network that contains the fork-join construct and define
	the state variable (see Section 4.1.1).
	(b) We approximate the service process of each node in the closed queueing network by
	a Coxian-m distribution, derive the state transition matrix, and calculate the system
	throughput (λ f j (•)) (see Section 4.1.2).
	2. The second step is the estimation of the performance measures of the FJQN (Section 4.2),
	including two sub-steps.

(a) We replace the fork-join node by a flow equivalent server (F ES) with exponential distributed load-dependent service time, whose service rate is µ F ES (•) = λ f j (•). Then, we get a non-product-form open queueing network since the service time of the µ l 2 node is generally distributed (see Section 4.2.1). (b) We use the Maximum Entropy Method (MEM) to derive the steady state probabilities of the open queueing network. Then, we obtain the performance measures of the FJQN (see Section 4.2.2).

Table 1 :

 1 System scenarios to be examined in simulation model

	S	1	2	3	4	5	6
	T	5	6	7	8	9	10
	A	35	42	50	58	65	72
	C	350	504	700	928	1170	1440

Table 2 :

 2 System scenarios for the comparison of sequential and parallel processing policies

	Small 1	2	3	4	5	6	7	8	9	10	11	12
	T		6			7			8			9
	A	30	42	54	35	49	63	40	56	72	45	63	91
	A T	5	7	9	5	7	9	5	7	9	5	7	9
	C	360	504	648	490	686	882	640	896	1152 810	1134 1638
	Large 13	14	15	16	17	18	19	20	21	22	23	24
	T		10			11			12			13
	A	50	70	90	55	77	99	60	84	108	65	91	117
	A T	5	7	9	5	7	9	5	7	9	5	7	9
	C	1000 1400 1800 1210 1694 2178 1440 2016 2592 1690 2366 3042

Table 3 :

 3 Average improvement percentage of the parallel processing policy over the sequential processing policy

	S	1	2	3	4	5	6	7	8	9	10	11	12
	I(%) 17.65 14.90 11.72 17.20 14.61 11.14 16.93 14.45 10.83 16.63 13.42 7.51
	S	13	14	15	16	17	18	19	20	21	22	23	24
	I(%) 15.09 11.55 5.51 14.

Table 4 :

 4 System parameters of an OSR case The results are presented in Fig 8. Under the current service load (λ r = 118 per hour),

	l	w	h	v v	a v	v h	a h	c h	c v
	0.65m	0.35m	0.67m	5m/s	7m/s 2	2m/s	1.25m/s 2 5.1s	2.4s
	We vary the retrieval transaction arrival rate varies from 50 to 200 per hour with a stepsize
	of 10.

Table 5 and

 5 Table 6 present the results of the simulation validation. The simulation results (R s ) are the average of 100 replications.

Table 5 :

 5 Simulation validation results of scenario one, two and three

	S		1			2			3
		R a	R s	ε(%)	R a	R s	ε(%)	R a	R s	ε(%)
	λ r = 50
	T r	25.52	24.31	4.98	27.56	26.45	4.20	29.62	28.99	2.17
	W r	3.44	3.75	8.27	4.09	4.56	10.31	4.82	5.45	11.56
	ρ l (%)	28.35	27.61	2.68	30.29	30.49	0.66	32.81	32.65	0.49
	ρ v (%) 4.14	4.13	0.24	3.86	3.84	0.52	3.70	3.68	0.54
	λ = 75
	T r	25.62	25.20	1.67	27.71	27.45	0.95	30.02	30.12	0.33
	W r	4.65	5.06	8.10	5.52	6.70	17.61	6.32	7.05	10.35
	ρ l (%)	40.21	40.31	0.25	42.65	42.87	0.51	46.13	45.65	1.05
	ρ v (%) 6.20	6.23	0.48	5.78	5.76	0.35	5.56	5.51	0.91
	λ = 100
	T r	25.83	26.15	1.22	28.00	28.56	1.96	30.58	31.49	2.89
	W r	5.73	6.51	11.98	6.79	8.20	17.20	7.73	8.65	10.64
	ρ l (%)	50.33	50.68	0.69	53.04	53.64	1.12	57.22	56.82	0.70
	ρ v (%) 8.27	8.31	0.48	7.71	7.67	0.52	7.41	7.39	0.27
	λ = 125
	T r	26.14	27.24	4.04	28.42	29.86	4.82	31.27	33.01	5.27
	W r	6.74	8.15	17.30	8.01	9.93	19.34	9.34	10.44	10.54
	ρ l (%)	58.96	59.77	1.36	61.77	62.87	1.75	66.38	66.20	0.27
	ρ v (%) 10.34	10.38	0.39	9.64	9.57	0.73	9.26	9.21	0.54
	λ = 150
	T r	26.57	28.56	6.97	29.00	31.44	7.76	32.18	34.82	7.58
	W r	7.75	9.83	21.16	9.24	11.96	22.74	10.94	12.52	12.62
	ρ l (%)	66.30	67.63	1.97	69.10	70.84	2.46	73.89	74.08	0.26
	ρ v (%) 12.41	12.45	0.32	11.57	11.52	0.43	11.11	11.06	0.45
	λ = 175
	T r	27.13	30.14	9.99	29.75	33.34	10.77	33.26	37.14	10.45
	W r	8.79	11.84	25.76	10.54	14.10	25.25	12.90	15.28	15.58
	ρ l (%)	72.54	74.38	2.47	75.23	77.51	2.94	80.01	80.50	0.61
	ρ v (%) 14.48	14.51	0.21	13.50	13.42	0.60	12.97	12.91	0.46
	λ = 200
	T r	27.82	32.13	13.41	30.69	35.78	14.23	34.69	40.03	13.34
	W r	9.90	14.09	29.74	11.95	16.34	26.87	15.44	18.93	18.44
	ρ l (%)	77.81	80.21	2.99	80.33	83.12	3.36	84.92	85.92	1.16
	ρ v (%) 16.54	16.60	0.36	15.42	15.35	0.46	14.82	14.79	0.20

V (t) av , V (t) ≤ v 2 v /a v .(3)The lift will reach its maximum velocity v v in the first case of Eq.(3), and can not reach v v in the second case. The deviation of Eq.(1) and Eq.(3) are given in Appendix B.

Acknowledge

This research is partially supported by the National Natural Science Foundation of China (grant number 71131004), (grant number 71471071), and Chutian Scholarship of Hubei Province of China.

A C C E P T E D M

A N U S C R I P T Lerher, T., Ekren, B. Y., Sari, Z., & Rosi, B. (2015b). Simulation analysis of shuttle based storage and retrieval systems. International Journal of Simulation Modeling, 14 , 48-59. Malmborg, C. J. (2002). Conceptualizing tools for autonomous vehicle storage and retrieval systems. International Journal of Production Research, 40 , 1807-1822. Malmborg, C. J. (2003a). Design optimization models for storage and retrieval systems using rail guided vehicles. Applied Mathematical Modelling, 27 , 929-941.

A C C E P T E D M A N U S C R I P T

Appendix A Fig. 9 and Fig. 10 show the storage and retrieval operations of tier-captive AVS/RSs under parallel processing policy.

A storage transaction arrives

Send requests for the lift and the vehicle

Is the vehicle available ?

Is the lift available ?

The load waits for the vehicle

The vehicle moves to the inbound buffer

Vehicle available

Is the load in the inbound buffer ?

The vehicle waits for the load The following is the queuing networks for tier-captive AVS/RS that the storage and retrieval transactions at the ground-floor tier do not need the lift. The service of the first tier is modeled as a M/G/1 queuing system, and the service of the rest part is modeled as a FJQN. We use the approximation method of [START_REF] Allen | Probability, statistics and queueing theory with computer science applications[END_REF] to analyze the M/G/1 and the approximation method

proposed in this study to analyze the FJQN.

Appendix D

Given a general distribution with a mean value τ and a squared coefficient of variation (scv) denoted by cv 2 , we can approximate it by a Coxian-2 (C 2 ) distribution if cv 2 ≥ 0.5, otherwise, we