局外k-卡车调度问题及其MCMF法求解

局内问题及其解法的研究是优化领域研究热点之一,而有关局内问题解法的研究必将涉及相应的局外问题.针对局外k 卡车调度问题,给出了如下研究结果:给出了一种通过构造加权有向图,进而应用最小费用最大流法(MinimalCostMaximalFlow,简记为MCMF)求解该问题的方法;给出了应用动态规划(DynamicProgramming,简记为DP)以及MCMF求解该问题的算法复杂性并给予证明;通过一个具体的实例来说明MCMF求解的思路.     

局内封闭式车辆调度问题及其竞争策略

基于k-卡车问题和局内运输问题,提出了具有时间窗的局内封闭式车辆调度问题,建立了相关的模型,研究了当车辆数为1时该问题的竞争分析的有关结果,给出了三种不同的竞争策略,得到了相应的竞争比,并进行了理论证明.     

具有时间窗的局内开放式车辆调度的竞争分析

基于k-卡车问题和局内运输问题，提出了具有时间窗的局内开放式车辆调度问题．该问题的优化目标为：在服务需求的发布为局内方式的条件下，如何最小化完成整个服务需求序列的时间跨度．建立了该问题的数学模型并对有关的概念和参数进行了定义和说明．研究了当车辆数为1时该问题的竞争分析的有关结果：给出并证明了对于该问题的竞争策略的竞争比下限；针对该局内问题，设计了两种不同的竞争策略，得到了相应的竞争比，并进行了理论证明．     

直线上的k-配送小车调度问题与竞争策略

提出和研究了直线上的局内k-配送小车调度问题。应用复位策略，竞争比为k 2；设计了解决该问题的竞争算法，证明采用局部双覆盖策略Local Double Coverage Strategy(LDCS)的竞争比为k.最后，简单地分析了该问题的一个特例——局内电梯调度问题，得出了比较结果。     

局内车辆选线问题和竞争策略分析

将现实物流配迭中所遇到的问题抽象为一个局内车辆选线问题，考虑堵塞点动态产生、一个个遇到的情况下的车辆调度方案，经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解)，在条件发生变化时就会失去其最优性。而论文所考虑的竞争算法能使得调度方案对于变化因素的每一个特例得到的解离最优方案给出的解总在一定范围之内。不仅设计了解决局内车辆选线问题的竞争算法：贪婪策略和复位策略，分析了不同情况下算法各自的竞争比，而且给出了此问题的竞争比下界。     

基于遗传算法的混合Flow-shop调度方法

混合Flow-shop调度问题（Hybrid flow-shop scheduling problem,HFSP),是一般Flow-shop调度问题的推广，由于在某此工序上存在并行机器，所以比一般的Flow-shop调度问题更复杂。本文提出了遗传算法求解混合Flow-shop调度问题的方法，给出了一种新的编码方法，设计了相应的交叉和变异操作算法，能够保证个体的合法性，同时又具有遗传算法本身所要求的随机性。最后给出了某汽车发动机厂金加工车间的生产调度实例，表明了此算法的有效性。     

卫星观测联合调度问题的VRP与JSP模型

针对一类具有车辆路线和加工调度混合特征的卫星观测联合调度问题，对车辆路线和加工调度两类常见的优化问题模型及其求解技术进行了比较研究，探讨了两类模型的相互转化形式及模型特征与求解技术问的相互关系，在此基础上，给出了一种可行的卫星观测联合调度问题的建模方式，并利用约束规划工具软件进行了实现。与其它形式模型的比较表明，所建模型的求解效率和质量更适合大规模卫星调度问题的实际应用需求。     

限制图上的局内出租车调度与竞争算法

经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去．局内问题与竞争算法则是针对特定的优化问题来研究这样的方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内．本文应用复位策略给出限制图上局内ｋ 出租车调度问题竞争比为１＋ （ｎ－ ｋ）λ的竞争算法．     

用遗传算法解决在并行机上带有不同交货期窗口的Job-Shop调度问题

本文讨论了不同交货期窗口下的提前／拖期并行机调度问题，提出了染色体用工件编号进行编码规则，给出了用稳步遗传算法求解上述问题的方法，仿真实验表明了算法及编码规则的可行性和有效性。     

多目标动态规划及其在过程优化中的应用

