Scheduling Step-Deteriorating Jobs on Parallel Machines by Mixed Integer Programming

Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.

Integer Programming Formulations for Maximum Lifetime Broadcasting Problems in Wireless Sensor Networks

Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.

A Two-Objective Integer Programming Model for the Location of Waste Transfer Station and Landfill in IoT Environment: Shenzhen City is Taken as an Example

In the traditional environment, the factors for considering the location of the waste transfer station and the landfill are relatively fixed, and the scale of the problem is small. But in Internet of Things(IoT) environment, the waste storage in the household waste can be monitored in real time, the environmental data can be collected by means of emerging information technology, and the residents are more sensitive to the environmental pollution of the waste. Under such conditions, the method for location of traditional waste disposal facilities needs to be redeveloped to obtain a waste transfer station and landfill site that are suitable for the IoT environment. For this reason, a two-objective integer programming model is designed. The two objectives are lowest cost and minimum impact of waste on residents. The expectations of city managers and residents are considered into the modeling. Through the simulation experiments on different scale problems, the integration method for integer programming model and simulation system is verified to solve the location of waste transfer stations in IoT environment.

A Survey of Model Predictive Control Methods for Traffic Signal Control

Enhancing traffic efficiency and alleviating(even circumventing) traffic congestion with advanced traffic signal control(TSC) strategies are always the main issues to be addressed in urban transportation systems. Since model predictive control(MPC) has a lot of advantages in modeling complex dynamic systems, it has been widely studied in traffic signal control over the past 20 years. There is a need for an in-depth understanding of MPC-based TSC methods for traffic networks. Therefore, this paper presents the motivation of using MPC for TSC and how MPC-based TSC approaches are implemented to manage and control the dynamics of traffic flows both in urban road networks and freeway networks. Meanwhile, typical performance evaluation metrics, solution methods, examples of simulations,and applications related to MPC-based TSC approaches are reported. More importantly, this paper summarizes the recent developments and the research trends in coordination and control of traffic networks with MPC-based TSC approaches. Remaining challenges and open issues are discussed towards the end of this paper to discover potential future research directions.

Circle geometric constraint model for open-pit mine ore-matching and its applications

The circle geometric constraint model （CGCM） was put forward for resolving the open-pit mine ore-matching problems （OMOMP）. By adopting the approaches of graph theory, block model of blasted piles was abstracted into a set of nodes and directed edges, which were connected together with other nodes in the range of circle constraints, to describe the mining sequence. Also, the constructing method of CGCM was introduced in detail. The algorithm of CGCM has been realized in the DIM1NE system, and applied to a short-term （5 d） program calculation for ore-matching of a cement limestone mine in Hebei Province, China. The applications show that CGCM can well describe the mining sequence of ore blocks and its mining geometric constraints in the process of mining blasted piles. This model, which is applicable for resolving OMOMP under complicated geometric constraints with accurate results, provides effective ways to solve the problems of open-pit ore-matching.

Discrete optimization models and methods for management systems of pavement maintenance and rehabilitation

With the rapid development of highway construction and formation of the highway network in China,the man- agement of pavement maintenance and rehabilitation （MR） activities has become important.In this paper,four discrete optimization models are proposed for different parties involved in the management system： government,highway agent,con- tractor and the common users.These four optimal decision models are formulated as linear integer programming problems with binary decision variables.The objective function and constraints are based on the pavement performance and prediction model using the pavement condition index （PCI）.Numerical experiments are carried out with the data from a highway system in Sichuan Province which show the feasibility and effectiveness of the proposed models.

Weekly Fleet Assignment Model and Algorithm

A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.

Mathematical Models for a Social Partitioning Problem

In this paper we develop modeling techniques for a social partitioning problem. Different social interaction regulations are imposed during pandemics to prevent the spread of diseases. We suggest partitioning a set of company employees as an effective way to curb the spread, and use integer programming techniques to model it. The goal of the model is to maximize the number of direct interactions between employees who are essential for company’s work subject to the constraint that all employees should be partitioned into components of no more than a certain size implied by the regulations. Then we further develop the basic model to take into account different restrictions and provisions. We also give heuristics for solving the problem. Our computational results include sensitivity analysis on some of the models and analysis of the heuristic performance.

Fitting boxes to Manhattan scenes using linear integer programming

We propose an approach for automatic generation of building models by assembling a set of boxes using a Manhattan-world assumption.The method first aligns the point cloud with a per-building local coordinate system,and then fits axis-aligned planes to the point cloud through an iterative regularization process.The refined planes partition the space of the data into a series of compact cubic cells(candidate boxes)spanning the entire 3D space of the input data.We then choose to approximate the target building by the assembly of a subset of these candidate boxes using a binary linear programming formulation.The objective function is designed to maximize the point cloud coverage and the compactness of the final model.Finally,all selected boxes are merged into a lightweight polygonal mesh model,which is suitable for interactive visualization of large scale urban scenes.Experimental results and a comparison with state-of-the-art methods demonstrate the effectiveness of the proposed framework.

