Fleet routing position-based model for inventory pickup under production shutdown

This paper addresses the problem of collecting inventory of production at various plants having limited storage capacity, violation of which forces plant shutdowns. The production at plants is continuous (with known rates) and a fleet of vehicles need to be scheduled to transport the commodity from plants to a central storage or depot, possibly making multiple pickups at a given plant to avoid shutdown. One operational objective is to achieve the highest possible rate of product retrieval at the depot, relative to the total travel time of the fleet. This problem is a variant (and generalization) of the inventory routing problem. The motivating application for this paper is barge scheduling for oil pickup from off-shore oil-producing platforms with limited holding capacity, where shutdowns are prohibitively expensive. We develop a new model that is fundamentally different from standard node-arc or path formulations in the literature. The proposed model is based on assigning a unique position to each vehicle visit at a node in a chronological sequence of vehicle-nodal visits. This approach leads to substantial flexibility in modeling multiple visits to a node using multiple vehicles, while controlling the number of binary decision variables. Consequently, our position-based model solves larger model instances significantly more efficiently than the node-arc counterpart. Computational experience of the proposed model with the off-shore barge scheduling application is reported.     

Minimizing earliness and tardiness costs in stochastic scheduling

We address the single-machine stochastic scheduling problem with an objective of minimizing total expected earliness and tardiness costs, assuming that processing times follow normal distributions and due dates are decisions. We develop a branch and bound algorithm to find optimal solutions to this problem and report the results of computational experiments. We also test some heuristic procedures and find that surprisingly good performance can be achieved by a list schedule followed by an adjacent pairwise interchange procedure.     

Modeling lotsizing and scheduling problems with sequence dependent setups

Several production environments require simultaneous planing of sizing and scheduling of sequences of production lots. Integration of sequencing decisions in lotsizing and scheduling problems has received an increased attention from the research community due to its inherent applicability to real world problems. A two-dimensional classification framework is proposed to survey and classify the main modeling approaches to integrate sequencing decisions in discrete time lotsizing and scheduling models. The Asymmetric Traveling Salesman Problem can be an important source of ideas to develop more efficient models and methods to this problem. Following this research line, we also present a new formulation for the problem using commodity flow based subtour elimination constraints. Computational experiments are conducted to assess the performance of the various models, in terms of running times and upper bounds, when solving real-word size instances.     

Retail store scheduling for profit

In spite of its tremendous economic significance, the problem of sales staff schedule optimization for retail stores has received relatively scant attention. Current approaches typically attempt to minimize payroll costs by closely fitting a staffing curve derived from exogenous sales forecasts, oblivious to the ability of additional staff to (sometimes) positively impact sales. In contrast, this paper frames the retail scheduling problem in terms of operating profit maximization, explicitly recognizing the dual role of sales employees as sources of revenues as well as generators of operating costs. We introduce a flexible stochastic model of retail store sales, estimated from store-specific historical data, that can account for the impact of all known sales drivers, including the number of scheduled staff, and provide an accurate sales forecast at a high intra-day resolution. We also present solution techniques based on mixed-integer (MIP) and constraint programming (CP) to efficiently solve the complex mixed integer non-linear scheduling (MINLP) problem with a profit-maximization objective. The proposed approach allows solving full weekly schedules to optimality, or near-optimality with a very small gap. On a case-study with a medium-sized retail chain, this integrated forecasting–scheduling methodology yields significant projected net profit increases on the order of 2–3% compared to baseline schedules.     

单向航道散货港口船舶调度优化

为提高单向航道散货港口的泊位利用率,研究多港池的散货港口船舶调度优化问题。考虑船舶间需保持安全航行距离、进出港时段交替条件和成簇进出港规则等现实约束,以进港船舶总等待时间最小为目标,构建了混合整数线性规划模型。基于问题的特点,设计了启发式规则与模拟退火算法相结合的混合算法进行求解。在数值实验中分别将该算法的结果同下界值和两种现实调度方案对比。结果表明,运用混合算法求解的结果与下界值的平均相对偏差为5.28%,较两种现实调度方案的目标值优化率提升显著,且平均泊位优化率分别为6.74%和4.71%,验证了方案及算法的有效性。     

基于贪婪算法的水上漂移目标救助物资协同调度方法

受复杂水文、气象等条件影响,水上遇险目标在等待外部救援的过程中可能发生漂移,其漂移的速度与方向将直接影响到水上救助物资调度方案的制订。针对水上事故及其救援的特殊性,在对水上遇险目标漂移路径进行预测的基础上,构建了满足运力、时间限制及应急救助物资需求,包括水上遇险目标周边船舶、岸基救助基地及其附近陆地应急物资储备点共同参与的水陆两阶段多层级协同调度模型,并运用贪婪算法对其进行求解,最后通过算例对模型和算法的有效性进行验证。     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

工序顺序柔性的作业车间调度问题的改进遗传算法求解

针对在工艺设计中提供工序顺序柔性的作业车间调度问题,总结了该问题中柔性工序顺序的类型和特点,并提出了一种求解该问题的改进遗传算法.以尽可能缩短制造周期为目标,结合问题特点,改进了染色体的编码方式,在常用的基于工序顺序的编码方法上融入了基于柔性工序顺序的编码方法,并据此设计了相应的交叉、变异等操作,防止遗传过程中不可行解的产生,避免染色体修复,提高求解效率.最后以MATLAB为工具用某轴承公司的实际生产数据对该算法进行了仿真.通过与不考虑工序顺序柔性的作业车间调度问题遗传算法求解结果进行对比,证明了该算法可行性和有效性.     

并行机问题的模拟退火调度算法研究

研究了一类调度目标是最小化最大完成时间的并行机调度问题.考虑到此问题的NP-hard特性,引入模拟退火算法思想以获取高质量近优解.分析了现有此问题模拟退火算法的缺陷,定义了关键机器和非关键机器,设计了一个包含局部优化的模拟退火算法.除了交换变换,还引入插入变换以改变各子调度中作业个数.大量的随机数据实验用于验证算法解的质量和计算效率,实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解.