A heuristic for scheduling problems,especially for scheduling farm operations

Scheduling problems in agriculture are often solved using techniques such as linear programming (the multi-period formulation) and dynamic programming. But it is difficult to obtain an optimal schedule with these techniques for any but the smallest problems, because the model is unwieldly and much time is needed to solve the problem. Therefore, a new algorithm, a heuristic, has been developed to handle scheduling problems in agriculture. It is based on a search technique (i.e. hill-climbing) supported by a strong heuristic evaluation function. In this paper the heuristic performance is compared with dynamic programming. The heuristic offers near-optimal solutions and is much faster than the dynamic programming model. When tested against dynamic programming the difference in results was about 3%. This heuristic could probably also be applied in an industrial environment (e.g. agribusiness or road construction).     

Real time disruption management for a two-stage batch production–inventory system with reliability considerations

In this research, a two-stage batch production–inventory system is introduced. In this system, the production may be disrupted, for a given period of time, either at one or both stages. In this paper, firstly, a mathematical model has been developed to suggest a recovery plan for a single occurrence of disruption at either stage. Secondly, multiple disruptions have been considered, for which a new disruption may or may not affect the recovery plan of earlier disruptions. We propose a new approach that deals with a series of disruptions over a period of time, which can be implemented for disruption recovery on a real time basis. In this approach, the model formulated for single disruption has been integrated to generate initial solutions for individual disruptions and the solutions have been revised for multiple dependent disruptions with changed parameters. With the proposed approach, an optimal recovery plan can be obtained in real time, whenever the production system experiences either a sudden disruption or a series of disruptions, at different points in time. Some numerical examples and a real-world case study are presented to explain the benefits of our proposed approach.     

The cutting stock problem for large sections in the iron and steel industries

The characteristics of a cutting stock problem for large sections in the iron and steel industries are as follows:(1) There is a variety of criterions such as maximizing yield and increasing effeciency of production lines. (2) A cutting stock problem is accompanied by an optimal stock selection problem. A two-phase algorithm is developed, using an heuristic method. This algorithm gives nearly optimal solutions in real time. It is applied to both batch-solving and on-line solving of one-dimensional cutting of large section. The new algorithm has played an important role in a large-section production system to increase the yield by approximately 2.5%.     

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。     

军事物流系统中定位-运输路线安排模型及算法

考虑到战时物资需求的紧迫性和保障资源的有限性,从决策者的角度出发,以军事物流系统总体供应时间最短为目标,构建了两级军事配送网络的定位-运输路线安排模型,并给出一种启发式算法.算法分为两个阶段,首先利用蚁群算法和线性规划的方法解决运输路线安排问题,然后运用贪婪搜索算法解决军事物流配送中心选址问题.最终,将两种算法结合起来进行逐步搜索,从而得到模型的解,并运用实例说明了算法的有效性和可行性.     

Scheduling preemptive open shops to minimize total tardiness

This article considers the problem of scheduling preemptive open shops to minimize total tardiness. The problem is known to be NP-hard. An efficient constructive heuristic is developed for solving large-sized problems. A branch-and-bound algorithm that incorporates a lower bound scheme based on the solution of an assignment problem as well as various dominance rules are presented for solving medium-sized problems. Computational results for the 2-machine case are reported. The branch-and-bound algorithm can handle problems of up to 30 jobs in size within a reasonable amount of time. The solution obtained by the heuristic has an average deviation of less than 2% from the optimal value, while the initial lower bound has an average deviation of less than 11% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 65% of the problems actually solved.     

A heuristic approach based on shortest path problems for integrated flight,aircraft, and passenger rescheduling under disruptions

In this paper, we present a heuristic method to solve an airline disruption management problem arising from the ROADEF 2009 challenge. Disruptions perturb an initial flight plan such that some passengers cannot start or conclude their planned trip. The developed algorithm considers passengers and aircraft with the same priority by reassigning passengers and by creating a limited number of flights. The aim is to minimize the cost induced for the airline by the recovery from the disruptions. The algorithm is tested on real-life-based data, as well as on large-scale instances and ranks among the best methods proposed to the challenge in terms of quality, while being efficient in terms of computation time.     

A multi-objective hot-rolling scheduling problem in the compact strip production

This paper addresses a hot-rolling scheduling problem from compact strip production processes. At first, a mathematical model that consists of two coupled sub-problems is presented. The first sub-problem is the sheet-strip assignment problem that is about how to assign sheet-strips to rolling-turns with the objective of minimizing virtual sheet-strips. The second is the sheet-strip sequencing problem that is about how to sort the sheet-strips in each rolling-turn with the objective of minimizing the maximal changes in thickness between adjacent sheet-strips and the change times of the thickness so as to ensure high quality sheet-strips to be produced. And then, an improved hot-rolling scheduling heuristic is proposed to solve the sheet-strip assignment problem. A multi-objective evolutionary algorithm is developed to find the Pareto optimal or near-optimal solutions for the sheet-strip sequencing problem. Besides, the problem-specific knowledge is explored. The key operators including crossover operator, mutation operator and repair operator are designed for the multi-objective evolutionary algorithm. At last, extensive experiments based on real-world instances from a compact strip production process are carried out. The results demonstrate the effectiveness of the proposed algorithms for solving the hot-rolling scheduling problem under consideration.     

