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.

Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability

This paper compares the quality and execution times of several algorithms for scheduling service based workflow applications with changeable service availability and parameters. A workflow is defined as an acyclic directed graph with nodes corresponding to tasks and edges to dependencies between tasks. For each task, one out of several available services needs to be chosen and scheduled to minimize the workflow execution time and keep the cost of service within the budget. During the execution of a workflow, some services may become unavailable, new ones may appear, and costs and execution times may change with a certain probability. Rescheduling is needed to obtain a better schedule. A solution is proposed on how integer linear programming can be used to solve this problem to obtain optimal solutions for smaller problems or suboptimal solutions for larger ones. It is compared side-by-side with GAIN, divide-and-conquer, and genetic algorithms for various probabilities of service unavailability or change in service parameters. The algorithms are implemented and subsequently tested in a real BeesyCluster environment.

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.

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.

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.

An optimal algorithm for a class of tardiness scheduling problem

Scheduling n independent tasks on m multiprocessors to minimize the total tardiness is a fundamental problem of deterministic scheduling theory. Bearing in mind this class of scheduling problem, a genetics based m P S K algorithm is proposed and an example is used to verify the high efficiency and stability of this algorithm.

The Dynamic Scheduling Model of Battlefield Rush-Repair Tasks

During the war,equipment is constantly being damaged with limited battlefield rush-repair time and power.Therefore,some military problems are presented in this paper.In order to get more fighting time for damaged equipment to participate in operation again as much as possible,three problems should be considered properly.The first problem is how to dynamically choose the most suitable damaged equipment for each repair group.The second one is how to divide tasks between different groups.The third one is how to determine execution sequence in the same group.A mathematical model is established to solve the dynamic battlefield rushrepair task scheduling problem(DBRTSP) in wartime.A variant genetic algorithm is designed to dynamically track the change of the optimal solution.A scheduling example is solved through Matlab.Results show that the proposed model is not only scientific and reasonable,but also convenient and efficient.

An Optimal Algorithm for a Class of Parallel Machines Scheduling Problem

This paper considers the parallel machines scheduling problem where jobs are subject to different release times. A constructive heuristic is first proposed to solve the problem in a modest amount of computer time. In general, the quality of the solutions provided by heuristics degrades with the increase of the probiem’s scale. Combined the global search ability of genetic algorithm, this paper proposed a hybrid heuristic to improve the quality of solutions further. The computational results show that the hybrid heuristic combines the advantages of heuristic and genetic algorithm effectively and can provide very good solutions to some large problems in a reasonable amount of computer time.

Implicit memory-based technique in solving dynamic scheduling problems through Response Surface Methodology–Part I Model and method

Purpose–This is the first part of a two-part paper.The purpose of this paper is to report on methods that use the Response Surface Methodology(RSM)to investigate an Evolutionary Algorithm(EA)and memory-based approach referred to as McBAR–the Mapping of Task IDs for Centroid-Based Adaptation with Random Immigrants.Some of the methods are useful for investigating the performance(solution-search abilities)of techniques(comprised of McBAR and other selected EAbased techniques)for solving some multi-objective dynamic resource-constrained project scheduling problems with time-varying number of tasks.Design/methodology/approach–The RSM is applied to:determine some EA parameters of the techniques,develop models of the performance of each technique,legitimize some algorithmic components of McBAR,manifest the relative performance of McBAR over the other techniques and determine the resiliency of McBAR against changes in the environment.Findings–The results of applying the methods are explored in the second part of this work.Originality/value–The models are composite and characterize an EA memory-based technique.Further,the resiliency of techniques is determined by applying Lagrange optimization that involves the models.

Implicit memory-based technique in solving dynamic scheduling problems through Response Surface Methodology–PartⅡExperiments and analysis

Purpose–This is the second part of a two-part paper.The purpose of this paper is to report the results on the application of the methods that use the Response Surface Methodology to investigate an evolutionary algorithm(EA)and memory-based approach referred to as McBAR–the Mapping of Task IDs for Centroid-Based Adaptation with Random Immigrants.Design/methodology/approach–The methods applied in this paper are fully explained in the first part.They are utilized to investigate the performances(ability to determine solutions to problems)of techniques composed of McBAR and some EA-based techniques for solving some multi-objective dynamic resource-constrained project scheduling problems with a variable number of tasks.Findings–The main results include the following:first,some algorithmic components of McBAR are legitimate;second,the performance of McBAR is generally superior to those of the other techniques after increase in the number of tasks in each of the above-mentioned problems;and third,McBAR has the most resilient performance among the techniques against changes in the environment that set the problems.Originality/value–This paper is novel for investigating the enumerated results.

