Scheduling of depalletizing and truck loading operations in a food distribution system

This paper studies a scheduling problem arising in a beef distribution system where pallets of various types of beef products in the warehouse are first depalletized and then individual cases are loaded via conveyors to the trucks which deliver beef products to various customers. Given each customer's demand for each type of beef, the problem is to find a depalletizing and truck loading schedule that fills all the demands at a minimum total cost. We first show that the general problem where there are multiple trucks and each truck covers multiple customers is strongly NP‐hard. Then we propose polynomial‐time algorithms for the case where there are multiple trucks, each covering only one customer, and the case where there is only one truck covering multiple customers. We also develop an optimal dynamic programming algorithm and a heuristic for solving the general problem. By comparing to the optimal solutions generated by the dynamic programming algorithm, the heuristic is shown to be capable of generating near optimal solutions quickly. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Computational analysis of MMAP[K]/PH[K]/1 queues with a mixed FCFS and LCFS service discipline

This paper studies a queueing system with a Markov arrival process with marked arrivals and PH‐distribution service times for each type of customer. Customers (regardless of their types) are served on a mixed first‐come‐first‐served (FCFS) and last‐come‐first‐served (LCFS) nonpreemptive basis. That is, when the queue length is N (a positive integer) or less, customers are served on an FCFS basis; otherwise, customers are served on an LCFS basis. The focus is on the stationary distribution of queue strings, busy periods, and waiting times of individual types of customers. A computational approach is developed for computing the stationary distribution of queue strings, the mean of busy period, and the means and variances of waiting times. The relationship between these performance measures and the threshold number N is analyzed in depth numerically. It is found that the variance of the virtual (actual) waiting time of an arbitrary customer can be reduced by increasing N. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 399–421, 2000     

Waiting time analysis for a queueing system with time‐limited service and exponential timer

We consider a single‐queue with exhaustive or gated time‐limited services and server vacations, in which the length of each service period at the queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then takes vacations. The customer whose service is interrupted due to the timer expiration may be attended according to nonpreemptive or preemptive service disciplines. For the M/G/1 exhaustive/gated time‐limited service queueing system with an exponential timer and four typical preemptive/nonpreemptive service disciplines, we derive the Laplace—Stieltjes transforms and the moment formulas for waiting times and sojourn times through a unified approach, and provide some new results for these time‐limited service disciplines. © John Wiley & Sons, Inc. Naval Research Logistics 48: 638–651, 2001.     

Scheduling a production–distribution system to optimize the tradeoff between delivery tardiness and distribution cost

We consider a make‐to‐order production–distribution system with one supplier and one or more customers. A set of orders with due dates needs to be processed by the supplier and delivered to the customers upon completion. The supplier can process one order at a time without preemption. Each customer is at a distinct location and only orders from the same customer can be batched together for delivery. Each delivery shipment has a capacity limit and incurs a distribution cost. The problem is to find a joint schedule of order processing at the supplier and order delivery from the supplier to the customers that optimizes an objective function involving the maximum delivery tardiness and the total distribution cost. We first study the solvability of various cases of the problem by either providing an efficient algorithm or proving the intractability of the problem. We then develop a fast heuristic for the general problem. We show that the heuristic is asymptotically optimal as the number of orders goes to infinity. We also evaluate the performance of the heuristic computationally by using lower bounds obtained by a column generation approach. Our results indicate that the heuristic is capable of generating near optimal solutions quickly. Finally, we study the value of production–distribution integration by comparing our integrated approach with two sequential approaches where scheduling decisions for order processing are made first, followed by order delivery decisions, with no or only partial integration of the two decisions. We show that in many cases, the integrated approach performs significantly better than the sequential approaches. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Customer delays in M/M/c repair systems with spares

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.     

Stochastic analysis of a single server retrial queue with general retrial times

Retrial queueing systems are widely used in teletraffic theory and computer and communication networks. Although there has been a rapid growth in the literature on retrial queueing systems, the research on retrial queues with nonexponential retrial times is very limited. This paper is concerned with the analytical treatment of an M/G/1 retrial queue with general retrial times. Our queueing model is different from most single server retrial queueing models in several respectives. First, customers who find the server busy are queued in the orbit in accordance with an FCFS (first‐come‐first‐served) discipline and only the customer at the head of the queue is allowed for access to the server. Besides, a retrial time begins (if applicable) only when the server completes a service rather upon a service attempt failure. We carry out an extensive analysis of the queue, including a necessary and sufficient condition for the system to be stable, the steady state distribution of the server state and the orbit length, the waiting time distribution, the busy period, and other related quantities. Finally, we study the joint distribution of the server state and the orbit length in non‐stationary regime. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 561–581, 1999     

The effect of catastrophes on the strategic customer behavior in queueing systems

