A cutting plane method for solving harvest scheduling models with area restrictions

We describe a cutting plane algorithm for an integer programming problem that arises in forest harvest scheduling. Spatial harvest scheduling models optimize the binary decisions of cutting or not cutting forest management units in different time period subject to logistical, economic and environmental restrictions. One of the most common constraints requires that the contiguous size of harvest openings (i.e., clear-cuts) cannot exceed an area threshold in any given time period or over a set of periods called green-up. These so-called adjacency or green-up constraints make the harvest scheduling problem combinatorial in nature and very hard to solve. Our proposed cutting plane algorithm starts with a model without area restrictions and adds constraints only if a violation occurs during optimization. Since violations are less likely if the threshold area is large, the number of constraints is kept to a minimum. The utility of the approach is illustrated by an application, where the landowner needs to assess the cost of forest certification that involves clear-cut size restrictions stricter than what is required by law. We run empirical tests and find that the new method performs best when existing models fail: when the number of units is high or the allowable clear-cut size is large relative to average unit size. Since this scenario is the norm rather than the exception in forestry, we suggest that timber industries would greatly benefit from the method. In conclusion, we describe a series of potential applications beyond forestry.     

MODELING HARVEST SCHEDULING IN MULTIFUNCTIONAL PLANNING OF FORESTS FOR LONGTERM WATER YIELD OPTIMIZATION

In this study, wood production and hydrologic functions of forests were accommodated within a planning procedure for separate working circles (areas dedicated to certain forest functions) that were delineated according to an Ecosystem‐Based Functional Planning approach. Mixed integer goal programming was used as the optimization technique. The timing and scheduling of a maintenance cutting (partial harvest) was the decision variable in the modeling effort, and an original formulation was developed as a multiobjective planning procedure. Four sample planning strategies were developed and model outputs were evaluated according to these strategies. Spatial characteristics of stands were considered, and used to prohibit the regeneration of adjacent stands during the same time period. Because of the positive relationship between qualified water production and standing timber volume in the forest, the model attempts to maximize qualified water production levels by increasing standing volume stocks in the forest through the delay of regeneration activities.     

Patient mix optimization in tactical cardiothoracic surgery planning: a case study

Cardiothoracic surgery planning involves different resourcessuch as operating theatre (OT) time, medium care beds, intensivecare beds and nursing staff. Within cardiothoracic surgery differentcategories of patients can be distinguished with respect totheir requirements of resources. The mix of patients is, therefore,an important aspect of decision making for the hospital to managethe use of these resources. A master OT schedule is used atthe tactical level of planning for deriving the weekly OT plan.It defines for each day of a week the number of OT hours availableand the number of patients operated from each patient category.We develop a model for this tactical level planning problem,the core of which is a mixed integer linear program. The modelis used to evaluate scenarios for surgery planning at tacticalas well as strategic levels, demonstrating the potential ofinteger programming for providing recommendations for change.     

多种产品生产系统的生产计划问题

研究一个为满足确定性需求而进行产品生产的系统.系统中有一台用于生产的机器, 生产$n$种不同的产品.每一种产品都有确定的日需求. 我们将能够满足所有产品需求的生产计划称之为可行计划.主要想通过数学模型, 来建立一套判定可行计划存在性的理论. 在确保存在可行计划的前提下, 设计了一种找寻出具体可行计划的计算方法. 并且, 进一步可以通过0-1规划来优化系统的效率,称之为最小化产能占用率.     

A new approach to tactical and strategic planning in production-distribution networks

Today the most important concern of the managers is to make their firms viable in the competitive trade world. Managers are looking for effective tools for decision making in the complex business world. This paper presents a new mathematical model for strategic and tactical planning in a multiple-echelon, multiple-commodity production-distribution network. In the proposed model, different time resolutions are considered for strategic and tactical decisions. Also expansion of the network is planned based on cumulative net incomes. To illustrate applications of the proposed model as well as its performance based on the solution times, some hypothetical numerical examples have been generated and solved by CPLEX. Results show that in small and medium scale of instances, high quality solutions can be obtained using this solver, but for larger instances, some heuristics has to be designed to reduce solution time.     

