Scheduling aerial resource operations for the extinction of large-scale wildfires

The significant increase in large-scale wildfire events in recent decades, caused primarily by climate change, has resulted in a growing number of aerial resources being used in suppression efforts. Present-day management lacks efficient and scalable algorithms for complex aerial resource allocation and scheduling for the extinction of such fires, which is crucial to ensuring safety while maximizing the efficiency of operations. In this work, we present a Mixed Integer Linear Programming (MILP) optimization model tailored to large-scale wildfires for the daily scheduling of aerial operations. The main objective is to achieve a prioritized target water flow over all areas of operation and all time periods. Minimal target completion across individual areas and time periods and total water output are also maximized as secondary and ternary objectives, respectively. An efficient and scalable multi-start heuristic, combining a randomized greedy approach with simulated annealing employing large neighborhood search techniques, is proposed for larger instances. A diverse set of problem instances is generated with varying sizes and extinction strategies to test the approaches. Results indicate that the heuristic can achieve (near)-optimal solutions for smaller instances solvable by the MILP, and gives solutions approaching target water flows for larger problem sizes. The algorithm is parallelizable and has been shown to give promising results in a small number of iterations, making it applicable for both night-before planning and, more time-sensitive, early-morning scheduling.     

PLANNING PROCESS ARCHETYPES AND THEIR EFFECTIVENESS

Case studies of planning were profiled to identify how practitioners carry out a planning process. Five archetype processes emerged from the analyses which were named evaluative, historical model, off-the-shelf, search, and nova. These five processes were compared in terms of their adoption rate and perceived quality. The evaluative process was found to be the most successful, followed by the historical model and off-the-shelf processes. Nova and search processes had the least success. Contextual factors, such as time pressure and resources available, were included in the analyses to identify conditions of use for each process type. In situations where time pressure was high or the planning concerned services, the off-the-shelf model produced the best results; in situations where time pressure was low or the planning concerned internal operations, the historical model produced the best results. Most of the planning activity in organizations appears to be informal and heuristic, ignoring the methods described in the planning literature.     

Marginal analysis production planning

A forward looking with backward recourse production planning heuristic is developed using marginal analysis. In the search for a minimum cost solution, a set of rules derived by Kunreuther and Morton for determining planning horizons is employed. It is shown that the logic of the heuristic is similar to several dynamic lot-sizing models. The marginal analysis production planning (MAPP) heuristic is computationally more efficient than optimizing approaches and gives results that are generally less than 5% more expensive than the optimal solution. In addition, through the notion of level periods, the heuristic permits the user to easily investigate strategies where the work force size and daily production rate remain constant for a specified number of periods.     

Order Dispatching and Labor Assignment in Cellular Manufacturing Systems

Although order and labor dispatching in the job shop manufacturing setting have been investigated extensively over the last three decades, its representation of actual processes found in practice today is limited due to the move to cellular manufacturing (CM). Manufacturing cells have become an important approach to batch manufacturing in the last two decades, and their layout structure provides a dominant flow structure for the part routings. The flow shop nature of manufacturing cells adds a simplifying structure to the problem of planning worker assignments and order releases, which makes it more amenable to the use of optimization techniques. In this paper we exploit this characteristic and present two mathematical modeling approaches for making order dispatching and labor assignment/reassignment decisions in two different CM settings. The two formulations are evaluated in a dynamic simulation setting and compared to a heuristic procedure using tardiness as the primary performance measure. The formulations are superior to the heuristic approach and can be incorporated into detail scheduling systems that are being implemented by corporations employing enterprise resource planning (ERP) systems today.     

RESOURCE PLANNING FOR MULTIPLE PROJECTS *

This paper is concerned with the estimation of the resource requirements to service multiple projects that use many types of resources. It reports on a systematic procedure to determine the low cost levels of these resources, focusing on the two following characteristics: (1) the comparative cost of standard time to overtime in the utilization of these resources for the economical completion of the projects, and (2) the impact of highly expensive equipment in the determination of the economic levels of the manpower resources that combine with the equipment to form a crew. A numerical example is also presented to illustrate the method. Resource planning is of particular interest in the area of multiproject scheduling, since most of the commonly utilized heuristic solution approaches focus on the allocation of a limited set of available resources. In the corporate strategic planning functions, resource planning is particularly important for capital investment, training and development, and procurement scheduling.     

The Performance of MRP Purchase Lot-Size Procedures Under Actual Multiple Purchase Discount Conditions

Several heuristic procedures for purchase lot sizing in material requirements planning (MRP) systems were tested with actual data from manufacturing companies. Information provided by the companies for each purchased item included the estimated requirements and costs, the price discount structure from the vendor, and the actual company ordering policy. Simulation tests for each purchased item involved comparisons of several purchase lot-size procedures from the research literature along with the actual procedure used by the company providing the data. Results indicate that one of the heuristic lot-size procedures from the literature consistently outperformed the company policies as well as all other models tested. Another noteworthy result is that, in some cases, the actual company order policy was more cost-effective than some of the models from the research literature.     