Fair Scheduling Models for Doubles Group Competitions

This paper gives integer linear programming models for scheduling doubles tennis group competitions. The goal is to build a fair and competitive schedule for all players. Our basic model achieves that for each player the average ranking of his partners in all matches is as close as possible to the average ranking of his opponents in all matches. One of the variations of the basic model provides that each matchup is fair and competitive. We also give models for the case when the number of players is 4n + 2, and thus one of the matches has to be singles. Our models were implemented and tested using optimization software AMPL. Computational results along with schedules for some typical situations are also given the paper.

低轨星座传感器资源调度的自主任务规划建模方法

低轨星座传感器资源的优化调度是复杂多约束下的任务规划问题,为了满足多个运动目标全程跟踪与监视的资源实时优化调度需求,提出一种星上自主快速求解的规划模型.在对自主任务规划问题进行详细建模的基础上,考虑各项约束条件与优化因素,将原问题转化成简易的0-1线性整数规划模型,并构建多目标跟踪试验场景对所提方法进行了仿真验证.仿真结果表明,基于简易规划模型的资源调度可实现多目标的全程跟踪与监视.

洪水过程线同频放大混合整数规划模型

当设计洪水峰、量关系较差时,设计洪水过程线同频放大会出现明显的畸形。构建了设计洪水过程线同频放大混合整数规划模型,以洪水过程线各时段流量作为决策变量,提出了时序系列光滑度函数,并以此作为目标函数,以设计洪峰流量、不同时段设计洪量作为约束条件,首次加入了涨落同向约束条件,保证设计和典型洪水过程线具备相近模式。实例研究表明,当设计洪水峰、量关系不协调时,此模型计算的设计洪水过程线顺滑、各频率之间无交叉,与典型洪水过程线(特别在洪峰附近时段保持)相近模式。研究成果为设计洪水过程线同频放大提供了新的、可行的方法。

基于动态优先级的机坪车辆避冲突运行规划方法

【目的】针对机坪车机混行环境,提出了一种考虑动态优先级的避冲突运行规划方法。【方法】首先,从作业效率和运行风险两个层面,提出动态优先级计算方法,完善了多类型保障车辆时变冲突风险划分的规则。其次,考虑保障车辆运行规则和物理特性,建立了考虑行驶和等待时间最小化的混合整数规划模型。最后,设计全局路径优化的两阶段算法进行求解,并通过低时间复杂度的改进冲突探测方法,弥补了传统方法求解大规模复杂问题在时效性方面的不足。【结果】实验表明,设计的算法在大、小规模场景均有较好的适用性,相比对照算法,冲突优化幅度提升7.6%,车辆与航空器冲突占比降低7.5%。【结论】所提方法满足了保障车辆差异化运行要求,实现了车辆和航空器混合运行环境下避冲突路径规划的功能。

基于混合整数规划的数据中心冷却能耗优化

以广州某数据中心水蓄冷冷却系统为研究对象,提出了一种基于混合整数线性规划的模型预测控制方法.该方法以数据中心冷却系统的能耗最低为优化目标,通过对冷却系统和环境条件进行建模,并结合能源成本和冷却系统效率,确定最佳的冷水机组运行策略和水蓄冷冷却系统的时序控制.在优化过程中,考虑了冷水机组的最小连续运行时间对冷却系统能耗的影响,并确定了最佳取值,提高了机组的稳定性,减少了因冷机频繁启停带来的能耗浪费.通过全年能耗模拟,相较于传统控制方法,该方法将总能耗降低了6.52%,总运行费用降低了6.93%.

连铸切割的在线优化

连铸是将钢水变成钢坯的生产过程,在连铸停浇时,会产生尾坯,尾坯的切割也是连铸切割的组成部分。在满足用户的目标值的前提下,我们尽量让切割损失最小。在合理假设的前提下对连铸切割的合理优化,综合运用EXCEL、MATLAB等多种工具,根据数学中的优化及整数规划知识建立优化模型,从而求出最优解。

基于CSA-AFSA算法的集装箱港口连续型泊位分配优化

