基于粒子群算法的流程工业生产调度研究

以优化流程工业生产为目标,研究了将基于惯性权重的粒子群算法应用到流程工业的生产调度问题。在对流程工业生产调度问题进行分析的基础上,建立了以总加工完成时间最短为优化目标的生产调度模型。调度算法采用动态惯性权重,使惯性权值在粒子群算法搜索过程中线性变化,以提高粒子群算法的优化性能。给出了粒子编码与解码实现方法,以及具体的算法实现过程。以某流程工业企业生产调度实例为例,利用建立的优化调度模型和设计的粒子群算法进行了实验仿真,结果表明,建立的调度模型和设计的算法是可行的,与蚁群系统方法相比较,有较好的调度性能,适用于解决流程工业实际生产调度问题。     

铝工业虚拟企业伙伴选择问题优化方法研究

铝工业生产调度都是针对某一特定的生产过程,单纯地追求产量为最高目标,凭经验进行调度。而产量目标的实现不但以牺牲能耗为代价,调度结果还达不到全局最优,无法实现能耗最优为目标的生产调度与资源配置,造成能源的浪费。以生产能耗、运输能耗及库存能耗之和最小为目标函数,结合企业生产经验,建立了铝工业虚拟企业伙伴选择优化调度模型,并提出了一种混合离散粒子群算法对其进行求解。最后,利用工业数据进行了仿真实验,结果表明该优化调度方法在缩短调度时间、资源优化配置等方面优化效果明显,达到了节能降耗的目的。     

Robust scheduling optimization for flexible manufacturing systems with replenishment under uncertain machine failure disruptions

This paper studies the scheduling problem for the flexible manufacturing systems (FMSs) under uncertain machine failure disruptions, where machine allocations and job schedules need to be determined to achieve a set of production due-date requirements as well as possible. A robust scheduling optimization model is proposed based on the concept of threshold scenario, bounded by which the due-dates are guaranteed to be achieved. It is shown that the associated stochastic scheduling problem can be equivalently solved by computing the solution of a mixed-integer linear program (MILP). Computational results show that our proposed model performs well in achieving the planned due-dates under uncertainty when compared to various standard approaches. The practical applicability of our approach is verified using a real stamping industry application, in which the stamping parts are various types of voice coil motor yokes used in commercial hard disk drive actuators. Apart from FMSs, the proposed approach can also be applied to various other industries including project scheduling, airline scheduling, transportation scheduling.     

间歇生产调度优化模型的分周期逼近算法

间歇生产调度过程中存在许多不确定因素,其中最重要的是需求不确定.考虑需求不确定的多周期间歇生产调度优化模型采用离散或连续时间表达方式,将调度时间域分割成大量与调度决策相关的时间段,导致模型中存在大量整数变量,给模型求解造成很大困难.本研究对已有求解方法进行了分析,提出分周期逼近算法.将多周期间歇生产调度决策问题分解为第一周期调度决策问题和其余周期调度决策问题,简化结构,加快求解速度.通过方案树聚集将表达需求不确定信息的方案树转化成若干方案文件,针对每个方案文件应用确定性方法获得调度决策,但只保留第一周期调度决策,可以减小最小利益方案对期望利益的影响,提高第一周期调度决策水平;获得若干第一周期候选调度决策后,以时间收缩三阶段方法确定其余周期较优调度决策,同时应用时间收缩策略和补偿策略,提高其余周期调度决策水平;最后用期望利益评估第一周期候选调度决策并确定全部周期调度决策.实例研究证明了本文提出的算法能够提高间歇生产调度决策水平,同时加快求解速度,能够有效求解多周期间歇生产调度优化模型.     

网格调度机制研究综述

对网格调度体系结构、网格调度模型以及实际的网格项目和系统所采用的网格调度机制进行了分析,介绍了目前网格调度机制的研究情况,从网格调度研究的不同侧面对其进行了综述,阐述了网格调度的基本概念。针对网格与Web服务融合的情况,提出了服务网格环境下的服务调度问题,分析了解决服务调度的关键技术,结合已有的研究成果展望了未来网格调度的研究方向。     

面向云计算的任务调度算法综述

介绍了云计算,对任务调度在云计算中的地位做了分析,并由任务调度出发,对云计算任务调度算法的研究现状进行分类、梳理和总结.根据调度目标的不同,将算法分为单目标优化的任务调度算法和多目标的任务调度算法,对每类方法的代表性算法进行了分析介绍,并详细总结了每类方法的基本思想,对其优缺点做了分析、对比,并对改进方式进行了归纳.     

Optimal rate-based scheduling on multiprocessors