A dynamic production planning and scheduling algorithm for two products processed on one line

This paper presents a dynamic production planning and scheduling algorithm for two products processed on one line over a fixed time horizon. Production rates are assumed fixed, and restrictions are placed or inventory levels and production run lengths. The resulting problem is a nonlinear binary program, which is solved using an implicit enumeration strategy. The algorithm focuses on the run changeover period while developing tighter bounds on the length of the upcoming run to improve computational efficiency. About 99% pf 297 randomly generated problems with varying demand patterns are solved in less than 15 seconds of CPU time on a CDC Cyber 172 Computer. A mixed integer programming formulation of the generalized multi-product case under no-backlogging of demand is also given.     

Fix and Relax Heuristic for a Stochastic Lot-Sizing Problem

This paper addresses a particular stochastic lot-sizing and scheduling problem. The evolution of the uncertain parameters is modelled by means of a scenario tree and the resulting model is a multistage stochastic mixed-integer program. We develop a heuristic approach that exploits the specific structure of the problem. The computational experiments carried out on a large set of instances have shown that the approach provides good quality solutions in a reasonable amount of time.     

Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: worst-case analysis

The paper deals with the problem of scheduling jobs on a single machine, in which each job has a release date, a delivery time and a controllable processing time, having its own associated linearly varying cost. An approximation algorithm for minimizing the overall schedule cost is provided which has the performance guarantee of , where is the worst-case performance bound of a procedure used in the proposed algorithm for solving the pure sequencing problem. The best approximation procedure known has .     

呼叫中心坐席人员排班问题优化模型与算法研究

国内呼叫企业在保证每个坐席人员周内当值相同班次情况下,通过灵活安排周内当班日期与班次来制定排班方案。针对该实际排班场景,构建问题整数规划模型。通过对问题数据特征及优化性质分析,以及对班次人力有效满足区段电话服务需求的量化指标表征,分别提出两个构造性启发式算法。使用企业实例数据对模型算法进行计算实验。实验结果显示,整数规划模型适合于求解小规模排班问题最优解,而启发式算法能够以小计算成本获得大规模排班问题优化解。最后讨论保证员工上班规律性的同班次用工制度对企业人力成本控制的影响。     

A note on “A mixed integer programming model for advanced planning and scheduling (APS)”

In a recent paper, Chen and Ji [Chen, K., Ji, P., 2007. A mixed integer programming model for advanced planning and scheduling (APS). European Journal of Operational Research 181, 515–522] develop a mixed integer programming model for advanced planning and scheduling problem that considers capacity constraints and precedence relations between the operations. The orders require processing of several operations on eligible machines. The model presented in the above paper works for the case where each operation can be processed on only one machine. However, machine eligibility means that only a subset of machines are capable of processing a job and this subset may include more than one machine. We provide a general model for advanced planning and scheduling problems with machine eligibility. Our model can be used for problems where there are alternative machines that an operation can be assigned to.     

Dual-based optimization of cyclic four-day workweek scheduling

Email: hesham{at}ccse.kfupm.edu.sa An optimization method is presented for the cyclic labour days-offscheduling problem, in which workers are given three consecutivedays off per week. This method does not include linear or integerprogramming, and it does not assume that the costs of differentdays-off work patterns are equal. The dual problem is firstsolved to determine the minimum workforce size. Then, the dualsolution is used to determine days-off assignments that minimizethe total labour cost. By requiring only simple manual calculations,the new method eliminates the need for linear or integer programmingsoftware.     

A mixed integer programming model for advanced planning and scheduling (APS)

This paper presents a mixed integer programming (MIP) model which succeeds in a system integration of the production planning and shop floor scheduling problems. The proposed advanced planning and scheduling (APS) model explicitly considers capacity constraints, operation sequences, lead times and due dates in a multi-order environment. The objective of the model is to seek the minimum cost of both production idle time and tardiness or earliness penalty of an order. The output of the model is operation schedules with order starting time and finish time. Numerical result shows that the suggested APS model can favorably produce optimal schedules.     

