Framework and deployment of a cloud-based advanced planning and scheduling system

Many small and medium-sized manufacturing enterprises (SMEs) have already implemented enterprise resource planning (ERP) and manufacturing execution system (MES) and began to start the journey of cloud manufacturing; however, the high cost of hardware and software investment, implementation, and maintenance usually hinder SMEs from adopting an advanced planning and scheduling (APS) system. This paper aims to develop a cloud-based APS (C-APS) system framework, the service structure, and approach of deploying the C-APS system in a public cloud infrastructure platform and service provider or hybrid cloud platform. The package diagram is proposed for building the C-APS system's virtual factory model to improve modeling efficiency and data stability. The C-APS system is a cloud-based and object-oriented software; its simulation-based scheduling engine can generate the significant production and operations schedule, and has the characteristics of on-demand self-service, quickly expanding and adjusting to the virtual plant model. The C-APS system's application in a leading automotive part assembly company's printed circuit board production scheduling shows that the input planning data model is easy to maintain. The scheduling quality is high; the computing time is short and acceptable for practical application.     

APS系统中基于改进的遗传算法的分布式排产研究

探讨了在分布式生产模式下,解决生产排程问题的新技术——APS（Advanced Planning and Scheduling）系统。系统利用PowerBuilder作为开发工具。实践证明,在APS的计划模型下,改进的遗传算法在解决分布式生产排程问题上具有良好的算法性能,并在某大型制药厂的实施中取得成功。     

一种用于异构环境中任务调度的高效算法

在异构计算环境中,有效的任务调度对于获得高性能是十分重要的。现在虽然已经有许多异构处理器调度算法,但它们或者不具有良好的效果,或者算法代价太高。提出了一种新的基于表的调度算法APS。APS利用有向无环图来计算任务优先级,并采用基于调度的策略分配任务到不同处理器,以获得任务最少完工时间。将APS和LMT,HEFT,CPOP算法做比较之后得出：在大多数情况下APS算法都能获得更好性能。     

APS 9: an improved adaptive population-based simplex method for real-world engineering optimization problems

The adaptive population-based simplex (APS) algorithm is a recently-proposed optimization method for solving continuous optimization problems. In this paper, a new variant of APS, referred to as APS 9, is proposed to solve engineering optimization problems. APS 9 still follows the main structure of APS where three strategies (i.e., reflection, contraction and local search) can be used to improve the population of solutions. However, the three strategies have been significantly modified and the rules for applying them have been revised. A stagnation detection mechanism and duplicates removal step have been added. The proposed method is compared with the winners of the IEEE CEC 2005 and CEC 2011 competitions on the 22 CEC 2011 problems. The results show the superiority of APS 9 compared to the other two methods. Moreover, APS 9 has been compared with two recent optimization methods on the same test bed. The limitations of the CEC 2011 competition are also discussed and new rules that are more engineering-friendly are proposed.     

Mining SOTs and dispatching rules from RFID-enabled real-time shopfloor production data

Radio frequency identification (RFID) has been widely used in manufacturing field and created a ubiquitous production environment, where advanced production planning and scheduling (APS) might be enabled. Within such environment, APS usually requires standard operation times (SOTs) and dispatching rules which have been obtained from time studies or based on past experiences. Wide variations exist and frequently cause serious discrepancies in executing plans and schedules. This paper proposes a data mining approach to estimate realistic SOTs and unknown dispatching rules from RFID-enabled shopfloor production data. The approach is evaluated by real-world data from a collaborative company which has been used RFID technology for supporting its shopfloor production over seven years. The key impact factors on SOTs are quantitatively examined. A reference table with the mined precise and practical SOTs is established for typical operations and suitable dispatching rules are labled as managerial implicities, aiming at improving the quality and stability of production plans and schedules.     

Time windows and constraint programming to deal with strong restriction in the due date of productive systems

The APS (Advanced Planning and Scheduling) systems are widely used by companies; however, the traditional APS systems cannot deal with problems whose the due date is a strong restriction. The problem derives from the way companies use their scheduling heuristics. This paper addresses this problem by using the concept of time windows with the constraint programming mechanism. A procedure is shown to generate the time windows and how they can be used for the APS systems. The APS heuristic approach that uses the concepts of time windows with constraint programming is introduced to solve problems for which the due date is a strong restriction. These heuristics, with tasks allocation either at the beginning or at the end of the task time window, eliminate the need for a priority scheme. To illustrate the advantage of the proposal, some examples are presented.     

Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm

Most flexible job shop scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines may be unavailable due to maintenances, pre-schedules and so on. In this paper, we study the flexible job shop scheduling problem with availability constraints. The availability constraints are non-fixed in that the completion time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure. We then propose a hybrid genetic algorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints (fJSP-nfa). The genetic algorithm uses an innovative representation method and applies genetic operations in phenotype space in order to enhance the inheritability. We also define two kinds of neighbourhood for the problem based on the concept of critical path. A local search procedure is then integrated under the framework of the genetic algorithm. Representative flexible job shop scheduling benchmark problems and fJSP-nfa problems are solved in order to test the effectiveness and efficiency of the suggested methodology. Received: June 2005 /Accepted: December 2005     

Implizite Determinierung von Plan-Belegungszeiten

Correct standard times are needed for logistic operating curves, manufacturing planning and control systems and Advanced Planning Systems (APS) for scheduling, lot-sizing and sequencing. This paper presents a model for calculation of standard times based on the knowledge of the total busy time of a work center and the produced number of items in a fixed time period. The developed method requires little effort in comparison to other methods such as Work-Factor or time observation. It can regularly determine standard times using current confirmation data.     

A note on “the capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

Gupta and Magnusson [The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times. Computers and Operations Research 2005;32(4):727–47] develop a model for the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence dependent setup times and setup costs, incorporating all the usual features of setup carryovers. In this note we show that this model does not avoid disconnected subtours. A new set of constraints is added to the model to provide an exact formulation for this problem.     

面向MES的炼钢-连铸协同调度系统

针对某大型钢铁联合企业炼钢．连铸主辅设备协同调度的难题,采用基于“数据、模型、知识、人机交互”四维一体的调度方法,提出了冶金MES中炼钢．连铸协同调度系统的设计原则,系统结构和功能。研发了炼钢．连铸生产调度、钢包优化配备、行车和台车协同调度系统。实际数据模拟效果良好,验证了炼钢．连铸协同调度系统的结构和方法的可行性,并受到现场调度专家的好评。     

基于蚁群——遗传混合算法的高级计划与排产系统应用研究

生产管理系统是制造业中最为复杂的系统之一,高级计划与排产(Advanced Planning and Scheduling以下简称APS)是其重点与难点。由于生产的复杂性与不确定性,当前企业的生产计划编制方法虽多但效果不尽人意,特别是中小企业的现行生产计划与排产系统尤是如此。本文以江门某塑胶丝花行业为背景,以生产计划编制为研究对象,以计划编制的优化为主要内容,结合蚁群算法、遗传算法及其混合应用等算法理论与多种数学及智能信息技术方法,对建立一个能有效提高企业生产计划编制水平的APS系统应用进行了研究。     

基于蚁群——遗传混合算法的高级计划与排产系统应用研究

生产管理系统是制造业中最为复杂的系统之一，高级计划与排产（Advanced Planning and Scheduling以下简称APS）是其重点与难点。由于生产的复杂性与不确定性，当前企业的生产计划编制方法虽多但效果不尽人意．特别是中小企业的现行生产计划与排产系统尤是如此。本文以江门某塑胶丝花行业为背景，以生产计划编制为研究对象．以计划编制的优化为主要内容．结合蚁群算法、遗传算法及其混合应用等算法理论与多种数学及智能信息技术方法，对建立一个能有效提高企业生产计划编制水平的APS系统应用进行了研究。     

Project-driven planning and scheduling support for virtual manufacturing

The paper addresses the issue of decision-making support for small and medium-size enterprises operating within a virtual project-driven enterprise environment. The problem considered here can be defined in terms of finding a feasible schedule that satisfies the constraints imposed by the work-order duration, the price, and the time-constrained resource availability. The problem belongs to the class of multi-mode case problems of project scheduling, where finding a feasible solution is NP-hard. A heuristic method for process planning and scheduling is proposed. The method is based on a critical path approach and the branch and bound search scheme. It has been implemented in a web-enabled interactive software package, and is illustrated using the example of a virtual construction enterprise. Received: February 2005 / Accepted: January 2006     

Crew pairing optimization by a genetic algorithm with unexpressed genes

We propose a genetic algorithm to solve the pairing optimization problem for subway crew scheduling. Our genetic algorithm employs new crossover and mutation operators specially designed to work with the chromosomes of set-oriented representation. To enhance the efficiency of the search with the newly designed genetic operators, we let a chromosome consist of an expressed part and an unexpressed part. While the genes in both parts evolve, only the genes in the expressed part are used when an individual is evaluated. The purpose of the unexpressed part is to preserve information susceptible to be lost by the application of genetic operators, and thus to maintain the diversity of the search. Experiments with real-world data have shown that our genetic algorithm outperforms other local search methods such as simulated annealing and tabu search. Received: June 2005/Accepted: December 2005     

