A Capacitated Multi‐echelon Inventory Placement Model under Lead Time Constraints

We develop an inventory placement model in the context of general multi‐echelon supply chains where the delivery lead time promised to the customer must be respected. The delivery lead time is calculated based on the available stocks of the different input and output products in the different facilities and takes into account the purchasing lead times, the manufacturing lead times, and the transportation lead times. We assume finite manufacturing capacities and consider the interactions of manufacturing orders between time periods. Each facility manages the stocks of its input and output products. The size of customer orders and their arrival dates and due dates are assumed to be known as in many B2B situations. We perform extensive computational experiments to derive managerial insights. We also derive analytical insights regarding the manufacturing capacities to be installed and the impacts of the frequency of orders on the system cost.     

On vendor part delivery dates in a stochastic assembly system

This paper describes the development of a model for the determination of optimal mean part delivery dates in a stochastic assembly system for the objective of minimizing the expected cost of subassembly and part inventory. Parts are assembled at each station to a subassembly. The part delivery and processing times at assembly stations follow known probability distributions. An approximate solution technique based on the optimization of individual stations in isolation is developed. The approximation applies a correction factor, as a function of the variability in part delivery and processing time, cost parameters and number of stations, to the decisions from the single station solutions to compensate for interdependence between stations. Results indicate that this is an effective approach and yields good near-optimal solutions with very little computational effort. Insights regarding the effect of the type of distribution used, random processing times, variance of the distribution used and cost parameter values on part delivery dates are also reported.     

Single vs. multiple objective supplier selection in a make to order environment

The problem of allocation of orders for custom parts among suppliers in make to order manufacturing is formulated as a single- or multi-objective mixed integer program. Given a set of customer orders for products, the decision maker needs to decide from which supplier to purchase custom parts required for each customer order. The selection of suppliers is based on price and quality of purchased parts and reliability of on time delivery. The risk of defective or unreliable supplies is controlled by the maximum number of delivery patterns (combinations of suppliers delivery dates) for which the average defect rate or late delivery rate can be unacceptable. Furthermore, the quantity or business volume discounts offered by the suppliers are considered. Numerical examples are presented and some computational results are reported.     

DELIVERY GUARANTEES AND THE INTERDEPENDENCE OF MARKETING AND OPERATIONS

Delivery guarantees are an important element in a customer satisfaction program. When setting delivery guarantees, a firm must consider customer expectations as well as operational constraints. We develop a profit‐maximization model in which a firm's sales organization, with incomplete information on operations' status, solicits orders and quotes delivery dates. If obtained, orders are processed in a make‐to‐order facility, after which revenue is received, minus tardiness penalty if the delivery was later than quoted. We specify conditions for an optimal log‐linear decision rule and provide exact expressions for its effect on arrival rate, mean processing time, and mean cycle time.     

Container Scheduling: Complexity and Algorithms

We consider the transport of containers through a fleet of ships. Each ship has a capacity constraint limiting the total number of containers it can carry and each ship visits a given set of ports following a predetermined route. Each container has a release date at its origination port, and a due date at its destination port. A container has a size 1 or size 2; size 1 represents a 1 TEU (20‐foot equivalent unit) and size 2 represents 2 TEUs. The delivery time of a container is defined as the time when the ship that carries the container arrives at its destination port. We consider the problem of minimizing the maximum tardiness over all containers. We consider three scenarios with regard to the routes of the ships, namely, the ships having (i) identical, (ii) nested, and (iii) arbitrary routes. For each scenario, we consider different settings for origination ports, release dates, sizes of containers, and number of ports; we determine the computational complexity of various cases. We also provide a simple heuristic for some cases, with its worst case analysis. Finally, we discuss the relationship of our problems with other scheduling problems that are known to be open.     

TECHNICAL NOTE: A SIMPLE MODEL FOR OPTIMIZING THE SINGLE MACHINE EARLY/TARDY PROBLEM WITH SEQUENCE-DEPENDENT SETUPS

A simple mixed integer programming model for the N job/single machine scheduling problem with possibly sequence-dependent setup times, differing earliness/tardiness cost penalties, and variable due dates is proposed and evaluated for computational efficiency. Results indicated that the computational effort required to reach optimality rose with the number of jobs to be scheduled and with decreased variance in due dates. Though computational effort was significant for the largest problems solved, the model remained viable for optimizing research scale problems.     

Balancing Production and Distribution in Paper Manufacturing

A paper manufacturing plant minimizes its production cost by using long production runs that combine the demands from its various customers. As jobs are completed, they are released to distribution for delivery. Deliveries are made by railcars, each of which is dedicated to one customer. Long production runs imply that maximizing railcar utilization requires holding the cars over several days or holding completed jobs within the loading facility. Each of these methods imposes a cost onto the distribution function. We find how distribution can minimize its cost, given production's schedule. We then consider the problem of minimizing the company's overall cost of both production and distribution. A computational study using general data illustrates that the distribution cost is reduced by 25.80% through our proposed scheme, and that the overall cost is reduced an additional 4.40% through our coordination mechanism. An optimal algorithm is derived for a specific plant's operations.     

Integrated Order Scheduling and Packing