The PD² Pfair/ERfair scheduling algorithm is the most efficient known algorithm for optimally scheduling periodic tasks on multiprocessors. In this paper, we prove that PD² is also optimal for scheduling “rate-based” tasks whose processing steps may be highly jittered. The rate-based task model we consider generalizes the widely-studied sporadic task model.     

非对称多核处理器上的操作系统集成调度

相对于对称多核处理器,非对称多核处理器具有更高的效能,将成为未来并行操作系统中的主流体系结构.对于非对称多核处理器上操作系统的并行任务调度问题,现有的研究假设所有核心频率恒定,缺乏理论分析,也没有考虑算法的效能和通用性.针对该问题,该文首先建立非线性规划模型,分析得出全面考虑并行任务同步特性、核心非对称性以及核心负载的调度原则.然后,基于调度原则提出一个集成调度算法,该算法通过集成线程调度和动态电压频率调整来提高效能,并通过参数调整机制实现了算法的通用性.提出的算法是第一个在非对称多核处理器上结合线程调度和动态电压频率调整的调度算法.实际平台上的实验表明:该算法可适用于多种环境,且效能比其他同类算法高24%～50%.     

Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible

Optimal online scheduling algorithms are known for sporadic task systems scheduled upon a single processor. Additionally, optimal online scheduling algorithms are also known for restricted subclasses of sporadic task systems upon an identical multiprocessor platform. The research reported in this article addresses the question of existence of optimal online multiprocessor scheduling algorithms for general sporadic task systems. Our main result is a proof of the impossibility of optimal online scheduling for sporadic task systems upon a system comprised of two or more processors. The result is shown by finding a sporadic task system that is feasible on a multiprocessor platform that cannot be correctly scheduled by any possible online, deterministic scheduling algorithm. Since the sporadic task model is a subclass of many more general real-time task models, the nonexistence of optimal scheduling algorithms for the sporadic task systems implies nonexistence for any model which generalizes the sporadic task model.     

Bottleneck analysis for network flow model

It is very important to develop effective strategies for process industry to implement feasible scheduling while the process bottlenecks work optimally. However, the bottlenecks adopted by the existed scheduling strategies are often partial bottlenecks, local bottlenecks, or even deceptive bottlenecks, which are basically not key constraints to achieve optimal objective, so that the corresponding scheduling strategies are not perfect, and the further improvement and evaluation can hardly be proposed. So, it is a valuable issue to analyze the bottlenecks both in academic and engineering fields. This paper aims at the minimum cost problem of generalized network flow model to define and analyse three classes of bottlenecks based on generalized network simplex algorithm, and the corresponding search algorithms are proposed in this paper. The obtained bottlenecks cannot only be used to determine whether the object cost will be increased or decreased, but also be used to propose the corresponding strategy to evaluate the improvement on the network flow model for scheduling. Finally, a typical example is discussed.     

基于Lebesgue采样的动态反馈实时调度模型

提出一种基于Lebesgue采样方法和弹性调度算法的动态反馈实时调度模型。通过调整实时任务的执行速率,使软实时系统的系统负载始终保持在参考值以下。利用硬件看门狗技术在系统过载时产生中断,实现基于事件的Lebesgue采样。在实时操作系统RTAI中实现该调度模型,并对模型的暂态性能和稳态性能进行分析验证。实验结果表明,该模型不仅保持了系统的稳定性,还能显著降低调度算法的系统开销。     

Scheduling Optimization Modelling: A Case Study of a Woven Label Manufacturing Company

Production scheduling involves all activities of building production schedules, including coordinating and assigning activities to each person, group of people, or machine and arranging work orders in each workplace. Production scheduling must solve all problems such as minimizing customer wait time, storage costs, and production time; and effectively using the enterprise’s human resources. This paper studies the application of flexible job shop modelling on scheduling a woven labelling process. The labelling process includes several steps which are handled in different work-stations. Each workstation is also comprised of several identical parallel machines. In this study, job splitting is allowed so that the power of work stations can be utilized better. The final objective is to minimize the total completion time of all jobs. The results show a significant improvement since the new planning may save more than 60% of lead time compared to the current schedule. The contribution of this research is to propose a flexible job shop model for scheduling a woven labelling process. The proposed approach can also be applied to support complex production scheduling processes under fuzzy environments in different industries. A practical case study demonstrates the effectiveness of the proposed model.     

网格环境下基于信任机制的资源调度研究

信任是网格资源调度中一个很重要的因素,也是影响网格计算有效性和性能的关键技术之一。将信任机制引入到网格资源调度中,提出了网格环境下的信任模型和基于信任机制的资源调度模型,在调度策略上对传统的Min-Min算法进行了改进,提出了基于信任机制的Trust-Min-Min算法。仿真结果表明,算法不仅可以缩短任务的总执行时间,而且可以有效地平衡负载,是网格环境下一种有效的资源调度方法。     

