优化交货期窗口的两阶段供应链排序问题

研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.     

储存时间有上限的两阶段供应链排序问题

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.     

需求率依赖于库存水平的离散性库存费的库存模型

传统的库存控制模型都视需求率为固定不变的,放松了这个假定,通过考虑库存费为存储时间的阶梯函数的情形:(1)全单位库存费用,(2)增量库存费用,并且在需求率依赖于库存水平,当库存水平下降到一定程度时,需求率变为常数的形式下,把变化的订购费引入,发展了两个离散性库存费的变质物品的库存控制模型。在模型中允许周期末库存水平不为零,并且提出了最优解的算法。     

Time and inventory dependent optimal maintenance policies for single machine workstations: An MDP approach

In this work the problem of obtaining an optimal maintenance policy for a single-machine, single-product workstation that deteriorates over time is addressed, using Markov Decision Process (MDP) models. Two models are proposed. The decision criteria for the first model is based on the cost of performing maintenance, the cost of repairing a failed machine and the cost of holding inventory while the machine is not available for production. For the second model the cost of holding inventory is replaced by the cost of not satisfying the demand. The processing time of jobs, inter-arrival times of jobs or units of demand, and the failure times are assumed to be random. The results show that in order to make better maintenance decisions the interaction between the inventory (whether in process or final), and the number of shifts that the machine has been working without restoration, has to be taken into account. If this interaction is considered, the long-run operational costs are reduced significantly. Moreover, structural properties of the optimal policies of the models are obtained after imposing conditions on the parameters of the models and on the distribution of the lifetime of a recently restored machine.     

Consolidating or non-consolidating queues: A game theoretic queueing model with holding costs

We consider a two-server queueing system in which the servers choose their service rate based on the demand and holding cost allocation scheme offered by the demand generating entity. We provide an optimal holding cost allocation scheme that leads to the maximum possible service rate for each of a pooled and a split system. Our results suggest that careful allocation of holding costs can create incentives that enable minimum turnaround times using a common queue.     

Improved vehicle scheduling in public transport through systematic changes in the time-table

Vehicle scheduling for a fixed time-table is easy to formulate and solve as a minimal-cost-flow problem. Normally, however, there is considerable flexibility in the time-table. We propose here a method for exploiting this flexibility in order to improve the vehicle scheduling.A given set of trips must be assigned to a fleet of identical vehicles, starting from a common garage. Each trip is characterized by initial stop, final stop, duration, earliest departure time, and latest departure time.The problem is to decide which vehicle should be assigned to each individual trip and when the trip should start, so that a generalized cost is minimized.The minimum-cost-flow problem is first solved for the ‘kernels’ of every trip in order to make clear when the critical time-periods occur and obtain a lower bound for the solution. The kernel is defined as a trip that starts at the latest possible departure time and finishes at the earliest possible arriving time.The departure time for each trip is then chosen, thereby increasing the chances of obtaining a good schedule. The minimum-cost-flow problem is then solved for this fixed time-table.Finally, the departure times for each vehicle are adjusted (blocked) so that each vehicle (and driver) is efficiently used. This method is used as an integral part of the Volvo Traffic Planning Package.     

Note: An application of the EOQ model with nonlinear holding cost to inventory management of perishables

In this note, we consider a variation of the economic order quantity (EOQ) model where cumulative holding cost is a nonlinear function of time. This problem has been studied by Weiss [Weiss, H., 1982. Economic order quantity models with nonlinear holding costs. European Journal of Operational Research 9, 56–60], and we here show how it is an approximation of the optimal order quantity for perishable goods, such as milk, and produce, sold in small to medium size grocery stores where there are delivery surcharges due to infrequent ordering, and managers frequently utilize markdowns to stabilize demand as the product’s expiration date nears. We show how the holding cost curve parameters can be estimated via a regression approach from the product’s usual holding cost (storage plus capital costs), lifetime, and markdown policy. We show in a numerical study that the model provides significant improvement in cost vis-à-vis the classic EOQ model, with a median improvement of 40%. This improvement is more significant for higher daily demand rate, lower holding cost, shorter lifetime, and a markdown policy with steeper discounts.     

Optimal transshipments and reassignments under periodic or cyclic holding cost accounting