We consider an integrated production–distribution scheduling model in a make‐to‐order supply chain consisting of one supplier and one customer. The supplier receives a set of orders from the customer at the beginning of a planning horizon. The supplier needs to process all the orders at a single production line, pack the completed orders to form delivery batches, and deliver the batches to the customer. Each order has a weight, and the total weight of the orders packed in a batch must not exceed the capacity of the delivery batch. Each delivery batch incurs a fixed distribution cost. The problem is to find jointly a schedule for order processing and a way of packing completed orders to form delivery batches such that the total distribution cost (or equivalently, the number of delivery batches) is minimized subject to the constraint that a given customer service level is guaranteed. We consider two customer service constraints—meeting the given deadlines of the orders; or requiring the average delivery lead time of the orders to be within a given threshold. Several problems of the model with each of those constraints are considered. We clarify the complexity of each problem and develop fast heuristics for the NP‐hard problems and analyze their worst‐case performance bounds. Our computational results indicate that all the heuristics are capable of generating near optimal solutions quickly for the respective problems.     

Pool‐Point Distribution of Zero‐Inventory Products

We study zero‐inventory production‐distribution systems under pool‐point delivery. The zero‐inventory production and distribution paradigm is supported in a variety of industries in which a product cannot be inventoried because of its short shelf life. The advantages of pool‐point (or hub‐and‐spoke) distribution, explored extensively in the literature, include the efficient use of transportation resources and effective day‐to‐day management of operations. The setting of our analysis is as follows: A production facility (plant) with a finite production rate distributes its single product, which cannot be inventoried, to several pool points. Each pool point may require multiple truckloads to satisfy its customers' demand. A third‐party logistics provider then transports the product to individual customers surrounding each pool point. The production rate can be increased up to a certain limit by incurring additional cost. The delivery of the product is done by identical trucks, each having limited capacity and non‐negligible traveling time between the plant and the pool points. Our objective is to coordinate the production and transportation operations so that the total cost of production and distribution is minimized, while respecting the product lifetime and the delivery capacity constraints. This study attempts to develop intuition into zero‐inventory production‐distribution systems under pool‐point delivery by considering several variants of the above setting. These include multiple trucks, a modifiable production rate, and alternative objectives. Using a combination of theoretical analysis and computational experiments, we gain insights into optimizing the total cost of a production‐delivery plan by understanding the trade‐off between production and transportation.     

On the integration of due date setting and order release control

This paper calls for a paradigm shift in the production control literature away from assuming due date setting and order release are two independent decision levels. When order release is controlled, jobs do not enter the shop floor directly but are retained in a pre-shop pool and released to meet certain performance targets. This makes the setting of accurate planned release dates – the point at which jobs transition from the pool to the shop floor – a key consideration when setting due dates. We develop a new approach to estimating planned release dates to be embedded in the Workload Control (WLC) concept. Our approach is unique as it anticipates the release decision as part of the due date setting procedure. This makes a second independent release decision superfluous and avoids a major cause of tardiness – deviations between (i) the planned release date used when calculating the delivery time allowance and (ii) the actual, realised release date. Simulation is used to compare the performance of WLC using two decision levels with the new single-level approach where the release decision is anticipated when setting the due date. Performance improvements are shown to be robust to uncertainty in processing time estimates.     

Online algorithms for maximizing weighted throughput of unit jobs with temperature constraints

We consider a temperature-aware online deadline scheduling model. The objective is to schedule a number of unit jobs, with release dates, deadlines, weights and heat contributions, to maximize the weighted throughput subject to a temperature threshold. We first give an optimally competitive randomized algorithm. Then we give a constant competitive randomized algorithm that allows a tradeoff between the maximum heat contribution of jobs and the competitiveness. Finally we consider the multiple processor case and give several tight upper and lower bounds.     

Online pickup and delivery problem with constrained capacity to minimize latency

The online pickup and delivery problem is motivated by the takeaway order delivery on crowdsourcing delivery platform, which is a newly emerged online to offline business model based on sharing economy. Considering the features of crowdsourcing delivery, an online pickup and delivery problem with constrained capacity is proposed, whose objective is to route a delivery man with constrained capacity to serve requests released over time so as to minimize the total latency. We consider online point-to-point requests with single pickup location where each request has to be picked up at the single pickup location and delivered to its destination, and each request become available at its release time, which is not known in advance. The lower bound of this problem for various capacities is proved. Two online algorithms WR and WI are presented, the competitive ratios on a half line and on general metric space are proved respectively. Further, a computational study is conducted to compare the performance of these two online algorithms on random instances of general metric space. The result shows algorithm WR performs better than WI in random cases but not in the worst case.

     

A heuristic algorithm for minimizing maintenance workforce level

We develop a heuristic algorithm for minimizing the workforce level required to accommodate all the maintenance jobs requested within a specific time interval. Each maintenance job has its own release and due dates as well as the required man-days, and must be scheduled in a noninterrupted time interval, i.e. without preemption. However, the duration of each job is not fixed, but to be determined within a specific range. We show that this problem can be seen as a variant of the two-dimensional bin-packing problem with some additional constraints. We develop a non-linear mixed integer programming model for the proposed problem, and employ some well-known bin-packing algorithms to develop an efficient heuristic algorithm. In order to evaluate the performance of the proposed heuristic, we present a computationally efficient scheme for getting a good lower bound for the actual minimum. The computational experiment shows that the proposed heuristic algorithm performs quite satisfactorily in practice.     

