Coordinated Replenishments from a Common Supplier

Coordinated replenishment strategies may be implemented by jointly ordering multiple items from a common supplier. A major benefit of coordinated replenishment is that it increases the size of shipments, permitting the buyer to enjoy transportation economies without a major increase in average inventory levels. The coordinated replenishment problem is complex because side constraints govern the attainment of transportation rate breaks. The problem is further complicated by the presence of purchase quantity discount opportunities. Thus, the buyer must decide which items to order independently, which items to include in a group order, and the order quantities of each item, governed by the frequency of independent or group orders. We present a mathematical model and a heuristic solution procedure that provide analytical support to the buyer seeking to minimize total costs of replenishing multiple items from a common supplier. The relevant costs are purchase prices, ordering costs, holding costs, and transportation costs. Coordinated replenishment provides nearly a 30 percent reduction in controllable costs relative to independent control. Experimentation with the heuristic has yielded optimal solutions over 88 percent of the time. When optimality was not obtained, the mean penalty was much less than one percent. The average heuristic search was more than two orders of magnitude faster than branch and bound, even for small problems, and possessed a much tighter distribution around the mean search time.     

Optimal Selection Strategy for the Group Interview Problem

We propose a more generalized version of the secretary problem, called the group interview problem, in which each group contains several alternatives and each group of alternatives is presented and evaluated sequentially over time. Using the assumptions corresponding to the classical secretary problem, we derive an optimal selection strategy which maximizes the probability of winning or selecting the single best choice in a given sequence of groups. We further address the problem of choosing at the beginning of the evaluation process a sequence of groups to maximize the winning probability. Because of formidable computational requirements to obtain an optimal solution to this sequencing problem, we then develop a heuristic algorithm based on several properties inherent in an optimal selection strategy. The heuristic procedure is evaluated experimentally using Monte Carlo simulation and is shown to be effective in obtaining near-optimal (within 5 percent) solutions.     

一种考虑动态时间窗的满载问题模型及算法

针对时间约束在满载问题中的复杂性,建立了一个考虑装载时间和次序的具有动态时间窗的满载车辆调度模型,并给出了一个基于动态构造原理的启发式算法。该模型和算法改进了以往满载问题中对时间窗的考虑,使得求解更具有实际派车意义,并且该算法通过参数调整,经过少量迭代即可快速求得最小化总成本的满意解。     

A comparison of fixed and dynamic pricing policies in revenue management

We consider the problem of selling a fixed capacity or inventory of items over a finite selling period. Earlier research has shown that using a properly set fixed price during the selling period is asymptotically optimal as the demand potential and capacity grow large and that dynamic pricing has only a secondary effect on revenues. However, additional revenue improvements through dynamic pricing can be important in practice and need to be further explored. We suggest two simple dynamic heuristics that continuously update prices based on remaining inventory and time in the selling period. The first heuristic is based on approximating the optimal expected revenue function and the second heuristic is based on the solution of the deterministic version of the problem. We show through a numerical study that the revenue impact of using these dynamic pricing heuristics rather than fixed pricing may be substantial. In particular, the first heuristic has a consistent and remarkable performance leading to at most 0.2% gap compared to optimal dynamic pricing. We also show that the benefits of these dynamic pricing heuristics persist under a periodic setting. This is especially true for the first heuristic for which the performance is monotone in the frequency of price changes. We conclude that dynamic pricing should be considered as a more favorable option in practice.     

A note on a well-known dispatching rule to minimize total tardiness

The single machine tardiness problem is considered. We clarify and correct an earlier result related to the Modified Due Date (MDD) Rule of Baker and Bertrand and show that a heuristic does not always satisfy an optimal sequence. However, we present some interesting special cases of optimal sequences that do satisfy the MDD Rule. We believe this note is important because the MDD Rule is still considered to be one of the most efficient rules to minimize the single machine tardiness problem. Because of its dispatching nature and simplicity, the MDD Rule is found to be very practical. It is widely applied in both static and dynamic job shop and industrial settings where setup times if any are negligible or included in the job processing times and hence not an issue.     

An efficient heuristic procedure for solving the layout design problem