数据驱动的多星任务网络预测调度算法

多星任务调度是具有NP-hard特性的优化问题,随着卫星资源规模和任务需求规模的双重增长,传统调度方法求解效率不高.在轨卫星在常年运行过程中积累了丰富的调度数据.针对大规模多星任务调度场景,建立多星多波束任务调度模型,并提出数据驱动的多星任务网络预测调度算法对其求解.以分割的思想,实现多星场景下任务可调度性预测.从历史调度数据中,提取设定的3个静态特征和5个动态特征,构建并训练预测网络,预测任务被不同卫星完成的概率,并以冲突避免、负载均衡等为原则,得到初始任务和资源卫星的分配方案.进一步设计双链结构的进化算法,以双链编码形式表征上述关系,配合设计的交叉、修复等进化算子,优化初始方案中的任务序列与资源分配关系,输出最终任务调度方案.仿真结果表明,与改进蚁群算法、混合遗传算法和数据驱动并行调度算法相比,所提出算法在运行时间、方案收益和卫星负载均衡3方面均有较好的表现.     

数据中心网络流量调度的研究进展与趋势

近年来,流量调度已经发展成为网络领域的热点研究问题.该问题主要决定何时以及以多大速率传输网络中的每条数据流,其对网络性能和应用性能都具有十分重要的影响.然而,在托管着许多大规模互联网应用的数据中心中,流量调度问题正面临着流量矩阵多变、流量种类混杂、以及流量突发等与流量模型相关的挑战.此外,随着数据中心规模的不断壮大,流量调度问题还面临着网络带宽动态化、网络拥塞随机化、以及网络目标多样化等与网络模型相关的挑战.为了进一步提升对数据中心流量调度的关注和理解,推动流调度技术在实际应用中的不断发展,本文分别从调度目标、调度方式和调度对象这三个维度对数据中心网络流调度的相关研究工作进行了分析和对比,并概括出如下结论:现有研究主要以分布式、集中式或混合式的调度方式对数据中心内、数据中心间或数据中心与用户间的流进行高效地调度,从而达到带宽保障、时限保障、最小化流完成时间、最小化Coflow完成时间、公平性保证、最小化流传输成本等目标.本文最后还指出了四个数据中心流调度的未来发展方向,并相应提出尚未解决的研究问题.     

A new ILS algorithm for parallel machine scheduling problems

This paper addresses the non-preemptive scheduling problem of scheduling jobs on identical parallel machines to minimize the maximum completion time or makespan. The problem has been proved to be NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new methodology to obtain near-optimal solutions. We formulate the problem as an integer programming and then propose a new iterated local search (ILS) algorithm based on a variable number of cyclic exchanges to solve it. The properties of the solutions are derived and the results are used to improve the computational efficiency of our algorithm. Computational experiments show that the cyclic exchange neighborhood embedded in an iterated local search framework is effective for solving the scheduling problems with up to 1000 jobs and 40 machines within a reasonable amount of computation time. Received: April 2005 / Accepted: January 2006     

智能交通动态调度优化模型与评价方法

为了降低大城市市民出行成本,缓解公交企业运力压力,提出一种智能交通出行OD(Origin Destination,出行地和目的地)的公交调度优化算法,以公交出行OD客流预测和计划排班发车时间间隔为出发点,运用公交出行OD客流推导理论,构建智能交通出行OD的公交调度优化模型。通过获取个人OD数据,利用单条线路公交OD方法,实现全市公交OD矩阵推算。根据全市公交出行OD推算结果,求解公交调度模型,解决智能交通调度多目标规划和公交线网优化问题。通过仿真模拟试验,分析智能公交排班计划评价指标,计算车辆营运效率占比:自动排班仿真数据为79%,实际运营数据为73%;统计车辆高峰时段与全天营运车次占比:自动排班仿真数据为36.75%,实际运营数据为37.37%,满足智能公交计划排班评价指标的要求,实例证明模型和算法具有实用性和可靠性。     

关于离散事件系统异步仿真中时钟管理机制的理论探讨

介绍了一种新的离散事件系统异步仿真方法,该方法完全摆脱了事件表数据结构,各过程之间没有共享变量,也没有一个单独的过程来处理信息的传递和过程的调度,过程之间的通信由信息驱动,它不仅克服了集中式仿真中由全局时钟控制可能造成的系统瓶颈问题,而且也避免了死锁问题。