In a centrally managed system, inventory at a retailer can be transshipped to a stocked-out retailer to meet demand. As the inventory at the former retailer may be demanded by future customers of that retailer and transshipment time/cost is non-negligible, it can be more profitable to not transship in some situations. When unsatisfied demand is backordered, reassignment of inventory to a previously backordered demand can perhaps become profitable as demand uncertainty resolves over time. Despite this intuition, we prove that no reassignments are necessary for cost optimality under periodic holding cost accounting in a two-retailer system. This remains valid for multi-retailer systems according to numerical analyses. When holding costs are accounted for only at the end of each replenishment cycle, reassignments are necessary for optimality but insignificant in reducing the total cost. In most instances tested, the decrease in total cost from reassignments is below 2% for end of cycle holding cost accounting. These results simplify transshipment policies and facilitate finding good policies in both implementation and future studies, as reassignments can be omitted from consideration in optimization models under periodic holding cost accounting and in approximation models under cyclical cost accounting.     

A new approach to find project characteristics and multiple possible critical paths in a fuzzy project network

Graphs are widely used to represent data and relationships. Among all graphs, a particularly useful family is the family of trees. In this paper, we utilize a rooted tree to describe a fuzzy project network as it enables simplification in finding earliest starting times and trapezoidal fuzzy numbers to express the operation times for all activities in project network. As there is an increasing demand that the decision maker needs “Multiple possible critical paths” to decrease the decision risk for project management, in this paper, we introduce an effective graphical method to compute project characteristics such as total float, earliest and latest times of activities in fuzzy project network and a new ranking to find possible critical paths. Numerical example is provided to explain the proposed procedure in detail; the results have shown that the procedure is very useful and flexible in finding total floats. By comparing the critical paths obtained by this method with the previous methods, it is shown that the proposed method is effective in finding possible critical paths.     

Single-machine common due window assignment and scheduling to minimize the total cost

In this paper we consider a single-machine common due window assignment and scheduling problem with batch delivery cost. The starting time and size of the due window are decision variables. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a job sequence, a delivery date for each job, and a starting time and a size for the due window that jointly minimize the total cost comprising earliness, weighted number of tardy jobs, job holding, due window starting time and size, and batch delivery. We provide some properties of the optimal solution and present polynomial-time algorithms for the problem.     

Computing latest starting times of activities in interval-valued networks with minimal time lags

This paper deals with problems of determining possible values of earliest and latest starting times of an activity in networks with minimal time lags and imprecise durations that are represented by means of interval or fuzzy numbers. Although minimal time lags are practical in different projects, former researchers have not considered these problems.After proposing propositions which reduce the search space, a novel polynomial algorithm is presented to compute intervals of possible values of latest starting times in interval-valued networks with minimal time lags. Then, the results are extended to networks with fuzzy durations.     

Designing a new computational approach of partial backlogging on the economic production quantity model for deteriorating items with non-linear holding cost under inflationary conditions

This paper discusses the production inventory model over an infinite time horizon. Here we consider demand as a function of stock and time. Deterioration is a function of time and time-varying production. Our objective is to minimize the total cost which is a function of set up cost, holding cost, shortage cost, and opportunity cost due to lost sales. The traditional costs such as purchasing cost, shortage cost and opportunity cost due to lost sales are kept constant. We consider holding cost to be a non-linear function of time. Shortages are allowed and are partially backlogged. Here, time durations are the decision variables. Numerical examples are given to illustrate the model.     

一种计算工作时间参数新方法

为了编制和优化施工进度计划,计算构成施工项目的各项工作最早开始时间、最迟开始时间、最早完成时间、最迟完成时间、总时差和自由时差等时间参数十分重要.提出了一种计算工作时间参数新方法.该方法以工作完成时间为决策变量,通过建立和求解线性规划模型来得到各种工作时间参数.其建模思路清晰,不需绘制网络图,能用通用办公软件EXCEL求解.模拟计算表明,用该方法与用标准网络计划技术计算出的工作时间参数完全一致.     

Continuous-review,lost-sales inventory models with Poisson demand,a fixed lead time and no fixed order cost