The limited ability of schematic procedures, constraints of linear programming techniques, inflexibility of construction methods and inadequacy of dynamic programming approaches to provide acceptable solutions to realistic size layout design problems has led to an ever increasing interest in heuristic procedures. Comparative studies have shown that heuristic procedures can satisfy more desirable qualities in an ‘ideal algorithm’ to a greater extent than competitive techniques. Excessive computational effort, which has been one of the main criticisms levelled against heuristic approaches in the past, proves to be less of a problem in relation to layout design. By utilizing unique attributes associated with real-life problems and using small incisive modifications it is demonstrated how a heuristic procedure can be significantly improved.     

Transforming an MRP plan into a short-term schedule

A new approach for transforming MRP orders, planned periodically, e.g. on a weekly base, into a detailed sequence of jobs is presented. In this model for a single machine environment, the jobs are partitioned into families and a family specific set-up time is required at the start of each period and of each batch, where a batch is a maximal set of jobs in the same family, that are processed consecutively. An integer program is formulated for both the problem of minimizing the number of overloaded periods and the problem of minimizing the total overtime. These programs generate benchmark results for the heuristic approach. A heuristic model is developed that constructs a schedule in which overloaded periods are relieved and set-up time is saved. In this approach, the job sequence is constructed by repeatedly solving a knapsack problem. The weights used in this knapsack problem relate to the preferred priorities of the jobs not yet scheduled and determine the quality of the final sequence. The different features of the heuristic model are compared using a large set of test problems. The results show that the quality of the final sequence depends on an appropriate choice for the weights.     

On the Rank-Based Selection Strategy for the Group Interview Problem*

For the so-called group interview problem in which several groups of choice alternatives are presented sequentially to the decision maker, the optimal selection strategy is derived that minimizes the expected rank of the selected choice or purchased product. For the case in which the sequence of groups can be rearranged by the decision maker, a simple heuristic procedure is proposed for obtaining a near-optimal sequence of groups, and the performance of the heuristic procedure in a Monte Carlo simulation is accessed. According to the heuristic procedure, the consumer is advised to visit smaller stores first and then move to larger stores later to increase the likelihood of finding a better product. Finally, the optimal selection strategy and the heuristic procedure are compared with those proposed by Chun, Moskowitz, and Plante (1993) and the problem of locating a new store in an area where there are several competing stores is discussed. The optimal selection strategy and the heuristic procedure can be applied to many sequential decision problems such as the consumer search and purchase process.     

An Evaluation of Tour Scheduling Heuristics with Differences in Employee Productivity and Cost

This study focuses on the manpower tour scheduling problem using data from a lockbox system of a commercial bank. The lockbox system uses employees who differ in productivity, hourly cost, number of available working hours per week, and days-off constraints. These specific problem characteristics require a more general problem formulation and solution procedure for the manpower tour scheduling problem than addressed in previous research. Four heuristic methods for solving the problem (three developed here and a simple round-up procedure) are tested on a set of forty problems. The results of this study show the effort to develop sophisticated heuristic methods for this class of problems is well justified.     

Multi-time scale Markov decision process approach to strategic network growth of reverse supply chains

This paper addresses a complex set of decisions that surround the growth over time of reverse supply chain networks that collect used products for reuse, refurbishment, and/or recycling by processors. The collection network growth problem is decomposed into strategic, tactical and operational problems. This paper focuses on the strategic problem which is to determine how to allocate capital budget resource effectively to grow the network to meet long term collection targets and collection cost constraints. We model the strategic problem as a Markov decision process which can also be posed as multi-time scale Markov decision problem. The recruitment problem in a tactical level appears as a sub-problem for the strategic model. Using dynamic programming, linear programming and Q-Learning approaches, an heuristic is implemented to solve realistically sized problems. A numerical study demonstrates that the heuristic can obtain a good solution for the large-scale problem in reasonable time which is not possible when trying to obtain the optimal solution with the exact DP approach.     

Simulated annealing procedure for scheduling competing tasks in flexible manufacturing

This paper presents a simulated annealing SA procedure heuristic for the problem of scheduling N tasks on a machine equipped with an automatic tool changer to minimize the makespan time. The problem is first formulated as a symmetric travelling salesman problem TSP . A local search heuristic procedure is developed, then embedded into SA algorithm to enhance its performance. The implemented SA heuristic has the following features: an exponential acceptance function with non-monotonic cooling schedule, heuristic pre-processing, and a neighbourhood of changing the sequence of a small number of tasks and named the k-interchange procedure. The algorithm is compared with an exact solution method on a set of practical-sized problems. The proposed algorithm performed very well in terms of solution quality and computation time.     

