Rolling horizon scheduling algorithm for dynamic vehicle scheduling system

Dynamic exclusive pickup and delivery problem with time windows (DE-PDPTW), aspecial dynamic vehicle scheduling problem, is proposed. Its mathematical description is given andits static properties are analyzed, and then the problem is simplified asthe asymmetrical travelingsalesman problem with time windows. The rolling horizon scheduling algorithm (RHSA) to solve thisdynamic problem is proposed. By the rolling of time horizon, the RHSA can adapt to the problem'sdynamic change and reduce the computation time by dealing with only part of the customers in eachrolling time horizon. Then, its three factors, the current customer window, the scheduling of thecurrent customer window and the rolling strategy, are analyzed. The test results demonstrate theeffectiveness of the RHSA to solve the dynamic vehicle scheduling problem.

Dynamic and Integrated Load-Balancing Scheduling Algorithm for Cloud Data Centers

One of the challenging scheduling problems in Cloud data centers is to take the allocation and migration of reconfigurable virtual machines as well as the integrated features of hosting physical machines into consideration. We introduce a Dynamic and Integrated Resource Scheduling algorithm (DAIRS) for Cloud data centers. Unlike traditional load-balance scheduling algorithms which often consider only one factor such as the CPU load in physical servers, DAIRS treats CPU, memory and network bandwidth integrated for both physical machines and virtual machines. We develop integrated measurement for the total imbalance level of a Cloud datacenter as well as the average imbalance level of each server. Simulation results show that DAIRS has good performance with regard to total imbalance level, average imbalance level of each server, as well as overall running time.

Research of improving the dynamic scheduling algorithm in the CAN bus control networks

Currently, the article analyzes the CAN bus＇s rule of priority＇s arbitration bit by bit without destroy. It elicits the conclusion that if static priority based on the affirmatory system model is used, the lower priority＇s messages will be delayed considerably more, even some data will be lost when the bus＇s bandwidth is widely used. The scheduling cannot be modified neither during the system when static priority is used. The dynamic priority promoting method and the math model of SQSA and SQMA are presented; it analyzes the model＇s rate of taking in and sending out in large quantities, the largest delay, the problems and solutions when using SQMA. In the end, it is confirmed that the method of improving dynamic priority has good performances on the network rate of taking in and sending out in large quantities, the average delay, and the rate of network usage by emulational experiments.

EZDCP:A new static task scheduling algorithm with edge-zeroing based on dynamic critical paths

A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.

Dynamic Scheduling and Path Planning of Automated Guided Vehicles in Automatic Container Terminal

The uninterrupted operation of the quay crane(QC)ensures that the large container ship can depart port within laytime,which effectively reduces the handling cost for the container terminal and ship owners.The QC waiting caused by automated guided vehicles(AGVs)delay in the uncertain environment can be alleviated by dynamic scheduling optimization.A dynamic scheduling process is introduced in this paper to solve the AGV scheduling and path planning problems,in which the scheduling scheme determines the starting and ending nodes of paths,and the choice of paths between nodes affects the scheduling of subsequent AGVs.This work proposes a two-stage mixed integer optimization model to minimize the transportation cost of AGVs under the constraint of laytime.A dynamic optimization algorithm,including the improved rule-based heuristic algorithm and the integration of the Dijkstra algorithm and the Q-Learning algorithm,is designed to solve the optimal AGV scheduling and path schemes.A new conflict avoidance strategy based on graph theory is also proposed to reduce the probability of path conflicts between AGVs.Numerical experiments are conducted to demonstrate the effectiveness of the proposed model and algorithm over existing methods.

STUDY ON THE DYNAMIC SCHEDULING IN FMS REAL-TIME PRODUCTION ENVIRONMENT

A dynamic database based dynamic scheduling system is proposed.As the schedule is being preformed, the scheduling task data in the dynamic database is updated timely.Genetic algorithm (GA) is employed for generating optimised production plan quickly and easily in response to changes on the shop floor. The current status of the shop is considered while rescheduling, and new plan is used in conjunction with the existing schedule to improve the effeciency of flexble manufacturing systems. Simulation results demonstrate the effectiveness of the proposed system.

DYNAMIC ADVANCED PLANNING AND SCHEDULING WITH FROZEN INTERVAL FOR NEW ORDERS

A dynamic advanced planning and scheduling （DAPS） problem is addressed where new orders arrive on a continuous basis. A periodic policy with frozen interval is adopted to increase stability on the shop floor. A genetic algorithm is developed to find a schedule at each rescheduling point for both original orders and new orders that both production idle time and penalties on tardiness and earliness of orders are minimized. The proposed methodology is tested on a small example to illustrate the effect of the frozen interval. The results indicate that the suggested approach can improve the schedule stability while retaining efficiency.

Dynamic Resource Scheduling in Emergency Environment

Nowadays,emergency accidents could happen at any time.The accidents occur unpredictably and the accidents requirements are diversely.The accidents happen in a dynamic environment and the resource should be cooperative to solve the accidents.Most methods are focusing on minimizing the casualties and property losses in a static environment.However,they are lack in considering the dynamic and unpredictable event handling.In this paper,we propose a representative environmental model in representation of emergency and dynamic resource allocation model,and an adaptive mathematical model based on Genetic Algorithm(GA)to generate an optimal set of solution domain.The experimental results show that the proposed algorithm can get a set of better candidate solutions.