We consider the single server Markovian queue subject to Poisson generated catastrophes. Whenever a catastrophe occurs, all customers are forced to abandon the system, the server is rendered inoperative and an exponential repair time is set on. During the repair time new arrivals are allowed to join the system. We assume that the arriving customers decide whether to join the system or balk, based on a natural linear reward‐cost structure with two types of rewards: A (usual) service reward for those customers that receive service and a (compensation) failure reward for those customers that are forced to abandon the system due to a catastrophe. We study the strategic behavior of the customers regarding balking and derive the corresponding (Nash) equilibrium strategies for the observable and unobservable cases. We show that both types of strategic behavior may be optimal: to avoid the crowd or to follow it. The crucial factor that determines the type of customer behavior is the relative value of the service reward to the failure compensation. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A sequential scheduling problem with impatient jobs

There are n customers that need to be served. Customer i will only wait in queue for an exponentially distributed time with rate λ_i before departing the system. The service time of customer i has distribution F_i, and on completion of service of customer i a positive reward r_i is earned. There is a single server and the problem is to choose, after each service completion, which currently in queue customer to serve next so as to maximize the expected total return. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 659–663, 2015     

Simultaneous price,location, and capacity decisions on a line of time‐sensitive customers

Consider a monopolist who sells a single product to time‐sensitive customers located on a line segment. Customers send their orders to the nearest distribution facility, where the firm processes (customizes) these orders on a first‐come, first‐served basis before delivering them. We examine how the monopolist would locate its facilities, set their capacities, and price the product offered to maximize profits. We explicitly model customers' waiting costs due to both shipping lead times and queueing congestion delays and allow each customer to self‐select whether she orders or not, based on her reservation price. We first analyze the single‐facility problem and derive a number of interesting insights regarding the optimal solution. We show, for instance, that the optimal capacity relates to the square root of the customer volume and that the optimal price relates additively to the capacity and transportation delay costs. We also compare our solutions to a similar problem without congestion effects. We then utilize our single‐facility results to treat the multi‐facility problem. We characterize the optimal policy for serving a fixed interval of customers from multiple facilities when customers are uniformly distributed on a line. We also show how as the length of the customer interval increases, the optimal policy relates to the single‐facility problem of maximizing expected profit per unit distance. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Bernoulli抵消策略的负顾客的M/G/1排队系统

负顾客的排队模型是排队论近年来的新兴分支。文中引入了带有B ernou lli抵消策略的负顾客的M/G/1排队模型,即到达的负顾客以概率p抵消队首正在接受服务的正顾客,以1-p的概率抵消队尾的正顾客,利用补充变量法,状态转移法和L变换,最后得到系统稳态队长的概率母函数。     

Machine maintenance with workload considerations

Machine maintenance is modeled in the setting of a single‐server queue. Machine deterioration corresponds to slower service rates and failure. This leads to higher congestion and an increase in customer holding costs. The decision‐maker decides when to perform maintenance, which may be done pre‐emptively; before catastrophic failures. Similar to classic maintenance control models, the information available to the decision‐maker includes the state of the server. Unlike classic models, the information also includes the number of customers in queue. Considered are both a repair model and a replacement model. In the repair model, with random replacement times, fixed costs are assumed to be constant in the server state. In the replacement model, both constant and variable fixed costs are considered. It is shown in general that the optimal maintenance policies have switching curve structure that is monotone in the server state. However, the switching curve policies for the repair model are not always monotone in the number of customers in the queue. Numerical examples and two heuristics are also presented. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Double Mover–Stayer model on customer switching in telecommunications industry

Customer acquisition and customer retention are the most important challenges in the increasingly competitive telecommunications industry. Traditional studies of customer switching always assume that customers are homogeneous, and thus that model customer switching behavior follows a Markov formulation. However, this postulation is obviously inappropriate in most instances. Blumen et al. (Cornell Studies of Industrial and Labor Relations, Cornell University Press, Ithaca, NY, 1955) developed the Mover–Stayer (MS) model, a generalization of the Markov chain model, to relax the requirement of homogeneity and allow the presence of heterogeneity with two different types of individuals—“stayers,” who purchase the same kinds of products or services throughout the entire observation period; and “movers,” who look for variety in products or services over time. There are two purpose of this article. First, we extend the MS model to a Double Mover‐Stayer (DMS) model by assuming the existence of three types of individuals in the market: (1) stable and loyal customers, who have stable usage within the same company; (2) instable but loyal customers, whose usage varies within the same company over time; and (3) disloyal customers, who switch from one company to another to seek for new experiences or/and benefits. We also propose an estimation method for the DMS model. Second, we apply the DMS model to telecommunications data and demonstrate how it can be used for pattern identification, hidden knowledge discovery, and decision making. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Production and transport logistics scheduling with two transport mode choices

This paper considers a new class of scheduling problems arising in logistics systems in which two different transportation modes are available at the stage of product delivery. The mode with the shorter transportation time charges a higher cost. Each job ordered by the customer is first processed in the manufacturing facility and then transported to the customer. There is a due date for each job to arrive to the customer. Our approach integrates the machine scheduling problem in the manufacturing stage with the transportation mode selection problem in the delivery stage to achieve the global maximum benefit. In addition to studying the NP‐hard special case in which no tardy job is allowed, we consider in detail the problem when minimizing the sum of the total transportation cost and the total weighted tardiness cost is the objective. We provide a branch and bound algorithm with two different lower bounds. The effectiveness of the two lower bounds is discussed and compared. We also provide a mathematical model that is solvable by CPLEX. Computational results show that our branch and bound algorithm is more efficient than CPLEX. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Transshipment through crossdocks with inventory and time windows