Open Order Rescheduling in Job Shops with Demand Uncertainty: A Simulation Study

This paper addresses the problem of open order rescheduling in a job shop. Results are reported of experiments conducted in a simulation model of an 8-machine job shop. Four different order updating policies are examined. The due-date process is modeled to include several realistic features about the pattern of due-date variability. These features are parameterized and tested at several levels. Tardiness results indicate that open order rescheduling is beneficial only when allowances are loosely set. The results indicate that inventory performance is improved by order rescheduling, particularly in cases when due dates are revised to earlier times than originally forecast.     

Flexible time window management for attended home deliveries

In the competitive world of online retail, customers can choose from a selection of delivery time windows on a retailer’s website. Creating a set of suitable and cost-efficient delivery time windows is challenging, since customers want short time windows, but short time windows can increase delivery costs significantly. Furthermore, the acceptance of a request in a short time window can greatly restrict the ability to accommodate future requests. In this paper, we present customer acceptance mechanisms that enable flexible time window management in the booking of time-window based attended home deliveries. We build tentative delivery routes and check which time windows are feasible for each new customer request. We offer the feasible long delivery time windows and let our approaches decide when to offer short time windows. Our approaches differ in the information they consider with regard to customer characteristics as well as detailed characteristics of the evolving route plan. We perform a computational study to investigate the approaches’ ability to offer short time windows and still allow for a large number of customers to be served. We consider various demand scenarios, partially derived from real order data provided by a German online supermarket.     

Sequential Estimation of Dynamic Discrete Games

This paper studies the estimation of dynamic discrete games of incomplete information. Two main econometric issues appear in the estimation of these models: the indeterminacy problem associated with the existence of multiple equilibria and the computational burden in the solution of the game. We propose a class of pseudo maximum likelihood (PML) estimators that deals with these problems, and we study the asymptotic and finite sample properties of several estimators in this class. We first focus on two‐step PML estimators, which, although they are attractive for their computational simplicity, have some important limitations: they are seriously biased in small samples; they require consistent nonparametric estimators of players' choice probabilities in the first step, which are not always available; and they are asymptotically inefficient. Second, we show that a recursive extension of the two‐step PML, which we call nested pseudo likelihood (NPL), addresses those drawbacks at a relatively small additional computational cost. The NPL estimator is particularly useful in applications where consistent nonparametric estimates of choice probabilities either are not available or are very imprecise, e.g., models with permanent unobserved heterogeneity. Finally, we illustrate these methods in Monte Carlo experiments and in an empirical application to a model of firm entry and exit in oligopoly markets using Chilean data from several retail industries.     

A state-of-art survey of static scheduling research involving due dates

This paper provides a guided tour of those scheduling techniques in which the performance measures bear in one way or the other on job due dates. The classification is based on scheduling objectives. Within each category the theoretical developments and computational experiences have been reviewed.     

An Experimental Comparison of Time-Based and Economic-Based Scheduling Methods to Maximize Net Present Value*

In the past, performance in dynamic-scheduling environments was primarily measured in terms of time or physical shop characteristics. Objectives such as mean tardiness, flow time, and work-in-process inventory were commonly used. Today, there is increasing interest in the use of more advanced economic performance measures. These measures have the more comprehensive objective of maximizing ownership wealth by economically scheduling jobs and tasks. This study presents a large-scale experiment testing time-based and economic-based scheduling methods in a dynamic job shop. These methods are evaluated on their ability to maximize net present value (NPV). The study considers the just-in-time (JIT) delivery environment. The job shop is hypothetical, but is based on models of real production situations. Results show that the use of very detailed economic information in a sophisticated manner generally improves economic performance. Where due dates are easy to achieve, however, time-based scheduling methods are at least as good as those based on economics. Also, where utilization is high and due dates tight, early cost information in release and dispatch is detrimental to schedule value.     

On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity

We study the problem of on-line scheduling jobs with release dates on a batch machine of finite capacity with the objective of minimizing the makespan. We generalize several existing algorithms for the problem to a class of on-line algorithms that are 2-competitive for any arbitrary finite machine capacity. Then, we show that one of these generalized algorithms is in fact 7/4-competitive for machine capacity 2. This is the first on-line algorithm for a finite machine capacity with competitive ratio less than 2.This research is substantially supported by a grant from City Univ. of Hong Kong (Grant No. 7001119). The second author is supported by this grant and by the Natural Science Foundation of China.     

The three-dimensional matching problem in Kalmanson matrices

We investigate the computational complexity of several special cases of the three-dimensional matching problem where the costs are decomposable and determined by a so-called Kalmanson matrix. For the minimization version we develop an efficient polynomial time algorithm that is based on dynamic programming. For the maximization version, we show that there is a universally optimal matching (whose structure is independent of the particular Kalmanson matrix).