基于时间窗延迟的资源约束项目调度双层优化研究

本研究从业主—承包商交互的视角构建了一种RCPSP(resource-constrained project scheduling problem)双层优化模型,即在可更新资源约束条件下,项目双方如何进行交互决策达到双方NPV(Net present value)最大化的目标。首先对研究问题进行界定,构建资源约束下的max-NPV项目调度双层优化模型;然后利用延迟优先规则设计了一种基于时间窗延迟的嵌套式自适应遗传算法来求解该模型,以达到双方NPV最大化;最后用一个算例验证算法的有效性,同时通过PSPLIB数值实验说明算法的稳定性,并分析关键参数对项目双方收益的影响。研究结果为项目进程的安排以及奖励机制的设计提供依据,以提高双方利益。     

两台自私型机器上自私工件排序的PoA紧界

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。     

地下金属矿山采掘作业计划优化模型

为了实现地下金属矿山采掘作业计划编制的实时准确与科学有效性,针对矿山作业地点分散、生产组织复杂、矿石质量难以控制等特征,构建了基于0-1整数规划的作业计划优化模型.通过分析开采技术经济指标及空间逻辑关系,以最小品位偏差为目标,将产量均衡、出矿能力以及品位高低结合开采等转化为约束条件,考虑各采场作业工序、回采顺序、生产能力以及其他生产要素等,运用计算机技术和整数规划方法,得出地下矿山采掘作业计划最优方案.以国内某大型金矿为案例进行了模型的有效性验证,解算出矿山最优的采掘作业计划,并得出作业计划甘特图.结果表明,模型能够指导完成生产作业任务,且满足作业计划连续性和均衡性要求.     

两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件，每个工件包含两类任务：Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的，Map任务可以并行处理，即可以任意分割成若干小的任务并在两台机器上同时处理，而Reduce任务只可以在单台机器上处理。一旦工件到达，必须为其指派机器和开工时间，目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析，得到其一般情形下的竞争比当$s\geq（1+\sqrt{5}）/2$时为$1+1/s$，否则为$1+s/（s+1）$。而当每个工件$J_j$都满足其Map任务总长大于等于Reduce任务总长时，其竞争比当$s\geq（1+\sqrt{3}）/2$时不超过$1+1/（2s）$，否则为不超过$1+s/（2s+1）$。     

Mathematical models for job-shop scheduling problems with routing and process plan flexibility

As a result of rapid developments in production technologies in recent years, flexible job-shop scheduling problems have become increasingly significant. This paper deals with two NP-hard optimization problems: flexible job-shop scheduling problems (FJSPs) that encompass routing and sequencing sub-problems, and the FJSPs with process plan flexibility (FJSP-PPFs) that additionally include the process plan selection sub-problem. The study is carried out in two steps. In the first step, a mixed-integer linear programming model (MILP-1) is developed for FJSPs and compared to an alternative model in the literature (Model F) in terms of computational efficiency. In the second step, one other mixed-integer linear programming model, a modification of MILP-1, for the FJSP-PPFs is presented along with its computational results on hypothetically generated test problems.     

基于遗传算法的船舶分段运输调度方法

为解决船厂平板运输车搬运船舶分段的日程计划问题,建立了利用最少数量的平板运输车完成分段搬运作业,以及所有分段搬运作业完成时间最小化的两阶段优化模型,提出了基于遗传算法的2种启发式方法以实现模型求解,并用数值实验的方法进行验证.结果表明,所提出的2种方法都能够较好地完成船舶分段运输调度计划,并实现平板运输车的高效利用.     

舞台调度视频监控 IP 网络化标准体系构建

利用先进的音视频技术、多媒体技术和计算机网络技术,实现基于IP网络的舞台监督与调度集成系统,该系统主要包括内通对讲子系统(包括有线和无线)、视频监控子系统。目前国内外关于IP网络化舞台监督与调度系统的相关规范、标准研究仍是一项空白,为了能够在各大剧院广泛地推广应用,系统的标准化已经成为现阶段亟待解决的问题之一。其中IP网络化的舞台调度视频监控是系统的重要组成部分,主要采用网络视频监控技术。本文结合现阶段的网络视频监控相关的标准,研究了IP网络化舞台调度视频监控系统的标准体系构建。本文的研究为舞台监督与调度集成系统标准规范的制订奠定了理论基础和具有实际指导意义。     

Concurrent transmission with minimal SR-pair interference in WiMAX mesh networks

Performance of wireless mesh networks can be greatly improved by spatial reuse (SR), therefore, lots of algorithms have been proposed to maximize the number of concurrent transmissions. However, most methods only considered the interference brought by the sender nodes. In this paper, we study the interference model in WiMAX mesh networks and propose a minimal SR-pair interference model to perform concurrent transmissions in both uplink and downlink directions. Simulation results show that our model is more efficient and stable, i.e., it increases the number of concurrent transmissions and its performance is constant and independent of transmission directions. Biography: XIONG Qing(1978–), male, Ph. D., research direction: wireless mesh networks.     

110警车配置及巡逻方案

针对110警车调度问题,引入了图论中的最短路算法以及计算几何的相关理论,建立了车辆调配模型、巡逻路线模型以及基于模糊数学的评价指标模型.另外,用C++编写了一个可视化的软件,不仅实现了手动描点,自动求出覆盖线段集合的功能,同时利用计算机模拟警车的巡逻路线,最后通过计算机检验得到结果,其合理性和实用性都令人满意.针对问题一,通过人机结合,配置17辆警车就能实现D1的目标,很好地兼顾了警车巡逻的运行成本,减少公安部门车辆和人员等的投入.针对问题二,采用模糊数学相关理论使评价指标实现了从定性到定量的转变.针对问题三和六,在D1的基础上,兼顾了巡逻效果的显著性,采用最少被巡逻道路优先的贪心算法建立了动态巡逻模型,得到了合理的巡逻方案.在此方案中,我们动用了30辆警车完成了问题一的目标.另外还额外考虑了案发事件概率不均匀分布的情况,建立了改进模型.针对问题四,在完成问题三指标的基础上,为了尽可能提高巡逻车辆的隐蔽性和增强巡逻效果,采用轮盘赌算法来引入随机性.针对问题五,采用最远距离道路优先贪心策略,使模型尽可能满足条件D1,D2.针对问题七,提出了一些额外因素及其解决方案,进一步完善了模型,使模型更贴近现实.     

Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments

We study bicriteria problems of minimizing maximum tardiness and total due date assignment cost in various scheduling environments. We assume that each job can be assigned a different due date without any restriction, and that each due date assignment cost is a non-decreasing function of the quoted due date. We settle the complexity of most of the problems studied by either proving that they are NP-hard or finding a polynomial time solution for them. We also include approximation and non-approximability results for several parallel-machine problems.