基于混合遗传算法的作业车间调度问题的研究与仿真

作业车间调度问题(JSP)是一类典型的NP-hard问题,遗传算法(GA)由于其隐合并行性和全局解空间搜索两大优点而成为解决JSP问题的常用工具.但是,由于JSP问题本身的特点,普通遗传算法难以在解此类问题时得到满意解,最突出的问题就是过早收敛于某一局部最优解,使算法效率降低.在此基础上,将遗传算法和模拟退火算法相结合,提出了一种基于遗传和模拟退火的混合算法,该算法将模拟退火算法赋予搜索过程时变性融入其中,具有明显的概率跳跃性,并选取了典型问题进行分析和仿真研究.仿真结果表明,与传统的遗传算法相比该方法是行之有效的.     

A genetic fuzzy agent using ontology model for meeting scheduling system

A Genetic Fuzzy Agent (GFA) using the ontology model for Meeting Scheduling System (MSS) is presented in this paper. The ontology model includes the Fuzzy Meeting Scheduling Ontology (FMSO) and the Fuzzy Personal Ontology (FPO) that can support to construct the knowledge base of the GFA. The FMSO is utilized to record and describe the meeting scheduling domain knowledge for the GFA. In addition, we implement a FMSO editor for generating the Web Ontology Language, OWL, that will be utilized by the GFA. Furthermore, the GFA will infer the suitable meeting time slots based on the ontology model. Moreover, it also adjusts the FMSO and FPO based on the results of the genetic learning mechanism for the next meeting. The experimental results show that our approach can effectively work for MSS.     

Online algorithms for scheduling two parallel machines with a single server

We consider an online scheduling problem on two identical parallel machines with a single server. Jobs arrive one by one and each job has to be loaded by the server before being processed on one of the machines, and unloaded immediately by the server after its processing. Both loading and unloading times are equal to one time unit. The goal is to minimize the makespan. For the variant of the problem involving both loading and unloading operations, we present an online algorithm with competitive ratio of 5/3. For the variant with loading operation only, we show that the competitive ratio of list scheduling is at least 8/5 and provide an improved online algorithm with competitive ratio of 11/7. Finally, we discuss the lower bounds for these problems. We show that both variants have a lower bound of 3/2. Furthermore, we show that the lower bound of the first variant is at least 8/5 if the online algorithm satisfies a certain constraint.     

选煤厂信息物理系统任务调度研究

建立了选煤厂信息物理系统模型,将动态联盟思想引入选煤厂信息物理系统任务调度中,并提出了一种基于改进离散粒子群优化算法的选煤厂信息物理系统任务调度算法。该算法首先采用离散粒子群优化算法进行全局寻优,然后采用禁忌搜索算法进行局部搜索,求得全局最优解。仿真结果表明,该算法提高了任务调度的收敛速度、精度以及处理器的平均利用率。     

基于Hadoop YARN的TensorFlow GPU集群的调度扩展

本文研究并实现了大数据平台 Hadoop YARN 与深度学习框架 TensorFlow 的结合。通过对 DRF 算法的扩展,使得 Hadoop YARN 在原先支持 CPU 和内存的基础上,可以对 GPU 资源进行管理和调度。通过 YARN 的应用接口,把 TensorFlow 封装成了 YARN 的应用程序之一,把原来的分布式程序在多节点手动分发启动改为了在单节点自动分发启动,单机版不变。本文设计了多组实验对 YARN+TensorFlow 进行了多方位的测试,实验结果表明 YARN 和 TensorFlow 相结合相比原生 TensorFlow 程序具有相似的加速比,可以满足单系统多用户对 GPU 资源的使用,有效提高 GPU 资源的使用效率和编程人员的工作效率,增加系统的复用率。     

面向移动设备的温度感知的任务调度算法

由于志愿者分布式计算可以为计算量庞大的科研项目提供足够的计算能力,甚至比超级计算机的计算能力还要强大,因此,志愿者分布式计算技术受到了很多研究人员的关注,很多不同的志愿者分布式计算架构被广泛应用。以往的很多志愿者分布式计算架构通常考虑的志愿者主机是PC电脑,或者单纯地把移动设备当作PC电脑一样进行处理。由于移动设备的很多特性跟PC电脑存在着很大的差异,所以很多时候这些志愿者分布式计算架构并不能高效地处理同时拥有PC电脑和移动设备志愿者的志愿计算项目。针对志愿者分布式计算系统上两个主流的志愿者分布式计算任务调度方法——迭代计算的任务调度算法和先来先服务的调度算法FCFS在处理移动设备志愿者计算上存在着的不足,为了提高志愿者分布式计算平台的执行效率,提出了一个面向移动设备的温度感知的任务调度算法TATSA。实验结果表明,TATSA比主流的任务调度算法ISA和FCFS在移动设备志愿者计算时效率明显更高。     

Capacity planning for packaging industry

This paper presents a capacity planning system (CPS) to generate a feasible production schedule, improve production efficiency, and avoid overcapacity for the packaging industry. CPS applies the concept of workload leveling and finite capacity planning to assign orders to production lines by considering several production characteristics such as drying time, quantity splitting owing to the cutting pattern of the product type, and the variability of machine capacity threshold. CPS consists of five modules, namely, order treatment module (OTM), order priority module (OPM), lot release module (LRM), workload accumulation module (WAM), and workload balance module (WBM). The experimental design is used to evaluate the effectiveness and efficiency of the proposed CPS with five factors (number of orders, order size, order size variance, order priority, and balance policy) with various levels and three response variables, namely, machine workload balance, order due date deviation, and lateness. Moreover, this result extends into finding the best settings of order priority and balance policy to generate the best favorable responses under the given three environment factors.     

A multi-objective evolutionary algorithm guided by directed search for dynamic scheduling

This paper considers dynamic multi-objective machine scheduling problems in response to continuous arrival of new jobs, under the assumption that jobs can be rejected and job processing time is controllable. The operational cost and the cost of deviation from the baseline schedule need to be optimized simultaneously. To solve these dynamic scheduling problems, a directed search strategy (DSS) is introduced into the elitist non-dominated sorting genetic algorithm (NSGA-II) to enhance its capability of tracking changing optimums while maintaining fast convergence. The DSS consists of a population re-initialization mechanism (PRM) to be adopted upon the arrival of new jobs and an offspring generation mechanism (OGM) during evolutionary optimization. PRM re-initializes the population by repairing the non-dominated solutions obtained before the disturbances occur, modifying randomly generated solutions according to the structural properties, as well as randomly generating solutions. OGM generates offspring individuals by fine-tuning a few randomly selected individuals in the parent population, employing intermediate crossover in combination with Gaussian mutations to generate offspring, and using intermediate crossover together with a differential evolution based mutation operator. Both PRM and OGM aim to strike a good balance between exploration and exploitation in solving the dynamic multi-objective scheduling problem. Comparative studies are performed on a variety of problem instances of different sizes and with different changing dynamics. Experimental results demonstrate that the proposed DSS is effective in handling the dynamic scheduling problems under investigation.     

Home health care routing and scheduling: A review

In home health care (HHC) operations, nurses are scheduled and routed to perform various services at clients' homes. As this often requires a combination of vehicle routing and scheduling approaches, resulting optimization problems are complex and, hence, of high interest to stakeholders such as researchers, practitioners and policy-makers. With demand for HHC expected to increase substantially, future work is essential to decrease costs and to guarantee service quality. In this review, we provide a comprehensive overview of current work in the field of HHC routing and scheduling with a focus on considered problem settings. Recent advances in HHC optimization are highlighted and future research directions discussed.