An estimation of distribution algorithm for lot-streaming flow shop problems with setup times

Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses.     

Multi-objective simulation optimization using data envelopment analysis and genetic algorithm: Specific application to determining optimal resource levels in surgical services

Simulation is a powerful tool for modeling complex systems with intricate relationships between various entities and resources. Simulation optimization refers to methods that search the design space (i.e., the set of all feasible system configurations) to find a system configuration (also called a design point) that gives the best performance. Since simulation is often time consuming, sampling as few design points from the design space as possible is desired. However, in the case of multiple objectives, traditional simulation optimization methods are ineffective to uncover the efficient frontier. We propose a framework for multi-objective simulation optimization that combines the power of genetic algorithm (GA), which can effectively search very large design spaces, with data envelopment analysis (DEA) used to evaluate the simulation results and guide the search process. In our framework, we use a design point's relative efficiency score from DEA as its fitness value in the selection operation of GA. We apply our algorithm to determine optimal resource levels in surgical services. Our numerical experiments show that our algorithm effectively furthers the frontier and identifies efficient design points.     

Hybrid heuristic for design of cellular manufacturing systems

Cell design in Cellular Manufacturing Systems (CMS) assumes significance due to the incremental nature of implementation. In this study a hybrid heuristic has been developed considering incremental aspect of implementation. The heuristic identifies complete cells (if they exist), otherwise forms a CMS with combination of regular cells and a remainder cell which caters to the needs of exceptional parts/operations. The heuristic has been tested with the standard problems in the literature. It is found that the proposed heuristic produces superior solutions in 62.22% cases and the same solutions in the remaining cases. Further, statistical testing has been conducted and found that the performance of the proposed heuristic is significantly better than the existing methods.     

求解带时间窗的装-卸载问题的概率式禁忌搜索算法

本文介绍一个求解有时间窗的装载—卸载问题的概率式禁忌搜索算法。论文首先回顾了求解VRP、PDP问题的主要方法,介绍了搜索算法的基本概念,给出了基于概率式禁忌搜索的详细算法。初步实验表明新算法优于传统禁忌搜索算法。     

Simulation optimization through direct search for multi-objective manufacturing systems

Simulation modelling has been one of the most widely used techniques for analysing complex manufacturing systems. In this paper, we propose a direct search algorithm expanded from the Hooke-Jecves pattern search to systematically and efficiently locate satisfactory solutions for multi-objective simulation models. The user-specified goals can be precise and/or fuzzy. Heuristic rules stemming from the simulation result of resource statistics are incorporated into the Hooke-Jeeves pattern search. The proposed heuristic rules make the search procedure effective regardless of different initial points and various bounded ranges of decision variables. Experimental results show that the proposed approach is suitable for analysing complex manufacturing systems, in which multiple objectives and multiple decision variables are encountered.     

Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints

This research deals with scheduling jobs on unrelated parallel machines with auxiliary equipment constraints. Each job has a due date and requires a single operation. A setup for dies is incurred if there is a switch from processing one type of job to another type. For a die type, the number of dies is limited. Due to the attributes of the machines and the fitness of dies to each, the processing time for a job depends on the machine on which the job is processed, each job being restricted to processing on certain machines. In this paper, an effective heuristic based on threshold-accepting methods, tabu lists, and improvement procedures is proposed to minimize total tardiness. An extensive experiment is conducted to evaluate the computational characteristics of the proposed heuristic. Computational experiences demonstrate that the proposed heuristic is capable of obtaining optimal solutions for small-sized problems, and significantly outperforms an ATCS procedure and a simulated annealing method for problems in larger sizes.     

On the number of local minima for the multidimensional assignment problem