Simultaneous evacuation and entrance planning in complex building based on dynamic network flows

This paper presents mathematical models and a heuristic algorithm that address a simultaneous evacuation and entrance planning. For the simultaneous evacuation and entrance planning, four types of mathematical models based on the discrete time dynamic network flow model are developed to provide the optimal routes for evacuees and responders within a critical timeframe. The optimal routes obtained by the mathematical models can minimize the densification of evacuees and responders into specific areas. However, the mathematical model has a weakness in terms of long computation time for the large-size problem. To overcome the limitation, we developed a heuristic algorithm. We also analyzed the characteristics of each model and the heuristic algorithm by conducting case studies. This study pioneers area related to evacuation planning by developing and analyzing four types of mathematical models and a heuristic algorithm which take into account simultaneous evacuation and entrance planning.     

Order splitting with multiple capacitated suppliers

This paper studies an integrated decision making model for a supply chain system where a manufacturer faces a price-sensitive demand and multiple capacitated suppliers, two issues that are often considered separately in the literature. The goal is to maximize total profit by determining an optimal selling price and at the same time acquiring enough supplying capacity. The problem is proved to be NP-hard in the ordinary sense, a heuristic algorithm and an optimal dynamic programming algorithm are developed. Computational experiments are conducted to study the efficiency and effectiveness of the algorithms. Some managerial insights are observed.     

A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem

Owing to its theoretical as well as practical significance, the facility layout problem with unequal-area departments has been studied for several decades, with a wide range of heuristic and a few exact solution procedures developed by numerous researchers. In one of the exact procedures, the facility layout problem is formulated as a mixed-integer programming (MIP) model in which binary (0/1) variables are used to prevent departments from overlapping with one another. Obtaining an optimal solution to the MIP model is difficult, and currently only problems with a limited number of departments can be solved to optimality. Motivated by this situation, we developed a heuristic procedure which uses a “graph pair” to determine and manipulate the relative location of the departments in the layout. The graph-pair representation technique essentially eliminates the binary variables in the MIP model, which allows the heuristic to solve a large number of linear programming models to construct and improve the layout in a comparatively short period of time. The search procedure to improve the layout is driven by a simulated annealing algorithm. The effectiveness of the proposed graph-pair heuristic is demonstrated by comparing the results with those reported in recent papers. Possible extensions to the graph-pair representation technique are discussed at the end of the paper.     

The optimal control of just-in-time-based production and distribution systems and performance comparisons with optimized pull systems

In just-in-time (JIT) production systems, there is both input stock in the form of parts and output stock in the form of product at each stage. These activities are controlled by production-ordering and withdrawal kanbans. This paper discusses a discrete-time optimal control problem in a multistage JIT-based production and distribution system with stochastic demand and capacity, developed to minimize the expected total cost per unit of time. The problem can be formulated as an undiscounted Markov decision process (UMDP); however, the curse of dimensionality makes it very difficult to find an exact solution. The author proposes a new neuro-dynamic programming (NDP) algorithm, the simulation-based modified policy iteration method (SBMPIM), to solve the optimal control problem. The existing NDP algorithms and SBMPIM are numerically compared with a traditional UMDP algorithm for a single-stage JIT production system. It is shown that all NDP algorithms except the SBMPIM fail to converge to an optimal control.Additionally, a new algorithm for finding the optimal parameters of pull systems is proposed. Numerical comparisons between near-optimal controls computed using the SBMPIM and optimized pull systems are conducted for three-stage JIT-based production and distribution systems. UMDPs with 42 million states are solved using the SBMPIM. The pull systems discussed are the kanban, base stock, CONWIP, hybrid and extended kanban.     

B2C电子商务仓库拣货路径优化策略应用研究

当前国内B2C电子商务仓库多为人至物的拣货模式,拣货作业成为其核心作业之一,占据仓库大量时间成本和资金成本,拣货路径优化成为企业亟需解决的问题。本文基于TSP对拣货路径进行建模,利用蚁群算法、模拟退火算法和禁忌搜索对该NP-hard问题进行求解,并同当前企业普遍采用的S型启发式策略进行对比,拣货时间节约13.35%。进一步得出当拣货品数量较少时应采用模拟退火算法求解,而当拣货品数量较大时采用蚁群算法仅进行一次迭代,则可以实现短时间得到相对较优的解。所得结果已应用于某大型电子商务企业,效果明显。     

A heuristic algorithm for a production planning problem in an assembly system