This paper considers continuous-review lost-sales inventory models with no fixed order cost and a Poisson demand process. There is a holding cost per unit per unit time and a lost sales cost per unit. The objective is to minimise the long run total cost. Base stock policies are, in general, sub-optimal under lost sales. The optimal policy would have to take full account of the remaining lead times on all the orders currently outstanding and such a policy would be too complex to analyse, let alone implement. This paper considers policies which make use of the observation that, for lost sales models, base stock policies can be improved by imposing a delay between the placement of successive orders. The performance of these policies is compared with that of the corresponding base stock policy and also with the policy of ordering at fixed and regular intervals of time.     

Determining optimal order splitting and reorder level for N-supplier inventory systems

This paper considers multiple-supplier single-item inventory systems, where the item acquisition lead times of suppliers and demand arrival are random, and backorder is allowed. The acquisition takes place when the inventory level depletes to a reorder level, and the order is split among multiple suppliers. The acquisition lead times may have different distributions, the unit purchasing prices from suppliers may be different, and thus the order quantities for different suppliers may be different. The problem is to determine the reorder level and order quantity for each supplier so that the expected total cost per unit time, consisting of the fixed ordering cost, procurement cost, inventory holding cost and shortage cost, is minimized. We develop a mathematical model describing the system in detail. We also conduct extensive numerical experiments to analyze the advantages and distinct characteristics of multiple-supplier systems.     

A two-stage heuristic for disassembly scheduling with assembly product structure

Disassembly scheduling, one of the important operational problems in disassembly systems, is the problem of determining the ordering and disassembly schedules of used or end-of-life products while satisfying the demand of their parts or components over a certain planning horizon. This paper considers products with assembly structure for the objective of minimizing the sum of purchase, set up, inventory holding, and disassembly operation costs, and suggests a two-stage heuristic, in which an initial solution is obtained in the form of the minimal latest ordering and disassembly schedule, and then improved iteratively considering trade-offs among different cost factors. To show the performance of the heuristic, computational experiments were done on the example obtained from the literature and a number of randomly generated test problems, and the results show that the heuristic can give optimal or very near-optimal solutions within very short computation times.     

Inventory models with managerial policy independent of demand

This paper is an extension of two papers. The first of these, published in European Journal of Operational Research, 2007, 112-120 is by Deng et al. (2007) and concerns inventory models for deteriorating items with ramp type demand. The second, published in Computer & Industrial Engineering, 2009, 1296-1300 is by Cheng and Wang (2009) and concerns inventory models for deteriorating items with trapezoidal type demand. The purpose of this paper is threefold. First, this paper will show that the optimal solution is independent of the demand considered in the two previous papers. Second, several replenishment cycles were considered during the finite time horizon, to balance the set-up cost with the sum of the deteriorated cost, holding cost, and shortage cost. Third, this paper will examine the same numerical example in Cheng and Wang (2009) to show that this new approach will result in the saving of 84.39%.     

带有可变库存费用和短缺的变质性物品的经济批量模型

传统的经济批量模型通常都假定物品的库存费用是固定不变的.放松了这个假定,通过考虑库存费用的两种可能变化情形即(A)库存费的变化率为存储时间的函数;(B)库存费的变化率为库存量的函数,并在需求线性依赖于库存水平的形式下,发展了两个变库存费的变质性物品的经济批量模型.在模型中允许短缺发生且假定短缺完全拖后,理论上证明了模型具有唯一的整体最优解,揭示了库存费的变化对库存系统最优订货策略的影响.     

A column generation algorithm for the vehicle routing problem with soft time windows

The Vehicle Routing Problem with Time Windows consists of computing a minimum cost set of routes for a fleet of vehicles of limited capacity visiting a given set of customers with known demand, with the additional constraint that each customer must be visited in a specified time window. We consider the case in which time window constraints are relaxed into “soft” constraints, that is penalty terms are added to the solution cost whenever a vehicle serves a customer outside of his time window. We present a branch-and-price algorithm which is the first exact optimization algorithm for this problem.     

Deterministic models of perishable inventory with stock-dependent demand rate and nonlinear holding cost

This paper deals with an extended EOQ-type inventory model for a perishable product where the demand rate is a function of the on-hand inventory. The traditional parameters of unit item cost and ordering cost are kept constant; but the holding cost is treated as (i) a nonlinear function of the length of time for which the item is held in stock, and (ii) a functional form of the amount of the on-hand inventory. The approximate optimal solution in both the cases are derived. Computational results are presented indicating the effects of nonlinearity in holding costs.