Concurrent processes scheduling with scarce resources in small and medium enterprises

Scarce resources,precedence and non-determined time-lag are three constraints commonly found in small and medium manufacturing enterprises(SMEs),which are deemed to block the application of workflow management system(WfMS). To tackle this problem,a workflow scheduling approach is proposed based on timing workflow net(TWF-net) and genetic algorithm(GA). The workflow is modelled in a form of TWF-net in favour of process simulation and resource conflict checking. After simplifying and reconstructing the set of workflow instance,the conflict resolution problem is transformed into a resource-constrained project scheduling problem(RCPSP),which could be efficiently solved by a heuristic method,such as GA. Finally,problems of various sizes are utilized to test the performance of the proposed algorithm and to compare it with first-come-firstserved(FCFS) strategy. The evaluation demonstrates that the proposed method is an overwhelming and effective approach for scheduling the concurrent processes with precedence and resource constraints.

Design of task priority model and algorithm for imaging observation problem

In the imaging observation system, imaging task scheduling is an important topic. Most scholars study the imaging task scheduling from the perspective of static priority, and only a few from the perspective of dynamic priority. However,the priority of the imaging task is dynamic in actual engineering. To supplement the research on imaging observation, this paper proposes the task priority model, dynamic scheduling strategy and Heuristic algorithm. At first, this paper analyzes the relevant theoretical basis of imaging observation, decomposes the task priority into four parts, including target priority, imaging task priority, track, telemetry & control(TT&C)requirement priority and data transmission requirement priority, summarizes the attribute factors that affect the above four types of priority in detail, and designs the corresponding priority model. Then, this paper takes the emergency tasks scheduling problem as the background, proposes the dynamic scheduling strategy and heuristic algorithm. Finally, the task priority model,dynamic scheduling strategy and heuristic algorithm are verified by experiments.

Scheduling of Household Power Consumption for Step and Time-of-Use Tariff System

This paper proposes a hybrid optimization to solve the scheduling of household power consumption for Step and Time-of-Use (TOU) tariff system. The target function is the cost of electricity, and the optimization object is total instantaneous power within a billing period. The control variables are starting moments of each household appliance. The optimization procedure is divided into two stages. Firstly, the prerequisite for minimal cost is calculated through mathematical analysis and generalized function theory. Secondly, the solution is obtained by using a heuristic algorithm in which the result of the first stage is considered to reduce the searching space. And an evaluation methodology is deduced to evaluate the optimization. The computer simulation demonstrates that the proposed approach can reduce the cost of electricity evidently in the sense of probability. The approach shows great value for embedded applications.

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

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

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

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

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

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

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

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

考虑带宽和电力费用的数据中心工作流负载分配优化模型研究

针对数据中心处理工作流负载时产生的运行费用问题,首先,分析并建立了考虑带宽和电力费用的工作流负载分配模型优化数据中心运营商支付的经济成本。然后,针对优化模型的特点,设计了启发式算法求解最小运行费用和工作流子任务在各个数据中心的分配方案。最后,采用真实的工作流负载拓扑和参数设置进行算例分析,对比3种不同类型的工作流负载拓扑和常见的两种工作流负载分配方法,结果验证了综合考虑带宽流量费用和电力费用模型对降低数据中心总运行费用的作用。

带准备时间的异构并行机调度规则自动设计方法

以大规模定制化的家电行业生产为背景,将家电总装产线的投产排序决策抽象成为一类带准备时间的异构并行机动态调度问题。针对人工调度规则解决动态调度问题简单高效,但场景适应性弱的特点,引入了基于遗传规划(genetic programming,GP)的规则自动设计框架。首先,通过分析家电总装产线生产特征以及优化需求,以最小化平均拖期为优化目标,建立异构并行机调度模型;随后,针对问题特征,构建线体指派-工单排序规则对协同进化的改进型GP算法,并提取线体、工单的特征属性输入GP算法框架以自动设计调度规则。最后,基于某家电企业实际案例数据设计大量算例测试集,通过对比GP算法与人工设计规则在差异化工况场景的实验结果,验证GP算法有效性,并进一步分析了GP算法构造规则受不同生产环境参数的影响。