Finite-capacity scheduling-based planning for revenue-based capacity management

Finite-capacity scheduling can be argued to be a crucial component of revenue-based capacity management. In that case, one way to plan production is to reserve portions of capacity for incoming customer orders as they arrive, in real-time. In such a planning method, the way these work-orders are scheduled affects the useable capacity, due to fragmentation of the time-line. Assuming the work-orders are rejected if they cannot be inserted into the existing schedule, we develop heuristics to minimise the present-value of the cost of rejecting orders and inventory holding cost due to early completion. We perform simulation experiments to compare the performance of these heuristics in addition to some common heuristics used in practice.     

Multi-mode resource-constrained project scheduling problem with material ordering under bonus–penalty policies

This study emphasizes that project scheduling and material ordering (time and quantity of an order) must be considered simultaneously to minimize the total cost, as setting the material ordering decisions after the project scheduling phase leads to non-optimal solutions. Hence, this paper mathematically formulates the model for the multi-mode resource-constrained project scheduling with material ordering (MRCPSMO) problem. In order to be more realistic, bonus and penalty policies are included for the project. The objective function of the model consists of four elements: the material holding cost, the material ordering cost, the bonus paid by the client and the cost of delay in the project completion. Since MRCPSMO is NP-hard, the paper proposes three hybrid meta-heuristic algorithms called PSO-GA, GA-GA and SA-GA to obtain near-optimal solutions. In addition, the design of experiments and Taguchi method is used to tune the algorithms’ parameters. The proposed algorithms consist of two components: an outside search, in which the algorithm searches for the best schedule and mode assignment, and the inside search, which determines the time and quantity of orders of the nonrenewable resources. First, a comparison is made for each individual component with the exact or best solutions available in the literature. Then, a set of standard PROGEN test problems is solved by the proposed hybrid algorithms under fixed CPU time. The results reveal that the PSO-GA algorithm outperforms both GA-GA and SA-GA algorithms and provides good solutions in a reasonable time.     

A theoretical model for optimization of rolling schedule procedure parameters in ERP systems

The rolling schedule procedure has been an important part of the Enterprise Resource Planning (ERP) systems. The performance of production planning in an ERP system depends on the selection of the three parameters in rolling schedule procedure: frozen interval, replanning interval, and planning horizon (forecast window). This research investigated, in a theoretical approach, the combined impact of selections of those three parameters. The proven mathematical theorems provided guidance to reduction of instability (nervousness) and to seek the optimal balance between stability and responsiveness of ERP systems. Further the theorems are extended to incorporate the cost structure.     

Combining integer programming and the randomization method to schedule employees

We describe a method to find low cost shift schedules with a time-varying service level that is always above a specified minimum. Most previous approaches used a two-step procedure: (1) determine staffing requirements and (2) find a minimum cost schedule that provides the required staffing in every period. Approximations in the first step sometimes cause the two-step approach to find infeasible or suboptimal solutions. Our method iterates between a schedule evaluator and a schedule generator. The schedule evaluator calculates transient service levels using the randomization method and identifies infeasible intervals, where the service level is lower than desired. The schedule generator solves a series of integer programs to produce improved schedules, by adding constraints for every infeasible interval, in an attempt to eliminate infeasibility without eliminating the optimal solution. We present computational results for several test problems and discuss factors that make our approach more likely to outperform previous approaches.     

A hybrid scatter search heuristic for personalized crew rostering in the airline industry

The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.     

New and “Stronger” Job-Shop Neighbourhoods: A Focus on the Method of Nowicki and Smutnicki (1996)

Examination of the job-shop scheduling literature uncovers a striking trend. As methods for the deterministic job-shop problem have gradually improved over the years, they have come to rely on neighbourhoods for selecting moves that are more and more constrained. We document this phenomenon by focusing on the approach of Nowicki and Smutnicki (Management Science, 1996, 42(6), 797–813), noted for proposing and implementing the most restrictive neighbourhood in the literature. The Nowicki and Smutnicki (NS) method which exploits its neighbourhood by a tabu search strategy, is widely recognised as the most effective procedure for obtaining high quality solutions in a relatively short time. Accordingly, we analyse the contribution of the method's neighbourhood structure to its overall effectiveness. Our findings show, surprisingly, that the NS neighbourhood causes the method's choice of an initialisation procedure to have an important influence on the best solution the method is able to find. By contrast, the method's choice of a strategy to generate a critical path has a negligible influence. Empirical testing further discloses that over 99.7% of the moves chosen from this neighborhood (by the NS rules) are disimproving—regardless of the initial solution procedure or the critical path generation procedure employed. We discuss implications of these findings for developing new and more effective job-shop algorithms.     

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.     

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

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

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

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

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

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

