A holonic approach to dynamic manufacturing scheduling

Manufacturing scheduling is a complex combinatorial problem, particularly in distributed and dynamic environments. This paper presents a holonic approach to manufacturing scheduling, where the scheduling functions are distributed by several entities, combining their calculation power and local optimization capability. In this scheduling and control approach, the objective is to achieve fast and dynamic re-scheduling using a scheduling mechanism that evolves dynamically to combine centralized and distributed strategies, improving its responsiveness to emergence, instead of the complex and optimized scheduling algorithms found in traditional approaches.     

Study on shop floor control system in semiconductor fabrication by self-organizing map-based intelligent multi-controller

To confirm semiconductor wafer fabrication (FAB) operating characteristics, the scheduling decisions of shop floor control systems (SFCS) must develop a multiple scheduling rules (MSRs) approach in FABs. However, if a classical machine learning approach is used, an SFCS in FABs knowledge base (KB) can be developed by using the appropriate MSR strategy (this method is called an intelligent multi-controller in this study) as obtained from training examples. A classical machine learning approach main disadvantage is that the classes (scheduling decision variables) to which training examples are assigned must be pre-defined. This process becomes an intolerably time-consuming task. In addition, although the best decision rule can be determined for each scheduling decision variable, the combination of all the decision rules may not simultaneously satisfy the global objective function. To address these issues, this study proposes an intelligent multi-controller that incorporates three main mechanisms: (1) a simulation-based training example generation mechanism, (2) a data preprocessing mechanism, and (3) a self-organizing map (SOM)-based MSRs selection mechanism. These mechanisms can overcome the long training time problem of the classical machine learning approach in the training examples generation phase. Under various production performance criteria over a long period, the proposed intelligent multi-controller approach yields better system performance than fixed decision scheduling rules for each of the decision variables at the start of each production interval.     

A comparison of machine-learning algorithms for dynamic scheduling of flexible manufacturing systems

Dispatching rules are frequently used to schedule jobs in flexible manufacturing systems (FMSs) dynamically. A drawback, however, to using dispatching rules is that their performance is dependent on the state of the system, but no single rule exists that is superior to all the others for all the possible states the system might be in. This drawback would be eliminated if the best rule for each particular situation could be used. To do this, this paper presents a scheduling approach that employs machine learning. Using this latter technique, and by analysing the earlier performance of the system, ‘scheduling knowledge’ is obtained whereby the right dispatching rule at each particular moment can be determined. Three different types of machine-learning algorithms will be used and compared in the paper to obtain ‘scheduling knowledge’: inductive learning, backpropagation neural networks, and case-based reasoning (CBR). A module that generates new control attributes allowing better identification of the manufacturing system's state at any particular moment in time is also designed in order to improve the ‘scheduling knowledge’ that is obtained. Simulation results indicate that the proposed approach produces significant performance improvements over existing dispatching rules.     

Dispatching rule selection using artificial neural networks for dynamic planning and scheduling

To schedule a job shop, the first task is to select an appropriate scheduling algorithm or rule. Because of the complexity of scheduling problems, no general algorithm sufficient for solving all scheduling problems has yet been developed. Most job-shop scheduling systems offer alternative algorithms for different situations, and experienced human schedulers are needed to select the best dispatching rule in these systems. This paper proposes a new algorithm for job-shop scheduling problems. This algorithm consists of three stages. First, computer simulation techniques are used to evaluate the efficiency of heuristic rules in different scheduling situations. Second, the simulation results are used to train a neural network in order to capture the knowledge which can be used to select the most efficient heuristic rule for each scheduling situation. Finally, the trained neural network is used as a dispatching rule selector in the real-time scheduling process. Research results have shown great potential in using a neural network to replace human schedulers in selecting an appropriate approach for real-time scheduling. This research is part of an ongoing project of developing a real-time planning and scheduling system.     

Learning-based scheduling of flexible manufacturing systems using case-based reasoning

A common method of dynamically scheduling jobs in Flexible Manufacturing Systems (FMSs) is to employ dispatching rules. However, the problem associated with this method is that the performance of the rules depends on the state of the system, but there is no rule that is superior to all the others for all the possible states the system might be in. It would therefore be highly desirable to employ the most suitable rule for each particular situation. To achieve this, this paper presents a scheduling approach that uses Case-Based Reasoning (CBR), which analyzes the system's previous performance and acquires "scheduling knowledge," which determines the most suitable dispatching rule at each particular moment in time. Simulation results indicate that the proposed approach produces significant performance improvements over existing dispatching rules.     