为提升集装箱港口运营效率,笔者研究了考虑潮汐因素与泊位偏好的连续型泊位分配问题。引入了船舶时空矩形不可重叠约束和潮汐时间窗约束,构建以最小化船舶等待、延迟离港、泊位偏离以及在港期间油耗费用和最小为目标的混合整数线性规划模型;根据模型特征,采用CPLEX求解软件、鱼群算法、布谷鸟搜索算法和布谷鸟鱼群混合算法进行求解,以计划周期为36 h的20个不同规模的船舶到港数据为研究算例,通过算例求解得到符和潮汐时间窗、泊位偏好等要求的泊位分配方案。算例求解表明:算例规模较小时,CPLEX可以在较短时间内求出最优泊位分配方案;算例规模较大时,CPLEX求解时间较长,布谷鸟鱼群混合算法可以在平均3 min内求出与CPLEX差距为0.39%~4.20%的次优解;不同算法间的对比表明,布谷鸟鱼群混合算法求解能力更优,混合算法所得泊位分配方案中,乘潮船舶的进出港时刻均在潮汐高水位时段,且85%以上的船舶在偏好泊靠点200 m内接受装卸服务。

含分布式新能源和需求响应负荷的虚拟电厂定价机制及优化调度

面对电网中分布式风电、光伏发电以及柔性负荷的广泛接入,将这些资源通过虚拟电厂(VPP)进行聚合,采用合理的电价机制来引导用户参与需求响应,可以有效提升新能源的消纳能力并降低整体运营成本。传统的分时电价机制往往难以实现需求响应负荷与新能源出力的良好匹配,可能会导致需求响应的不合理或过度反应。为此,针对包括分布式风电、分布式光伏发电和柔性负荷的VPP,提出了一种基于新能源出力的VPP内部定价机制,并设置电力交易优先级来引导VPP内部各资源优化运行,以VPP的整体运营成本最小化为目标,构建了一个VPP优化调度的混合整数线性规划模型。基于内蒙古某地区的实际数据进行仿真计算,结果表明,与基于传统分时电价的优化结果相比,该方法能显著提高新能源的利用率并降低VPP的运行费用。

基于混合整数规划的智能车横纵向一体化滚动优化决策

本文针对智能车辆的行为决策问题,设计了基于混合整数规划的智能车横纵向一体化滚动优化决策方法.该方法首先将纵向车速表示为非整数,将期望车道表示为整数控制量,建立了混合整数智能车决策简化模型;然后,设计了横纵向一体化滚动优化决策方法,决策出纵向车速和换道动作,根据系统输出与非线性约束的时域关系证明了优化问题的递归可行性并通过遗传算法求解非线性混合整数规划优化问题.基于车辆动力学仿真软件veDYNA和Simulink进行了联合仿真,并在红旗E-HS3智能车上开展了实车试验,结果表明,本文提出的基于混合整数规划的智能车横纵向一体化决策方法能够实现超车、避障、跟车、停车和弯道工况下的行为决策.

基于多层次客流需求的高铁列车谱系结构优化设计

高速铁路的高质量服务特性激发了大量不同类型旅客的多样化出行需求。当前铁路旅客列车开行数量日益增多,但提供的客运产品分类较少,列车谱系化特征不明显,难以适应旅客的多样性需求。设计具有显性差异特征的铁路客运产品,满足不同类型旅客在经济、快捷、方便、舒适等方面的异质性出行需求,实现铁路客流分类与产品分类的高效匹配,对新时代铁路旅客运输发展具有重要意义。结合当前我国高速铁路网列车开行结构现状,并考虑路网中各线路具有不同的资源、能力、客流特征,基于铁路客运产品谱系化思想和发展趋势,从列车停站模式、旅速、运距、频率几个维度将既有列车种类进一步拓展划分为11类谱系,分析多层次旅客对谱系列车的选择,运用整数规划并结合客流分配技术,构建决策各线路区段上从11类谱系中选择列车开行种类、范围和数量的列车谱系结构优化模型,达到客流类型与列车谱系结构之间的有效匹配。以我国部分高铁路网为例开展案例研究,研究结果表明:优化后的列车开行结构明显改善,各高铁线路上列车谱系结构差异化分布特征明显;不同层次客流旅速、列车谱系和客流层次对应、列车客座率、“车-流”运距比等指标均表现出较好的“车-流”匹配效果。在高铁列车大规模成网运营条件下,研究结果可为设计具有谱系特征的列车产品提供方法和技术指导。

民机机队航班指派与维修调度联合优化策略

针对机队维修调度定检模式的经济性不足,综合飞机个体维修需求和机队整体航班运营与维修资源共享,提出一种新的民机机队航班指派与维修调度联合优化策略。为耦合飞行路径与维修方案,将飞行路径中涵盖的维修机会作为交互关键,创新改进了连接网络模型框架以将航班指派与维修调度统筹规划。全面考虑航班全覆盖与执飞连续性的运营约束、飞机适航性要求与维修资源承载限制的维修约束,基于网络结构建立了联合优化整数规划模型。设计了一种基于原始问题分解的两阶段求解算法,通过维修机会导向的航班指派优化与维修任务择优分配,高效输出联合调度方案。通过实例分析证明所提策略能够高效获得低成本调度方案,为航司维修调度优化提供指导。