Approaches to real world two-dimensional cutting problems

We consider a real world generalization of the 2-Dimensional Guillotine Cutting Stock Problem arising in the wooden board cutting industry. A set of rectangular items has to be cut from rectangular stock boards, available in multiple formats. In addition to the classical objective of trim loss minimization, the problem also asks for the maximization of the cutting equipment productivity, which can be obtained by cutting identical boards in parallel. We present several heuristic algorithms for the problem, explicitly considering the optimization of both objectives. The proposed methods, including fast heuristic algorithms, Integer Linear Programming models and a truncated Branch and Price algorithm, have increasing complexity and require increasing computational effort. Extensive computational experiments on a set of realistic instances from the industry show that high productivity of the cutting equipment can be obtained with a minimal increase in the total area of used boards. The experiments also show that the proposed algorithms perform extremely well when compared with four commercial software tools available for the solution of the problem.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

O(m2) ALGORITHMS FOR THE TWO AND THREE SUBLOT LOT STREAMING PROBLEM

Lot streaming is the process of splitting a job or lot into sublots to reduce its makespan on a sequence of machines. The goal in the lot streaming problem is to find the optimal size of each sublot that will minimize the makespan. The makespan is defined as the time the last sublot completes its processing on the last machine. If the sizes of these sublots are restricted to remain the same on all machines, the solution is called a consistent sublot solution. However, if the sizes of the sublots are allowed to vary, the solution is referred to as a nonconsistent or variable sublot solution. Also, if the machines must be in operation continuously from the first to the last sublot, the solution is a no idling solution. When setups are explicitly considered in the problem, there will be two cases. If setups on each machine require some portion of the first sublot be present by the machine, the problem is referred to as the attached setup time problem. If setups can be performed ahead of time before the first sublot reaches the particular machine, the corresponding problem is referred to as the detached setup problem. Finally, if the machines are allowed to be idle between the processing of sublots, the resultant solution is an intermittent idling solution. In this paper, the consistent sublot lot streaming problem with intermittent idling and no setups is discussed. The models developed also assume that the number of sublots are fixed and known. The m machine two sublot lot streaming problem is reviewed. An algorithm for the three sublot, m machine problem is derived using a network representation of the problem. The complexity of the algorithm is O (m²). Finally, using the insights from three sublot problem, a heuristic algorithm is provided for the m machine, n sublot problems. The results on the proposed heuristic are very encouraging; average percent deviation from optimal makespan is approximately at 0.76% on 155 randomly generated problems with different m and n values.     

面向安全硬约束的煤矿生产物流效率优化研究

在保证安全生产前提下实现效率最大化是煤炭生产企业亟需解决的现实问题。本文结合煤矿生产物流系统的复杂性特征,首先从人员素质、机械装备、环境改善、安全管理、应急救援等方面确定了煤矿生产物流的安全投入指标,运用响应曲面法分析了安全指标与安全水平间的作用关系,确定了煤矿生产物流安全硬约束条件;然后以效率最大化为目标函数、安全目标和资源投入为约束条件,构建了煤矿生产物流效率优化模型;最后通过实例验证了模型的有效性及适用性,为安全生产前提下实现资源优化配置,提高煤矿生产物流效率提供了科学依据。     

IMPLICIT OPTIMAL AND HEURISTIC LABOR STAFFING IN A MULTIOBJECTIVE,MULTILOCATION ENVIRONMENT*