The Multidimensional Assignment Problem (MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association, target tracking, and resource planning. As many solution approaches to this problem rely, at least partly, on local neighborhood search algorithms, the number of local minima affects solution difficulty for these algorithms. This paper investigates the expected number of local minima in randomly generated instances of the MAP. Lower and upper bounds are developed for the expected number of local minima, E[M], in an MAP with iid standard normal coefficients. In a special case of the MAP, a closed-form expression for E[M] is obtained when costs are iid continuous random variables. These results imply that the expected number of local minima is exponential in the number of dimensions of the MAP. Our numerical experiments indicate that larger numbers of local minima have a statistically significant negative effect on the quality of solutions produced by several heuristic algorithms that involve local neighborhood search.Partially supported by the NSF grant DMI-0457473.     

Improving human resources for health planning in developing economies

There is a universal consensus that human resources represent the heart and soul of effective health systems everywhere. However, despite this consensus, human resource planning in low income countries remains a neglected, often poorly implemented and ineffective component of health-system development. The planning exercises that do take place are often inefficient, use inappropriate planning models or fail to adequately prioritize human resource investment decisions. This article briefly discusses possible reasons why this failure occurs and describes four key steps that can help health system planners more effectively prioritize and link human resource for health investment decisions to health system strategy and programmatic initiatives. Implications for human resource development practice and national human resource development are discussed.     

中小呼叫中心月度排班优化模型与算法

国内中小呼叫中心制定坐席人员月度排班表时,通常考虑劳动法规合同约束和体现企业自身用工管理诉求。构建坐席人员月度排班优化问题的二次整数规划模型。鉴于问题模型难解性,依据调研企业需求和模型逻辑结构分析,把问题分解成三个子问题。通过构建整数规划模型和提出启发式算法来求出子问题解,从而生成排班问题优化解。问题实例计算表明,模型算法能够有效控制人力成本和兼顾员工同班次管理目标。与周排班方法比较,该方法能够充分体现月度排班人力灵活性来实现人力优化配置。     

A modified hierarchical production planning system integrated with MRP: A case study

In this paper, a hierarchical planning system is proposed which integrates aggregate capacity planning with MRP. This system is to be implemented in a metal box manufacturing company which multi-user MRP system covering manufacturing activities as well as procurement sales order processing and accounting systems. The hierarchical planning system includes a medium-range aggregate planning model adapted to the firm's requirements and strategies. The model consists of a mathematical formulation which covers labour capacity has already installed a constraints and includes certain cost estimations in the objective function. The planning horizon of the medium range planning is taken as twelve months in order to cover sales seasonality. The aggregate production quantities resulting from the optimized medium-range planning model are disaggregated according to procedures already found in the literature. Furthermore, the theoretical infeasibilities pertaining to the disaggregation procedures are also resolved in an heuristic manner. Using the latter modified disaggregation procedure, a feasible disaggregated plan is generated for the whole planning horizon. The proposed plan is compared with the current production policy of the firm and it is observed that the proposed plan leads to backorder reduction.     

基于柔性资源约束的前摄性项目调度优化研究

不确定环境中，项目进度计划鲁棒性的高低直接影响项目能否顺利实施。本文研究了具有随机活动工期的柔性资源约束下的前摄性项目调度优化问题，目标是在柔性资源和项目工期的约束下，借助对活动开始时间合理的进行安排进而得到拥有最大鲁棒性的进度计划。首先对研究问题进行界定；随后构建优化模型，并根据问题NP-hard属性和模型特点设计了双层嵌套禁忌搜索启发式算法，通过内外两层交互搜索寻找满意解；最后通过一个实际案例对本文研究进行说明，并分析关键参数对进度计划鲁棒性的影响，得到如下结论：相对于资源无柔性情况下的项目进度计划而言，资源具备柔性后得到的项目进度计划的鲁棒性更高，具有更强的抗干扰能力，能够保证项目稳定执行；同时，项目进度计划鲁棒性分别随着项目工期的延长、资源可用量的增加或资源柔性的提高而上升。     

Energy conservation through resource-aware movement in heterogeneous mobile ad hoc networks

Energy conservation in mobile ad hoc networks is of paramount importance because most mobile nodes usually have very limited energy supply. Previous research on this issue focused on the design at the network or MAC or physical layer. In this paper, we study this problem from the new perspective of node mobility, i.e., analyzing the impact of node movement on energy conservation. In particular, armed with the inherent resource heterogeneity in mobile ad hoc networks, we propose a novel resource-aware movement strategy to make better use of some powerful nodes to achieve energy conservation. We also formulate the resource-aware movement as a NP-complete distance-constrained least-cost (DCLC) routing problem and propose an efficient heuristic solution. Extensive simulations have been used to demonstrate the effectiveness of the proposed schemes.     

An integrated hybrid approach to the examination timetabling problem

This paper is derived from an interest in the development of automated approaches to tackle examination timetabling problems effectively. We propose a hybrid approach that incorporates effective heuristic operators within the great deluge algorithm. The latter was chosen because of consistently good performances being reported within the examination timetabling research domain. The additional heuristic procedures further enhance the overall effectiveness of this integrated hybrid approach. These procedures are drawn from methodologies that have appeared in the literature under term the “electromagnetic-like mechanism”. The aim is to move sample points towards a high quality solution while avoiding local optima by utilising a calculated force value. This value, which is calculated dynamically, is treated as a decay rate in determining the level within the great deluge algorithm. To evaluate the proposed algorithm, we carry out experimental work on two types of examination timetabling datasets. All the related results and analysis obtained illustrate that this hybrid approach is effective when compared with existing approaches in the literature.     

Market Good Flexibility in Capacity Auctions

We consider the allocation of limited production capacity among several competing agents through auctions. Our focus is on the contribution of flexibility in market good design to effective capacity allocation. The application studied is a capacity allocation problem involving several agents, each with a job, and a facility owner. Each agent generates revenue by purchasing capacity and scheduling its job at the facility. Ascending auctions with various market good designs are compared. We introduce a new market good that provides greater flexibility than those previously considered in the literature. We allow ask prices to depend both on agents’ utility functions and on the number of bids at the previous round of the auction, in order to model and resolve resource conflicts. We develop both optimal and heuristic solution procedures for the winner determination problem. Our computational study shows that flexibility in market good design typically increases system value within auctions. A further increase is achieved if each agent is allowed to bid for multiple market goods at each round. On average, the multiple flexible market goods auction provides over 95% of the system value found by centralized planning.