A major challenge in making supply meet demand is to coordinate transshipments across the supply chain to reduce costs and increase service levels in the face of demand fluctuations, short lead times, warehouse limitations, and transportation and inventory costs. In particular, transshipment through crossdocks, where just‐in‐time objectives prevail, requires precise scheduling between suppliers, crossdocks, and customers. In this work, we study the transshipment problem with supplier and customer time windows where flow is constrained by transportation schedules and warehouse capacities. Transportation is provided by fixed or flexible schedules and lot‐sizing is dealt with through multiple shipments. We develop polynomial‐time algorithms or, otherwise, provide the complexity of the problems studied. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Priority and dynamic scheduling in a make‐to‐stock queue with hyperexponential demand

We consider the scheduling problem in a make‐to‐stock queue with two demand classes that can be differentiated based on their variability. One class experiences Poisson arrivals and the other class experiences hyperexponential renewal arrivals. We provide an exact analysis of the case where the demand class with higher variability is given non‐preemptive priority. The results are then used to compare the inventory cost performance of three scheduling disciplines, first‐come first‐serve and priority to either class. We then build on an existing dynamic scheduling heuristic to propose a modification that works well for our system. Extensions of the heuristic to more than two classes and to the case where demand state is known are also discussed. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

Production scheduling with history‐dependent setup times

We consider a parallel‐machine scheduling problem with jobs that require setups. The duration of a setup does not depend only on the job just completed but on a number of preceding jobs. These setup times are referred to as history‐dependent. Such a scheduling problem is often encountered in the food processing industry as well as in other process industries. In our model, we consider two types of setup times—a regular setup time and a major setup time that becomes necessary after several “hard‐to‐clean” jobs have been processed on the same machine. We consider multiple objectives, including facility utilization, flexibility, number of major setups, and tardiness. We solve several special cases assuming predetermined job sequences and propose strongly polynomial time algorithms to determine the optimal timing of the major setups for given job sequences. We also extend our analysis to develop pseudopolynomial time algorithms for cases with additional objectives, including the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Coordinated scheduling of customer orders for quick response

The scheduling problem addressed in this paper concerns a manufacturer who produces a variety of product types and operates in a make‐to‐order environment. Each customer order consists of known quantities of the different product types, and must be delivered as a single shipment. Periodically the manufacturer schedules the accumulated and unscheduled customer orders. Instances of this problem occur across industries in manufacturing as well as in service environments. In this paper we show that the problem of minimizing the weighted sum of customer order delivery times is unary NP‐hard. We characterize the optimal schedule, solve several special cases of the problem, derive tight lower bounds, and propose several heuristic solutions. We report the results of a set of computational experiments to evaluate the lower bounding procedures and the heuristics, and to determine optimal solutions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Competitive location and capacity decisions for firms serving time‐sensitive customers

In this article we explore how two competing firms locate and set capacities to serve time‐sensitive customers. Because customers are time‐sensitive, they may decline to place an order from either competitor if their expected waiting time is large. We develop a two‐stage game where firms set capacities and then locations, and show that three types of subgame perfect equilibria are possible: local monopoly (in which each customer is served by a single firm, but some customers may be left unserved), constrained local monopoly (in which firms serve the entire interval of customers but do not compete with each other), and constrained competition (in which firms also serve the entire interval of customers, but now compete for some customers). We perform a comparative statics analysis to illustrate differences in the equilibrium behavior of a duopolist and a coordinated monopolist. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Workload distribution of discrete‐time parallel queues with two servers

We study discrete‐time, parallel queues with two identical servers. Customers arrive randomly at the system and join the queue with the shortest workload that is defined as the total service time required for the server to complete all the customers in the queue. The arrivals are assumed to follow a geometric distribution and the service times are assumed to have a general distribution. It is a no‐jockeying queue. The two‐dimensional state space is truncated into a banded array. The resulting modified queue is studied using the method of probability generating function (pgf) The workload distribution in steady state is obtained in form of pgf. A special case where the service time is a deterministic constant is further investigated. Numerical examples are illustrated. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 440–454, 2000     

Expected time delay in multi‐item inventory systems with correlated demands

This paper considers multi‐item inventory systems where a customer order may require several different items (i.e., demands are correlated across items) and customer satisfaction is measured by the time delays seen by the customers. Most inventory models on time delay in the literature assume each demand only requires one item (i.e., demands are not correlated across items or are independent). In this paper, we derive an exact expression for the expected total time delay. We show that when items are actually correlated, assuming items are independent leads to an overestimate of the total time delay. However, (1) it is extremely difficult in practice to obtain the demand information for all demand types (especially in a system with tens of thousands of part numbers), and (2) the problem becomes too complicated to be of practical interest when the correlation is considered. We then explore the possibility of including the demand information partially and develop bounds for the time delays. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 671–688, 1999