This paper presents a tractable set of integer programming models for the days-off scheduling of a mix of full- and part-time employees working α to β days/week (cycle) in a multiple-objective, multiple-location environment. Previous models were formulated to specifically schedule part-time employees working either two or three days per week. These models were intractable because they required complete employee schedule information. The new models are deemed implicit optimal since they are required to supply only essential information. While the number of variables in previous models is an exponential increasing function of β-α, the size of three of the new models is independent of α and β. The first three models developed here (as in [18]) deal with the trade-offs between idle time, the number of employees required to work at multiple “locations,” and the size of the total labor pool. The inherent flexibility of the implicit modeling approach is illustrated by the presentation of various modifications of the basic models. These modifications permit the use of preference weights on the number of employee work days/week (cycle) or the minimization of payroll costs where differential pay rates exist. These latter models may also be formulated such that idle time is ignored, constrained or minimized. The execution time for the implicit models (on a CDC CYBER 730 computer with commercially available software) averaged well under five seconds on 1200 trial problems for the type of application considered in [18]. A solution was obtained in less than 46 seconds of CPU time for a trial problem which would have required over 1.4 million integer variables with previous models. The availability of optimal solutions was invaluable in the development of two heuristics designed to deal with the trade-offs of [16]. In an experimental analysis a previous heuristic produced results which averaged from 74 to 508 percent above optimum across six experimental conditions. The comparable new heuristic produced results which averaged from 3 to 8 percent above optimum for the same experimental conditions. The paper concludes by developing a framework to integrate the results of this research with the tour scheduling problem and by identifying several other areas for related research.     

OPTIMAL AND NEAR OPTIMAL CONTROL OF A TWO-PART-TYPE STOCHASTIC MANUFACTURING SYSTEM WITH DYNAMIC SETUPS

This paper deals with a manufacturing system consisting of a single machine subject to random failures and repairs. The machine can produce two types of parts. When the production is switched from one part type to the other, a random setup time is incurred at a constant cost rate. The objective is to track the demand, while keeping the work-in-process as close as possible to zero for both products. The problem is formulated as an optimal stochastic control problem. The optimal policy is obtained numerically by discretizing the continuous time continuous state opti-mality conditions using a Markov chain approximation technique. The discretized optimality conditions are shown to correspond to an infinite horizon, discrete time, discrete state dynamic programming problem. The optimal setup policy is shown to have two different structures depending on the parameters of the system. A heuristic policy is proposed to approximate the optimal setup policy. Simulation results show that the heuristic policy is a very good approximation for sufficiently reliable systems.     

基于煤矿透水事故应急响应时效性的水泵布局鲁棒优选问题研究

为了提高煤矿透水事故中矿工获救和恢复健康的可能性，本文基于应急响应时效性研究关键资源-水泵布局问题。已有应急资源布局问题的研究多从成本、时间、资源需求满足度等方面进行，煤矿透水事故应急响应时效性是综合考虑被困矿工获救时间以及被困过程中被困位置最低氧气含量和食物缺少量三方面要素的事故应对效果。首先，建立了基于煤矿透水事故发生、发展和应急响应机理的三方面要素计算方法；然后，在供氧和供食物所需资源布局给定的前提下，设计水泵布局的目标函数和约束条件，建立水泵布局鲁棒优选模型，通过机会时间窗概念的引入和分支定界算法的思想，给出水泵布局不可行方案的判别准则，并在此基础上进行优选算法的设计；最后，在实际发生的煤矿透水事故典型案例基础上，构造算例，检验水泵布局鲁棒优选模型的有效性。     

A New Framework for Manufacturing Planning and Control Systems*

This paper presents a new framework for manufacturing planning and control systems which we call iterative manufacturing planning in continuous time (IMPICT) that appears to have several advantages over the well-known material requirements planning (MRP) framework. IMPICT explicitly considers capacity constraints and total system cost (including tardiness) to determine order sizes, order release/due dates, and operation schedules in a deterministic, multi-level, finite horizon, dynamic demand environment. Continuous time scheduling variables allow setups to be carried over from one period to the next. Three new heuristics built on the IMPICT framework are presented and tested in a simulation-based, full-factorial experiment with a wide variety of problem environments. The benchmark for the experiment was materials requirements planning with operations sequencing (MRP/OS) implemented with best-case, fixed planned lead times. The experiment showed that all three heuristics were statistically better than MRP/OS. The total cost for the order merging (OM) heuristic was 25 percent better than the total cost for MRP/OS. Computational times for OM were substantially larger than for MRP/OS; however, the computational times in the experiment suggest that OM is still computationally viable for large-scale batch manufacturing environments found in industry. IMPICT is superior to standard MRP systems because it explicitly considers capacity constraints and total system costs when it creates a materials plan. IMPICT is superior to linear programming-based approaches to finite loading and scheduling found in the literature because it allows setups to be carried over from one period to another and because it is computationally viable for realistic-sized problems.