A deteriorating inventory model with time-varying demand and shortage-dependent partial backlogging

Recently, Chu et al. [P. Chu, K.L. Yang, S.K. Liang, T. Niu, Note on inventory model with a mixture of back orders and lost sales, European Journal of Operational Research 159 (2004) 470–475] presented the necessary condition of the existence and uniqueness of the optimal solution of Padmanabhan and Vrat [G. Padmanabhan, P. Vrat, Inventory model with a mixture of back orders and lost sales, International Journal of Systems Science 21 (1990) 1721–1726]. However, they included neither the purchase cost nor the cost of lost sales into the total cost. In this paper, we complement the shortcoming of their model by adding not only the cost of lost sales but also the non-constant purchase cost, and then extend their model from a constant demand function to any log-concave demand function. We also provide a simple solution procedure to find the optimal replenishment schedule. Further, we use a couple of numerical examples to illustrate the results and conclude with suggestions for future research.     

一类自由作业供应链排序的研究

本文研究一类集成工件生产和发送的排序模型.在该模型中,供应链的上游首先将工件安排在自由作业机器上加工,然后把加工完毕的工件分批发送给下游.问题是寻找生产和发送相连的排序,使得生产排序费用和发送费用总和最少.这里,生产排序费用是以工件带权送到时间和表示;发送费用由固定费用和与运输路径有关的变化费用组成.在指出问题的NP困难性后,本文用动态规划算法构造了一致条件下的多项式时间近似算法,并分析算法的性能比.本文最后还讨论了该问题的其它情形.     

EOQ under Date-terms Supplier Credit: A Near-optimal Solution

This paper shows that under date-terms supplier credit, making explicit the separate effects of carrying cost, the financing and other marginal holding costs, does not invalidate Kingsman's original result that the optimal order quantity is given by an integer multiple of monthly demands, provided the capital investment component of the inventory holding costs is equal to or greater than 30% of the component due to the physical holding of inventory. The analysis is extended to the case when orders of less than a month's demand are optimal. Here it is shown that the order quantity should be an integer fraction of a month's demand, provided that the capital investment component of the inventory holding charge is equal to or greater than one quarter of the component due to the physical holding of inventory. It is argued that these conditions are likely to be satisfied for most if not all practical inventory situations. Combining these results with those of Carlson and Rousseau leads to a simple formula for the general optimal policy. The EOQ can still be expressed as a simple formula, so for practical situations generally there is no need to use the numerical search procedure these authors propose.     

Efficient Scheduling Rules in a Combined Make-to-Stock and Make-to-Order Manufacturing System

In this paper, we consider a mixed MTS/MTO policy to manage a single manufacturing facility producing two classes of end-products. A few end-products have high volume demands, whereas a fairly large number of end-products have low volume demands. In this situation, it is appealing to try to produce the high volume products according to an MTS policy and the low volume products according to an MTO policy. The purpose of this paper is to analyze and compare the impact of the choice of the scheduling policy on the overall performance of the system. We consider two policies: the classical FIFO policy and a priority policy (PR). The PR policy gives priority to production orders corresponding to low volume products over production orders corresponding to high volume products. Under some simple stochastic modeling assumptions, we develop analytical/numerical solutions to optimise each system. We then provide insights regarding this issue with the help of numerical examples. It appears that for some range of parameters, the PR rule can outperform the FIFO rule in the sense that, to achieve the same service level constraint, the corresponding cost under the PR rule is much lower. This situation is encountered when the low volume products can be managed with an MTO policy under the PR scheduling rule, while they have to be managed according to an MTS policy under the FIFO scheduling rule. We also derive some theoretical properties that support our empirical findings.     

带有可变库存费的变质性物品的部分延期供给的库存控制模型

传统的库存控制模型都视需求率为常数,在这篇文章中,放松了这个假定,研究了库存费的两种可能的变化:(i)库存费的变化率为存储时间的函数;(ii)库存费的变化率为库存量的函数.在模型中允许短缺发生且假定短缺部分延期供给,且在需求率线性依赖于库存水平的情形下,发展了两个变库存费的库存控制模型.     

Using mathematical programming heuristics in a multicriteria network flow context