Hierarchical Disturbance Propagation Mechanism and Improved Contract Net Protocol for Satellite TT&C Resource Dynamic Scheduling

The practical engineering of satellite tracking telemetry and command(TT&C)is often disturbed by unpredictable external factors,including the temporary rise in a significant quantity of satellite TT&C tasks,temporary failures and failures of some TT&C resources,and so on.To improve the adaptability and robustness of satellite TT&C systems when faced with uncertain dynamic disturbances,a hierarchical disturbance propagation mechanism and an improved contract network dynamic scheduling method for satellite TT&C resources were designed to address the dynamic scheduling problem of satellite TT&C resources.Firstly,the characteristics of the dynamic scheduling problem of satellite TT&C resources are analyzed,and a mathematical model is established with the weighted optimization objectives of maximizing the revenue from task completion and minimizing the degree of plan disturbance.Then,a bottom-up distributed dynamic collaborative scheduling framework for satellite TT&C resources is proposed,which includes a task layer,a resource layer,a central internal collaboration layer,and a central external collaboration layer.Dynamic disturbances are propagated layer by layer from the task layer to the central external collaboration layer in a bottom-up manner,using efficient heuristic strategies in the task layer and the resource layer,respectively.We use improved contract network algorithms in the center internal collaboration layer and the center external collaboration layer,the original scheduling plan is quickly adjusted to minimize the impact of disturbances while effectively completing dynamic task requirements.Finally,a large number of simulation experiments were carried out and compared with various comparative algorithms.The results show that the proposed algorithm can effectively improve the solution effect of satellite TT&C resource dynamic scheduling problems,and has good application prospects.

Design and Implementation of Dynamic High-Speed Switches in Super Base Station Architectures

Novel centralized base station architectures integrating computation and communication functionalities have become important for the development of future mobile communication networks.Therefore,the development of dynamic high-speed interconnections between baseband units(BBUs)and remote radio heads(RRHs)is vital in centralized base station design.Herein,dynamic high-speed switches(HSSs)connecting BBUs and RRHs were designed for a centralized base station architecture.We analyzed the characteristics of actual traffic and introduced a switch traffic model suitable for the super base station architecture.Then,we proposed a data-priority-aware(DPA)scheduling algorithm based on the traffic model.Lastly,we developed the dynamic HSS model based on the OPNET platform and the prototype based on FPGA.Our results show that the DPA achieves close to 100%throughput with lower latency and provides better run-time complexity than iOCF and HE-iSLIP,thereby demonstrating that the proposed switch system can be adopted in centralized base station architectures.

A Multi-Customer Supply Chain Scheduling with Subcontracting Option on a Single Machine

This paper studies the cost problem caused by the activity of the work-piece in the supply chain. The objective function is to find an optimal ordering that minimizes the total cost of production, transportation and subcontracting. This paper presents a dynamic programming algorithm for the corresponding sorting problem, and finally demonstrates the feasibility of the algorithm through an example.

基于生产数据的混合流水车间动态调度方法研究

在智能制造背景下,物联网等信息技术为制造系统积累了大量数据,同时人工智能等先进方法为车间数据分析和实时控制提供了有效手段。因此,针对不相关并行机混合流水车间调度问题,提出了一种基于生产数据的动态调度方法,以实现订单完工时间最小化。首先以高质量调度方案为基础,从中提取生产特征和调度规则完成样本构建。其次使用Relief F算法过滤冗余生产特征,获得用于训练和预测的调度样本。然后采用融合鲸鱼优化算法的概率神经网络作为调度模型,实现基于调度样本的训练和预测过程。最后,实验结果表明,所提方法具有良好的特征选择能力和较高的预测精度,与其他实时调度方法相比具有更加优越的性能,可以有效地根据车间实时状态指导制造执行过程。

基于规则与Q学习的作业车间动态调度算法

为了在特定的作业条件下找到最优调度规则,提高调度规则在不确定动态条件下的自适应、自寻优能力,提出一种调度规则与Q学习算法集成的作业车间动态调度算法。考虑车间中作业随机到达的动态情况,以最小化最大延迟时间为调度目标,在Q学习框架下设计了新的状态特征、奖励机制以及以Boltzmann采样函数为主体的搜索策略,提高了算法探索和利用规则的能力;以最短加工时间优先和最早交货期等经典调度规则构成动作集,继承了调度规则的可解释性,使智能体能实时处理随机到达的作业任务,通过持续学习和迭代更新获得不同作业场景下的最优调度规则。仿真研究和对比测试验证了所提算法的优越性。

混合遗传变邻域搜索算法求解柔性车间调度问题

针对考虑生产成本的柔性作业车间调度问题(flow job shop scheduling problem, FJSP),以完工时间与加工成本为优化指标,提出一种求解FJSP的混合遗传变邻域搜索算法。根据个体适应度对种群分割,结合自适应交叉概率改进子代种群产生方式;设计两种邻域结构增强算法的局部搜索能力;提出一种基于动态交叉变异概率的优化算法流程提高求解效率。运用提出的算法求解基准实例与实际问题测试,验证了算法的有效性。