本文以Waltz分层优化方法为基础,提出了多目标动态规划的分层解法。该方法通过将目标按其重要性为序排列,将多目标决策问题转化为一系列的单目标决策问题,然后分别在相应的工程宽容范围内分层求解。文中给出了有关分层解法的弱有效解和有效解的两个定理证明。分层解法的主要优点是计算量逐层减小。最后,本文给出了这一方法在求解多级化学反应器操作优化问题中应用的示例。     

带时间窗的局内开放式车调度问题的竞争分析

对于带时间窗的局内车辆调度问题，以往文献的研究都是关于k=1的单车调度，其开放式情形下最好的竞争比为4。针对该问题本文进行了开放式情形下多辆丰（k≥2）调度的研究分析，设计了解决试问题的竞争算法，并证明了其竞争比为3．5。同时本文分析了该问题的一种特殊情形——单车调度问题，可证明其竞争比为3．优于已有结果。     

SCHEDULING TWO GROUPS OF JOBS WITH INCOMPLETE INFORMATION

In real world situations, most scheduling problems occur neither as complete off-line nor ascomplete on-line models. Most likely a problem arises as an on-line model with some partialinformation. In this article, we consider such a model. We study the scheduling problem P(n_1,n_2),where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon asall jobs in the first group are assigned, the second job group appears. The objective is to minimize thelongest job completion time(makespan). We show a lower bound of 3/2 even for very special cases.Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed forthe general case. The main contribution of this paper is to discuss the impact of the quantity ofavailable information in designing an on-line algorithm. It is interesting to note that the absence ofeven a little bit information may significantly affect the performance of an algorithm.     

车间作业调度(JSSP)技术问题简明综述

介绍了车间作业调度技术问题的理论、算法分类、特点及一般框架 .将 JSSP问题的研究方法分为两类 :最优化方法和近似 /启发式方法 ,对各种算法逐一分析比较 .总结了近年来该研究领域取得的进展和存在的问题 ,并指明了将来的发展方向.     

The complexity and on-line algorithm for automated storage and retrieval system with stacker cranes on one rail

This paper considers an on-line scheduling and routing problem concerning the automated storage and retrieval system from tobacco industry. In this problem, stacker cranes run on one common rail between two racks. Multiple input/output-points are located at the bottom of the racks. The stacker cranes transport bins between the input/output-points and cells on the racks to complete requests generated over time. Each request should be accomplished within its response time. The objective is to minimize the time by which all the generated requests are completed. Under a given physical layout, the authors study the complexity of the problem and design on-line algorithms for both one-stacker-crane model and two-stacker-crane model. The algorithms are validated by instances and numerical simulations.     

有时间窗的非满载车辆调度问题的遗传算法

有时间窗的车辆调度问题是一个典型的ＮＰ－难题，传统求解方法往往不能令人满意，本文将货运量约束和时间窗约束转化为目标约束，设计了基于自然数编码的可同时处理软、硬时间窗约束的遗传算法，实验分析获得了较好的结果。     

动态取送问题研究综述

随着动态取送问题(dynamic pickup and delivery problem,DPDP)应用于网约车调度、外卖配送等新的领域,具有大规模、强实时、强动态特征的DPDP引起学术界的日益关注.本文首先介绍了动态取送问题的应用和影响因素,从配送模式和配送对象的角度对不同应用背景下的DPDP进行了分类.之后介绍了动态取送问题的定义和特征、常见的求解策略和动态算法的评价标准.选取了三个典型应用(动态拨召服务、网约车调度、即时配送),比较了不同应用背景下问题的共性特征和区别之处,分类回顾了不同问题模型和算法的研究成果.最后,结合目前研究成果对未来发展方向进行了展望.     

一种新的求解Flow Shop问题的启发式算法

同顺序 Flow Shop问题是一个著名的 NP难题 ,至今尚未找到有效算法 .总体来讲 ,求解该问题的启发式算法主要可分为规则式算法和迭代式算法两种 .对该问题有很多求解目标 ,如最小加工周期 ( min makespan) ,工件的最小平均在系统的停留时间 ( min mean flow tim e)等 .本文以求解最小加工周期为目标 ,基于目前已知的性能最好的算法 NEH算法的基本思想 ,提出了一种新的启发式算法 -组合指标算法 .大量的数据实验表明 ,新的算法具有很好的计算结果 ,而且这种算法可以说是给出了求解 Flow shop问题的一种新的思路和方向.