Adaptive pre-task assignment scheduling strategy for heterogeneous distributed raytracing system

One of the main obstacles in obtaining high performance from heterogeneous distributed computing (HDC) system is the inevitable communication overhead. This occurs when tasks executing on different computing nodes exchange data or the assigned sub-task size is very small. In this paper, we present adaptive pre-task assignment (APA) strategy for heterogeneous distributed raytracing system. In this strategy, the master assigns pre-task to the each node. The size of sub-task for each node is proportional to the node’s performance. One of the main features of this strategy is that it reduces the inter-processes communication, the cost overhead of the node’s idle time and load imbalance, which normally occurs in traditional runtime task scheduling (RTS) strategies. Performances of the RTS and APA strategies are evaluated on manager/master and workers model of HDC system. The experimental results of our proposed (APA) strategy have shown a significant improvement in the performance over RTS strategy.     

一类基于多Agent和分布式规则的敏捷生产调度

Agent范例为解决制造系统的敏捷生产调度问题提供了一条新途径,如何构建敏捷生产调度多Agent系统结构和Agent间的协调与生产调度机制,成为一个亟待解决的课题.本文阐述了一类基于多Agent和分布式规则构建敏捷生产调度的方法.首先通过基于功能分解的方法,给出了管理、资源和工件等三类Agent基本组件组成的分布式多Agent调度系统结构、Agent组件基本结构及定义.其次,利用基于分布式规则的方法,建立了Agent间的协调策略和调度机制,实现了敏捷生产调度.最后给出了应用此方法的调度仿真实验结果.     

Emphasizing conflict resolution versus conflict avoidance during schedule generation

Classical planning systems attempt to solve a planning problem by avoiding possible conflicts before the actions are put on a timeline. This is computationally very expensive and the search for all possible future conflicts may be prohibitive. A conflict resolution approach can check for immediate conflicts and try conflict resolution strategies as each activity is put on a timeline without regard for possible future conflicts. A more practical approach is to use a combination of conflict avoidance and conflict resolution based upon heuristics which limit the amount of search required when either is used. Because humans are not good at solving problems which require complex lookahead, this combined approach, with emphasis on conflict resolution, is what human schedulers actually use when they develop schedules. A system which simulates this human approach to scheduling has been developed at NASA's Goddard Space Flight Center for scheduling satellite activities. This system, which includes the Planning And Resource Reasoning (PARR) shell, allows expert schedulers to specify conflict resolution strategies as well as conflict avoidance strategies to be used during the scheduling process. PARR has been used since May 1987 to schedule the Tracking and Data Relay Satellite System services for the Earth Radiation Budget Satellite. PARR will also be used to schedule platform resources on the Explorer Platform, scheduled for launch in early 1992. This paper describes the advantages of using a combined conflict avoidance and resolution approach in a satellite scheduling system.     

Integrated scheduling and flexible maintenance in deteriorating multi-state single machine system using a reinforcement learning approach

This paper studies an integrated optimization problem of production scheduling and flexible preventive maintenance (PM) in a multi-state single machine system with deteriorating effects. A flexible PM strategy is proposed to proactively cope with machine failures while ensuring relatively regular PM intervals, which is composed of time-based PM (TBPM) and condition-based PM (CBPM). TBPM is conducted within every flexible time window and CBPM is implemented immediately after the most deteriorated yet still functional state. An illustrative case is presented using the enumeration approach to demonstrate the integration of production scheduling and machine maintenance. Then, Q-learning-based solution framework (QLSF) is further designed with proper state and action sets and reward functions to facilitate the determination of appropriate production scheduling rule under the constraint of the flexible maintenance. Numerical experiments show that the proposed QLSF outperforms the other four state-of-the-art scheduling rules in different scenarios. Moreover, the performance of the proposed flexible PM strategy is also examined and validated in comparison with three candidate maintenance strategies, i.e., run-to-failure corrective maintenance (CM), combination of TBPM and CM, and CBPM. The proposed flexible maintenance and solution approach can enrich the relevant academic knowledge base, and provide managerial insights and guidance in practical production systems.     

Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints

This paper investigates a difficult scheduling problem on a specialized two-stage hybrid flow shop with multiple processors that appears in semiconductor manufacturing industry, where the first and second stages process serial jobs and parallel batches, respectively. The objective is to seek job-machine, job-batch, and batch-machine assignments such that makespan is minimized, while considering parallel batch, release time, and machine eligibility constraints. We first propose a mixed integer programming (MIP) formulation for this problem, then gives a heuristic approach for solving larger problems. In order to handle real world large-scale scheduling problems, we propose an efficient dispatching rule called BFIFO that assigns jobs or batches to machines based on first-in-first-out principle, and then give several reoptimization techniques using MIP and local search heuristics involving interchange, translocation and transposition among assigned jobs. Computational experiments indicate our proposed re-optimization techniques are efficient. In particular, our approaches can produce good solutions for scheduling up to 160 jobs on 40 machines at both stages within 10?min.     

A fuzzy rule-based meta-scheduler with evolutionary learning for grid computing

Grid computing is increasingly emerging as a promising platform for large-scale problems solving in science, engineering and technology. Nevertheless, a major effort is still required to harness the high potential performance of such computational framework and in this sense, an important challenge is to develop new strategies that efficiently address scheduling on the distributed, heterogeneous and shared environment of grids. Fuzzy rule-based systems (FRBSs) models are dynamic and are currently attracting the interest of scheduling research community to obtain near-optimal solutions on grids. However, FRBSs performance is strongly related to the quality of their knowledge bases and thus, with the knowledge acquisition process. Due to the inherent dynamic nature and the typical complex search spaces of grids, automatically finding a high-quality knowledge base that accurately describes the fuzzy system is extremely relevant. In this work, we propose a scheduling system for grids considering a novel learning strategy inspired by Michigan and Pittsburgh approaches that applies genetic algorithms (GAs) to evolve the fuzzy rule bases and improves the classical learning strategies in terms of computational effort and convergence behaviour. In addition, experimental results show that the proposed schema significantly outperforms other extensively used scheduling strategies.     

Complete parameterized families of job scheduling strategies

Summary The concept of a family of scheduling strategies in which a few parameters may be varied to achieve different performance levels is introduced. The use of such families in satisfying performance requirements stated in terms of average response times for jobs of different classes is studied. A performance requirement is said to be achievable if, given the loading conditions on the system, there exists a scheduling strategy which satisfies it. A family of scheduling strategies is said to be complete if every achievable performance requirement can be satisfied by a strategy from the family. Sufficient conditions for a parameterized family to be complete are proven.Three parameterized families are discussed, one in detail. Completeness of the three families is demonstrated and simulation results illustrating some properties of implementation are presented.     

A Game-Theoretic Analysis of Grid Job Scheduling

Computational Grid is a well-established platform that gives an assurance to provide a vast range of heterogeneous resources for high performance computing. Efficient and effective resource management and Grid job scheduling are key requirements in order to optimize the use of the resources and to take full advantage from Grid systems. In this paper, we study the job scheduling problem in Computational Grid by using a game-theoretic approach. Grid resources are usually owned by different organizations which may have different and possibly conflicting concerns. Thus it is a crucial objective to analyze potential scenarios where selfish or cooperative behaviors of organizations impact heavily on global Grid efficiency. To this purpose, we formulate a repeated non-cooperative job scheduling game, whose players are Grid sites and whose strategies are scheduling algorithms. We exploit the concept of Nash equilibrium to express a situation in which no player can gain any profit by unilaterally changing its strategy. We extend and complement our previous work by showing whether, under certain circumstances, each investigated strategy is a Nash equilibrium or not. In the negative case we give a counter-example, in the positive case we either give a formal proof or motivate our conjecture by experimental results supported by simulations and exhaustive search.     

Combining technical trading rules using particle swarm optimization

Technical trading rules have been utilized in the stock market to make profit for more than a century. However, only using a single trading rule may not be sufficient to predict the stock price trend accurately. Although some complex trading strategies combining various classes of trading rules have been proposed in the literature, they often pick only one rule for each class, which may lose valuable information from other rules in the same class. In this paper, a complex stock trading strategy, namely performance-based reward strategy (PRS), is proposed. PRS combines the two most popular classes of technical trading rules – moving average (MA) and trading range break-out (TRB). For both MA and TRB, PRS includes various combinations of the rule parameters to produce a universe of 140 component trading rules in all. Each component rule is assigned a starting weight, and a reward/penalty mechanism based on rules’ recent profit is proposed to update their weights over time. To determine the best parameter values of PRS, we employ an improved time variant particle swarm optimization (TVPSO) algorithm with the objective of maximizing the annual net profit generated by PRS. The experiments show that PRS outperforms all of the component rules in the testing period. To assess the significance of our trading results, we apply bootstrapping methodology to test three popular null models of stock return: the random walk, the AR(1) and the GARCH(1, 1). The results show that PRS is not consistent with these null models and has good predictive ability.     