多车型车辆调度问题的优化模型

基于第十一届"华为杯"全国研究生数学建模竞赛E题第五问,针对一类多车型多目的地的整车物流运输调度问题,先直接计算完成总任务所需的车辆数来阐明该题的最优解的下界限为113辆,再对原始数据进行预处理,基于对乘用车的分类与排样算法,筛选出每种轿运车的M种装载方案代表,再对目的地位置及结合各目的地的任务需求,确定出3条不绕行路线,根据启发式调整优化算法,并以轿运车使用量最少及总行驶里程最短为优化目标,建立了多目标整数规划模型进行求解,最优可行解为114辆,其中1-1型91辆,1-2型18辆,2-2型5辆.     

On dual solutions of the linear assignment problem

For the linear assignment problem we describe how to obtain different dual solutions. It turns out that a shortest path algorithm can be used to compute such solutions with several interesting properties that enable to do better post-optimality analysis.Two examples illustrate how different dual solutions can be used in the context of the traveling salesman problem.     

Four-Day Workweek Scheduling with Two or Three Consecutive Days Off

A four-day workweek days-off scheduling problem is considered. Out of the three days off per week for each employee, either two or three days must be consecutive. An optimization algorithm is presented which starts by utilizing the problem's special structure to determine the minimum workforce size. Subsequently, workers are assigned to different days-off work patterns in order to minimize either the total number or the total cost of the workforce. Different procedures must be followed in assigning days-off patterns, depending on the characteristics of labor demands. In some cases, optimum days-off assignments are determined without requiring mathematical programming. In other cases, a workforce size constraint is added to the integer programming model, greatly improving computational performance.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

A NEW LOOK AT WHOLE-FOREST MODELING

The harvest scheduling problem customarily known as Model II can be reformulated using a dynamic equation, and solved in two ways using linear programming. Viewing the problem in this way offers many insights and is convenient for deriving extensions to the basic problem. Extensions include the risk of catastrophic loss through fire, the problem of a changing land base, and the imposition of area constraints on the forest. An economic interpretation of certain dual variables in one of the solution methods is given. The mathematical equivalence of the standard Model II linear program, and the dynamic equation formulation, is demonstrated and the numerical efficiency of the various methods is examined for simple problems.     

IRREVERSIBLE INVESTMENT AND OPTIMAL FOREST EXPLOITATION

A forest harvest scheduling model which includes as activities the level of investment in harvest capacity and the accumulated harvest capacity in each period, is presented. The inclusion of these activities, in addition to the harvest activities, allows for the removal of harvest-flow constraints found in more typical Model II formulations of the harvest scheduling problem. The optimal harvest and investment policy can be determined by linear programming or quadratic programming methods, depending on whether prices are constant or supply-dependent. The new model better reflects economic reality than existing models, and provides a method for determining the optimal economic development of a forest industry, and the optimal draw-down of old growth forest. Numerical examples are given.     

考虑生产计划的多周期切割问题优化研究

切割生产广泛存在于工业企业,是原材料加工的重要环节。已有文献主要关注单周期切割问题,但是切割计划也是生产计划的一部分,切割计划和生产计划应该协调优化,达到全局最优。本文研究考虑生产计划的多周期切割问题,目标是最小化运营成本,包括准备成本、切割成本、库存成本以及母材消耗成本。首先建立混合整数规划模型;提出动态规划启发式算法;最后对算例在多种情境下测试,分析成本因子变化对最优结果的影响。算法结果与CPLEX最优结果比较,平均误差为1.85%,表明算法是有效的。     

满足路径约束的最优路算法

满足路径约束的最优路问题已被证明是NP-hard问题。本针对源点到宿点满足两个QoS(服务质量)度量的路由问题，给出一种保证时延的最小费用路由启发式算法。这个算法的优点是计算较简单、占用内存小、时间短。算法的复杂度是多项式的，表明算法是有效的。