时间资源调度模型

本文首先提出Ｐｅｔｒｉ网调度模型的三个层次及其构造算法，在此基础上重点讨论第三个层次；时间资源调度模型－改进的Ｐｅｔｒｉ网模型，本文还给出一个相庆的调度算法，我们提出的调度模型对调度问题的描述极为清晰，对调度求解提供了一个强有力的工具。     

混合型实时容错调度算法的设计和性能分析

以往文献中研究的实时容错调度算法都只能调度单一的具有容错需求的任务.该文建立了一个混合型实时容错调度模型,提出一种静态实时容错调度算法.该算法能同时调度具有容错需求的实时任务和无容错需求的实时任务.该文还提出了一个求解最小处理机个数的算法,用于对静态实时容错调度算法的性能进行模拟分析.为了提高静态调度算法的调度性能,提出了一种动态调度算法.最后,通过模拟实验分析了静态和动态调度算法的性能.实验表明,调度算法的性能与实时任务的个数、任务的计算时间、周期和处理机个数等系统参数相关.     

基于二阶段法的配煤调运系统的设计与实现

现有的配煤调运系统没有将车辆调度的优化问题和配煤优化问题作为一个整体考虑,存在较大的局限性,难以满足日益复杂的煤炭调运任务的需要。针对上述问题,提出了一种以经济效益最大化为目标的配煤调运数学模型,给出了基于二阶段法的该模型的求解算法,并以山西某矿业公司为例,设计了以该模型为基础的动态配煤调运系统。实际运行表明,该系统既降低了配煤调运的运输费用,又协调了用户需求与原煤质量指标之间的矛盾,具有广阔的应用前景。     

基于EDF调度策略的端到端实时系统可调度性分析算法

端到端实时任务调度模型可用于描述许多分布式实时系统.提出一种基于EDF调度策略的端到端实时任务调度模型,给出了端到端实时系统的可调度性判定条件,并提出其可调度性分析算法,该可调度性判定条件及可调度性分析算法适用于采用非连续工作型同步协议和连续工作型同步协议控制下的端到端实时系统.与固定优先级的端到端实时任务调度模型及其算法相比,基于EDF调度策略的端到端实时任务调度模型和算法更加简单和易于实现,仿真结果也表明具有较高的性能.     

面向在线客服系统的调度算法研究

Different from traditional customer service systems, online customer service systems offer business services for multiple customers simultaneously, which makes the adaptation and scheduling between service providers and customers a big challenge. Based on the characteristics of online customer service, this paper proposes a scheduling model for online customer service systems. The scheduling model is composed of three constituents: a multi-priority customer queue, the states of the scheduling system and the transition relations between them, and the correspondence between scheduling strategies and states of the system. Its scheduling algorithm is designed. Experiments verify the rationality of the scheduling model and the effectiveness of the scheduling algorithm. In comparison to the operating customer service system, the algorithm can not only considerably reduce the average waiting time of customers, but also achieve load balancing among service providers, when guaranteeing high quality of services.     

提高卫星服务寿命的任务规划方法研究

基于组网卫星协同工作规划可提高复杂任务处理的基础上,本文探索降低规划风险,提高卫星服务寿命的卫星任务规划方法.从提高卫星服务寿命角度,建立用于描述资源使用期望的目标规划模型;建立卫星任务规划模型,在任务方案与资源使用中考虑了规划风险要素,并将资源使用目标模型引入到任务规划模型中,以期在规划中同时优化卫星服务寿命要素;基于邻域贪心扩展改善遗传禁忌求解算法,并运用分布并行技术提高工程实用性;利用STK提供基础仿真数据,对模型与算法进行了验证.     

MP or not MP: that is the question

It is well known that in the twentieth century, mathematical programming (MP) modeling and particularly linear programming (LP) modeling, even though strongly applied to combinatorial optimization, were not too successful when directed to scheduling problems. The purpose of this paper is to show that the field of successful applications of LP/MP modeling is still growing and includes also scheduling topics. We first focus on single machine scheduling. We consider a single machine scheduling model where a quadratic programming (QP) formulation handled by means of a QP solver is shown to be competitive with the state of the art approaches. Also, we discuss a single machine bicriterion scheduling problem and show that a standard LP formulation based on positional completion times performs reasonably well when handled by means of a LP solver. Then, we show how LP can be used to tighten bounds for approximation results in sequencing problems. Finally, we show how to enhance the complexity bounds of branch-and-reduce exact exponential algorithms by means of the so-called measure-and-conquer paradigm requiring always the solution of a specific MP model.