In this paper, we propose a local search procedure to test the robustness of a specific ‘satisfying point’ neighbourhood. It consists of the following steps: (1) build an indifference area around the satisfying point in the criteria space by using thresholds (this takes into account the possible uncertainty, vagueness and/or inaccuracy of data); (2) find some points in the satisfying point neighbourhood and the corresponding solutions in the decision variables space; (3) test the quality of these solutions from the point of view of user preference. The indifference area is defined by adding constraints to the network model. This approach, which allows us to verify the adequacy of the model, has been applied to a set of multicriteria network flow problems. A heuristic method, based on Lagrangian duality and subgradient techniques, exploits the combinatorial structure of network flow problems in order to find certain feasible points.     

Analysis of third-party warehousing contracts with commitments

This paper considers multi-period warehousing contracts under random space demand. A typical contract is specified by a starting space commitment plus a certain number of times at which the commitment can be further modified. Three forms of contracts are analysed: (1) there is a restriction on the range of commitment changes and the schedule for the changes is preset by the warehouser; (2) the same as form (1) but there is no restriction on the range; (3) the same as form (2) but the schedule for the changes is chosen by the user. We explore properties and algorithms for the three problems from the user's perspective. Solutions of simple form are obtained for the first two models and an efficient dynamic programming (DP) procedure is proposed for the last. A numerical comparison of the total expected leasing costs suggests that under certain demand patterns, contract forms (2) and (3) could be cost effective.     

同类机下的供应链排序及转包策略

研究了一类工件排序与转包关联的模型,即工件既可以在制造商的同类机上加工,也可以较高费用转包给某个承包商加工.需要确定被转包的工件集,以及未转包工件的加工顺序,使得工件加工与转包费用在工件最大完工时间满足限制条件下达到极小.证明了该问题的NP困难性,用数学规划方法构造多项式时间近似算法,并分析算法性能比.     

Variable neighbourhood structures for cycle location problems

Variable neighbourhood search is a metaheuristic used mainly to tackle combinatorial optimization problems. Its performance depends on having a good variable neighbourhood structure: that is, a sequence of neighbourhoods that are ideally pairwise disjoint and contain feasible solutions further and further from a given feasible solution. This article defines a variable neighbourhood structure with these properties that is new for cycle location problems. It find bounds for the neighbourhood sizes and shows how to iterate over then when the cycle is a circuit. It tests the structure and iteration method using variable neighbourhood search on a range of median cycle problems and finds a neighbourhood size beyond which there is, on average, no benefit in applying local search. This neighbourhood size is found not to depend on problem size or bound on circuit length.     

Evaluation of three production planning procedures for the use of recipe flexibility

Process industries often obtain their raw materials from mining or agricultural industries. These raw materials usually have variations in quality, which often lead to variations in the recipes used for manufacturing a product. Another reason for varying the recipe is to minimize production costs by using the cheapest materials that still lead to a satisfactory quality in the product. A third reason for using recipe flexibility is that it may occur that at the time of production not all materials for the standard recipe are available. In earlier research we showed under what conditions the use of this type of recipe flexibility should be preferred to the use of high materials stock to avoid materials shortages. We also showed that the use of recipe flexibility to account for material shortages can be justified if the material replenishment leadtime is long, the demand uncertainty is high and the required service level is high. In this paper we assume that these conditions are satisfied and we investigate three different production planning procedures that make use of recipe flexibility to cope with the uncertainty in demand and supply. We assume that the customer order leadtime is much smaller than the material replenishment leadtime, and therefore demand uncertainty is high. The optimal procedure optimizes material use over a planning horizon equal to the material replenishment leadtime, taking into account the customers orders and knowledge of the distribution function of future demand. The deterministic procedure also optimizes the material use over the material replenishment leadtime, but it assumes a deterministic demand level for unknown orders. The simplest, myopic procedure optimizes material use over only the accepted customer orders. These three procedures are investigated via an experimental design of computer simulations of an elementary small scale model of the production planning situation. The results show that the optimal procedure outperforms the other two procedures. Furthermore, for a realistic cost structure in feed industry under certain circumstances the use of the optimal procedure may lead to a 4% increase in profit. However, this improvement must be weighted against the cost incurred by the operational use of this complex procedure. Based on these considerations and the numerical results in this paper, we may expect that for some situations in practice the use of the simplest myopic procedure, optimizing material use only over the available customer orders, will be justified from an overall cost point of view.