动态上下料路径下柔性产品族生产调度研究

针对汽车零部件柔性产品族制造单元考虑工序间动态上下料路径与时间的生产调度求解问题,文中提出一种用于动态上下料路径柔性作业调度问题优化的自适应离散差分进化算法。通过自适应缩放参数实现收敛速度提升,构建基于矩阵映射的离散编码规则实现变异操作离散化及基于机器人实际运动路径的动态调度解码。通过对某平台化车型架构的转向器壳体加工单元实例分析并验证了算法有效性及优越性。

基于时间窗的机场地面保障车辆动态调度

机场各类地面资源的优化配置是机场场面运行优化的核心问题,而机场地面保障任务的调度是其中的关键一环。针对机场地面保障车辆的调度问题,考虑航班延误、提前等情况,构建了双阶段机场地面保障车辆调度模型,并设计双阶段启发式算法进行求解;基于中国某大型机场的实际运行数据,以清水车和食品车调度为例分别进行仿真实验。结果表明:对比先到先服务策略,清水车行驶总距离减少55.31%,食品车行驶总距离减少47.38%;对比传统遗传算法,清水车行驶总距离减少19.31%,食品车行驶总距离减少22.93%;动态调整后,清水车新增总行驶距离1.2%,食品车总行驶距离新增3.2%,均在可接受范围之内。可见,双阶段机场地面保障车辆调度模型能提高大型机场场面运行效率,为机场航班实际地面保障任务调度提供理论依据和决策支持。

基于“分类-调度”优化的应急物资动态调度-重调度算法

由于灾情的不确定性和信息延迟,应急救灾物资配送与车辆调度常面临配送过程中出现需求点信息动态变化的复杂环境,如何在动态变化的环境下快速反应,准确高效地实现应急物资重调度显得尤其重要。针对需求点信息动态变化的复杂环境,建立一个应急物资动态调度模型,并提出基于“分类-调度”的动态调度算法,通过k-means分类将原复杂问题降解为多个简单TSP问题,随着需求点信息的变化可动态调整分类,以实现快速重调度;设计相应的路线调整策略以保证方案的可行性;最后利用遗传算法求解。数值试验结果证明了所提方法的有效性。

融合蚁群算法框架下区域资源的动态调度模型

针对目前电力作业人力资源调度主要依赖于人工经验的现状,文中提出了基于改进蚁群算法的区域资源动态调度模型。该模型以花费总时间与总成本最小为优化目标,考虑了任务的资源需求、先后顺序等方面的约束条件。同时,结合区域资源动态调度模型的特性,对传统蚁群算法进行了改进设计,提出了优化的编码解码方法、蚁群动态更新机制及2-opt局部搜索方法等策略。算例分析结果表明,所提改进蚁群算法相比于传统蚁群算法具有更快的收敛速度和更高的计算准确度。在实际电力作业调度中,对比传统蚁群算法,所设计模型能够减少总时间约12%,降低总成本约10%。

带有动态到达工件的分布式柔性作业车间调度问题研究

分布式柔性作业车间调度是生产调度的1个重要分支,工件的动态到达作为实际生产中的1种常见扰动情况,进一步增加了作业车间调度问题的复杂性和不确定性。针对带有工件动态到达的分布式柔性作业车间调度问题(DA-DFJSP),提出1种分批调度策略,将原本的动态调度问题转化成一系列连续调度区间上的静态调度问题,构建以最大完工时间为优化目标的混合整数规划模型;在此基础上,结合问题特征采用批次、工厂、工序、机器的4层染色体编码及快速贪婪搜索插入的解码方式改进遗传算法,同时引入多种交叉、变异算子来增强染色体的多样性;最后,基于FJSP标准算例构建DA-DFJSP测试算例进行仿真对比实验,验证所提策略和改进算法的求解优势。结果表明:相较于传统的重调度策略和改进前的遗传算法,采用分批调度策略和改进的遗传算法(IGA)所求调度方案具有更短的完工周期、更均匀的工厂加工负荷及更高的设备工作效率,IGA与分批调度策略之间有高度的契合性,能够有效提升生产效率。

Dynamic Measurement of Task Scheduling Algorithm in Multi-Processor System

It is important to evaluate function behaviors and performance features of task scheduling algorithm in the multi-processor system.A novel dynamic measurement method(DMM)was proposed to measure the task scheduling algorithm’s correctness and dependability.In a multi-processor system,task scheduling problem is represented by a combinatorial evaluation model,interactive Markov chain(IMC),and solution space of the algorithm with time and probability metrics is described by action-based continuous stochastic logic(aCSL).DMM derives a path by logging runtime scheduling actions and corresponding times.Through judging whether the derived path can be received by task scheduling IMC model,DMM analyses the correctness of algorithm.Through judging whether the actual values satisfy label function of the initial state,DMM analyses the dependability of algorithm.The simulation shows that DMM can effectively characterize the function behaviors and performance features of task scheduling algorithm.