Multi-criteria and satisfaction oriented scheduling for hybrid distributed computing infrastructures

Assembling and simultaneously using different types of distributed computing infrastructures (DCI) like Grids and Clouds is an increasingly common situation. Because infrastructures are characterized by different attributes such as price, performance, trust, and greenness, the task scheduling problem becomes more complex and challenging. In this paper we present the design for a fault-tolerant and trust-aware scheduler, which allows to execute Bag-of-Tasks applications on elastic and hybrid DCI, following user-defined scheduling strategies. Our approach, named Promethee scheduler, combines a pull-based scheduler with multi-criteria Promethee decision making algorithm. Because multi-criteria scheduling leads to the multiplication of the possible scheduling strategies, we propose SOFT, a methodology that allows to find the optimal scheduling strategies given a set of application requirements. The validation of this method is performed with a simulator that fully implements the Promethee scheduler and recreates an hybrid DCI environment including Internet Desktop Grid, Cloud and Best Effort Grid based on real failure traces. A set of experiments shows that the Promethee scheduler is able to maximize user satisfaction expressed accordingly to three distinct criteria: price, expected completion time and trust, while maximizing the infrastructure useful employment from the resources owner point of view. Finally, we present an optimization which bounds the computation time of the Promethee algorithm, making realistic the possible integration of the scheduler to a wide range of resource management software.     

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.     

基于PVM的并行分布计算中的任务调度策略

在工程计算中,并行分布计算越来越显得重要,而任务调度策略是影响并行分布计算性能至关重要的因素。在分析了现有的任务调度策略的基础上,结合复杂机电系统耦和问题,提出了两层调度和主动报告的策略。     

A new algorithm for complex product flexible scheduling with constraint between jobs

In order to simplify the complex product flexible scheduling problem with constraint between jobs, a new hierarchical scheduling algorithm based on improved processing operation tree is presented. Aiming at the routing problem, short-time strategy and machine-balance strategy are adopted to assign each operation to a machine out of a set of machines. And in order to solve the sequencing problem, the allied critical path method is first adopted to confirm the scheduling sequence of operations, and then operations are divided into dependent operations and independent ones according to their characteristics. For the dependent operations, forward greedy rule is adopted in order to make the completion time of operation as soon as possible and the scheduling algorithm of shortening idle time is adopted by analyzing the characteristics of the independent operations. Experiment shows that the proposed algorithm solves for the first time the complex product flexible scheduling problem with constraint between jobs.     

基于深度强化学习的微电网在线优化调度

提出一种基于深度强化学习的微电网在线优化调度策略.针对可再生能源的随机性及复杂的潮流约束对微电网经济安全运行带来的挑战,以成本最小为目标,考虑微电网运行状态及调度动作的约束,将微电网在线调度问题建模为一个约束马尔可夫决策过程.为避免求解复杂的非线性潮流优化、降低对高精度预测信息及系统模型的依赖,设计一个卷积神经网络结构学习最优的调度策略.所提出的神经网络结构可以从微电网原始观测数据中提取高质量的特征,并基于提取到的特征直接产生调度决策.为了确保该神经网络产生的调度决策能够满足复杂的网络潮流约束,结合拉格朗日乘子法与soft actor-critic,提出一种新的深度强化学习算法来训练该神经网络.最后,为验证所提出方法的有效性,利用真实的电力系统数据进行仿真.仿真结果表明,所提出的在线优化调度方法可以有效地从数据中学习到满足潮流约束且具有成本效益的调度策略,降低随机性对微电网运行的影响.     

改进灰狼优化算法求解模糊车间调度问题

模糊车间调度问题是复杂调度的经典体现,针对此问题设计优秀的调度方案能提高生产效率。目前对于模糊车间调度问题的研究主要集中在单目标上,因此提出一种改进的灰狼优化算法（improved grey wolf optimization,IGWO）求解以最小化模糊完成时间和最小化模糊机器总负载的双目标模糊柔性作业车间调度问题。该算法首先采用双层编码将IGWO离散化,设计一种基于HV贡献度的策略提高种群多样性;然后使用强化学习方法确定全局和局部的搜索参数,改进两种交叉算子协助个体在不同更新模式下的进化;接着使用两级变邻域和四种替换策略提高局部搜索能力;最后在多个测例上进行多组实验分析验证改进策略的有效性。在多数测例上,IGWO的性能要优于对比算法,具有良好的收敛性和分布性。