This paper focuses on a production planning problem in an assembly system operating on a make-to-order basis. Due dates are considered as constraints in the problem, that is, tardiness is not allowed. The objective of the problem is to minimise holding costs for final product inventory as well as work-in-process inventory. A non-linear mathematical model is presented and a heuristic algorithm is developed using a solution property and a network model for defining solutions of the problem. A series of computational tests were done to compare the algorithm with a commercial planning/scheduling software and backward finite-loading methods that employ various priority rules. The results showed that the suggested algorithm outperformed the others.     

一种改进的蚁群算法及其在TSP中的应用

蚁群算法是一种求解复杂组合优化问题的新的拟生态算法,也是一种基于种群的启发式仿生进化算法,属于随机搜索算法的一种,并用于较好地解决TSP问题.然而此算法也有它自己的缺陷,如易于陷入局部优化、搜索时间长等.通过对基本蚁群算法的介绍及相关因素的分析,提出了一种改进的蚁群算法,用于解决TSPLAB问题的10个问题,并与参考文献中的F-W、NCSOM、ASOM算法进行比较,计算机仿真结果表明了改进算法的有效性.如利用改进的蚁群算法解决lin105问题,其最优解为14382.995933(已知最优解为14379),相对误差是0.0209%,计算出的最小值几乎接近于已知最优解.     

Optimal Low-Thrust Orbital Maneuvers via Indirect Swarming Method

In the last decades, heuristic techniques have become established as suitable approaches for solving optimal control problems. Unlike deterministic methods, they do not suffer from locality of the results and do not require any starting guess to yield an optimal solution. The main disadvantages of heuristic algorithms are the lack of any convergence proof and the capability of yielding only a near optimal solution, if a particular representation for control variables is adopted. This paper describes the indirect swarming method, based on the joint use of the analytical necessary conditions for optimality, together with a simple heuristic technique, namely the particle swarm algorithm. This methodology circumvents the previously mentioned disadvantages of using heuristic approaches, while retaining their advantageous feature of not requiring any starting guess to generate an optimal solution. The particle swarm algorithm is chosen among the different available heuristic techniques, due to its apparent simplicity and the recent promising results reported in the scientific literature. Two different orbital maneuvering problems are considered and solved with great numerical accuracy, and this testifies to the effectiveness of the indirect swarming algorithm in solving low-thrust trajectory optimization problems.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

A discrete time optimal control model with uncertainty for dynamic machine allocation problem and its application to manufacturing and construction industries

This paper proposed a discrete time optimal control model in which machine failure time is modeled assuming a Weibull distribution and machine productivity is regarded as a fuzzy variable for dealing with a dynamic machine allocation problem (DMAP) in manufacturing and construction industries. The aim is to maximize total production or construction throughput when uncertainties such as machine breakdowns are taken into account. A failure probability-work time equation is presented to describe the relationship between machine failure probability and mean time to work. To transform the uncertain optimal control model into a deterministic one, the expected value model (EVM) was introduced for forming an equivalent crisp model. The fuzzy variables in the model are also defuzzified by using an expected value operator with an optimistic–pessimistic index. Then a number of lemmas and theorems are presented and proved to formulate the theoretical algorithm so that the crisp model of the DMAP can be solved. Three actual construction and production projects are used as practical application examples. The theoretical algorithm results for the three project examples are compared with a particle swarm optimization approach and a genetic algorithm method, which demonstrates the practicality and efficiency of our optimization method.     

Multi-objective and prioritized berth allocation in container ports

This paper considers a berth allocation problem (BAP) which requires the determination of exact berthing times and positions of incoming ships in a container port. The problem is solved by optimizing the berth schedule so as to minimize concurrently the three objectives of makespan, waiting time, and degree of deviation from a predetermined priority schedule. These objectives represent the interests of both port and ship operators. Unlike most existing approaches in the literature which are single-objective-based, a multi-objective evolutionary algorithm (MOEA) that incorporates the concept of Pareto optimality is proposed for solving the multi-objective BAP. The MOEA is equipped with three primary features which are specifically designed to target the optimization of the three objectives. The features include a local search heuristic, a hybrid solution decoding scheme, and an optimal berth insertion procedure. The effects that each of these features has on the quality of berth schedules are studied.     

Optimal scheduling in film production to minimize talent hold cost

The problem of minimizing the cost due to talent hold days in the production of a feature film is considered. A combinatorial model is developed for the sequencing of shooting days in a film shoot. The problem is shown to be strongly NP-hard. A branch-and-bound solution algorithm and a heuristic solution method for large instances of the problem (15 shooting days or more) are developed and implemented on a computer. A number of randomly generated problem instances are solved to study the power and speed of the algorithms. The computational results reveal that the heuristic solution method is effective and efficient in obtaining near-optimal solutions.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG-0036424. The authors are thankful to two anonymous referees for their helpful comments on an earlier version of this paper.