New Bundle Methods for Solving Lagrangian Relaxation Dual Problems

Bundle methods have been used frequently to solve nonsmooth optimization problems. In these methods, subgradient directions from past iterations are accumulated in a bundle, and a trial direction is obtained by performing quadratic programming based on the information contained in the bundle. A line search is then performed along the trial direction, generating a serious step if the function value is improved by or a null step otherwise. Bundle methods have been used to maximize the nonsmooth dual function in Lagrangian relaxation for integer optimization problems, where the subgradients are obtained by minimizing the performance index of the relaxed problem. This paper improves bundle methods by making good use of near-minimum solutions that are obtained while solving the relaxed problem. The bundle information is thus enriched, leading to better search directions and less number of null steps. Furthermore, a simplified bundle method is developed, where a fuzzy rule is used to combine linearly directions from near-minimum solutions, replacing quadratic programming and line search. When the simplified bundle method is specialized to an important class of problems where the relaxed problem can be solved by using dynamic programming, fuzzy dynamic programming is developed to obtain efficiently near-optimal solutions and their weights for the linear combination. This method is then applied to job shop scheduling problems, leading to better performance than previously reported in the literature.     

P‖Cmin随机算法研究

本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。     

An approximation result for the interval coloring problem on claw-free chordal graphs

We study the problem of finding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to finding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to find an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were made.     

Market Power Issues in Bid-Based Hydrothermal Dispatch

The objective of this work is to investigate market power issues in bid-based hydrothermal scheduling. Initially, market power was simulated with a single stage Cournot–Nash equilibrium model. In this static model the equilibrium was calculated analytically. It was shown that the total production of N strategic agents is smaller than the least-cost solution by a factor of (N/(N+1)). Market power analysis for multiple stages was then carried through a stochastic dynamic programming scheme, where the decision in each stage and state is the Cournot–Nash equilibrium of a multi-agent game. Case studies with data taken from the Brazilian system are presented.     

Redefining Event Variables for Efficient Modeling of Continuous-Time Batch Processing

We define events so as to reduce the number of events and decision variables needed for modeling batch-scheduling problems such as described in [15]. We propose a new MILP formulation based on this concept, defining non-uniform time periods as needed and decision variables that are not time-indexed. It can handle complicated multi-product/multi-stage machine processes, with production lines merging and diverging, and with minimum and maximum batch sizes. We compare it with earlier models and show that it can solve problems with small to medium demands relative to batch sizes in reasonable computer times.     

考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题

针对卷烟企业生产中的批量计划和柔性流水车间调度集成问题,构建了整数规划模型,目标函数由卷烟生产时间、生产线调整次数、卷烟质量、库存成本四部分组成。鉴于该问题的NP-hard性,设计遗传算法进行求解,通过合理设计遗传算子,避免不可行解出现。应用某卷烟企业数据得到优化排产结果,与该企业之前依照经验排产方案进行对比,发现优化排程结果在减少品牌转换次数,提高生产的连续性方面具有明显优势。该算法已作为某卷烟企业排产人员的排产参考,应用于排产决策中,取得了良好的效果,对卷烟企业制定排产计划具有一定的实际指导意义。     

云制造平台加工能力分享调度优化研究

云制造平台加工能力分享的调度优化是云制造模式的核心运营问题。为提高云制造平台对参与能力分享企业资源的利用率,解决实际云制造需求环境下企业级制造资源调度问题,达到云制造平台动态实时的要求,以最小化工期和成本为目标函数,构建了基于平台并面向分享的云加工能力调度模型。为快速求解多个云任务订单的最优调度序列,引入任务简易编码和随机权重,设计了改进的二阶粒子群算法,并提出可分享加工能力时间窗的更新策略。最后,通过算例验证云制造平台加工能力调度机制的可行性和有效性。     

基于随机活动工期的多模式现金流均衡项目调度优化

承包商在项目执行过程中的现金流均衡是保证项目成功的关键因素。本文研究基于随机活动工期的多模式现金流均衡项目调度问题,旨是在项目工期及鲁棒性阈值约束下合理安排活动执行模式与开始时间,实现承包商现金流均衡。本文通过构建整数规划优化模型对研究问题进行刻画,随后设计模拟退火算法进行求解,最后进行案例分析。结果表明:鲁棒性阈值虽然可以保证基准进度的稳定性,但是提高鲁棒性阈值水平反而不利于承包商的现金流均衡,该值过高时甚至得不到可行解。本文研究可为随机活动工期背景下承包商的现金流控制提供定量化决策支持。     

负载均衡问题

自Ron Graham20世纪60年代发表第一篇负载均衡算法的论文以来,平行机排序作为组合优化近似算法理论的首个问题引起了学界的广泛兴趣,其本身研究的不断深化也一路见证了该领域的发展历程.介绍负载均衡问题的来龙去脉,特别是作者所在团队在相关问题的研究进展,从算法和复杂性不同的视角分析经典问题的计算本质,并对未来的研究提出一些建议.     

双目标突发事件应急救援前摄性调度优化

本文以救援时间最短化与计划鲁棒性最大化为目标,研究突发事件应急救援前摄性调度优化问题。作者首先对所研究问题进行界定,其中计划鲁棒性定义为各活动开始时间可调整时差的总和,任务是在应急预算和救援期限的约束下,确定活动执行模式与开始时间以实现上述两个目标。随后,构建问题的0-1规划优化模型,鉴于其强NP-hard属性,设计禁忌搜索启发式算法。最后用一个算例对研究进行说明,得到如下结论:救援时间随应急预算的增加而缩短,随救援期限的放宽而延长;计划鲁棒性随应急预算的增加或救援期限的放宽而提高;当权重分配系数增大时,应急救援时间先保持不变而后缩短,计划鲁棒性则呈减小趋势。本文研究可为突发事件应急救援的组织与协调提供决策支持。