Dynamic decision support framework for production scheduling using a combined genetic algorithm and multiagent model

Due to the dynamic nature, complexity, and interactivity of production scheduling in an actual business environment, suitable combined and hybrid methods are necessary. This paper takes prefabricated concrete components as an example and develops the dynamic decision support framework based on a genetic algorithm and multiagent system (MAS) to optimize and simulate the production scheduling. First, a multiobjective genetic algorithm is integrated into the MAS for preliminary optimization and a series of near‐optimal solutions are obtained. Subsequently, considering the resource constraints and uncertainties, the MAS is used to simulate complex real‐world production environments. Considering the different types of uncertainty factors, the paper proposes the corresponding dynamic scheduling method and uses MAS to generate the optimal production schedule. Finally, a practical prefabricated construction case is used to validate the proposed model. The results show that the model can effectively address the occurrence of uncertain events and can provide dynamic decision support for production scheduling.     

基于MAS的动态生产调度与控制及系统开发

提出基于MAS的面向敏捷制造的生产过程动态调度与控制的层次结构．1）以任务分解与分配层为中心，建立各层之间的协调工作及协同决策机制；2）引入协商式招／投标方法实现任务的分解与分配；3）采用能力匹配与动态调度相结合的方法实现任务分配与调度控制的有效集成；4）面向生产任务需求动态确定Agent粒度、组建MAS模型；5）适应制造系统状态变化的需要，进行任务的动态重构．讨论基于MAS的采用分级递阶和并行处理相结合的自治组织结构和运作模式，以及利用与组织结构相对应的层次黑板结构实现各Agent之间信息与数据共享．在支持生产过程动态调度与控制基础设施建设的基础上，结合奏川机床集团有限公司车间生产实际，研究开发了基于MAS的车间动态调度系统．     

A dynamic scheme for scheduling complex tasks in manufacturing systems based on collaboration of agents

The characteristics of scheduling tasks in the real world is a dynamic and challenging issue as the processes and the companies involved may change from time to time. For small flexible enterprises to respond to business opportunities, an effective scheme to facilitate dynamic coalition, share the core competencies and resources and support inter-enterprise collaboration must be developed. Although multi-agent systems (MAS) provide a paradigm for modeling these characteristics, scheduling tasks in MAS is a complex problem due to the computational complexity involved, distributed architecture for scheduling tasks by individual agents and dependency of different agents’ workflows. How to develop a problem solver that can be applied in MAS to achieve coherent and consistent workflow schedules that can meet a customer’s order is an important issue. In this paper, we propose a solution methodology for scheduling workflows in MAS. Our solution combines the multi-agent system architecture to dynamically discover services, workflow and activity models to specify the capabilities of agents, contract net protocol to facilitate negotiation and coordination of agents and optimization theories to optimize the cost for fulfilling an order. A problem solver for scheduling tasks in MAS has been implemented. An application scenario has also been provided to verify our solution methodology.     

An integrated agent-based approach for responsive control of manufacturing resources

Due to the dynamic fluctuation of customer demands in the global market, manufacturing enterprises are facing difficulties in rapidly responding to market changes. The aim of this research is to develop a system to integrate dynamic process planning and dynamic production scheduling for the purpose of increasing the responsiveness of adaptive manufacturing systems in accommodating dynamic market changes (rapidly changing demand patterns or product varieties). The concept of Multi-Agent Systems (MAS) has been adopted in this study. All of the tasks related to process planning, optimization and scheduling in this system are carried out by autonomous agents that are capable of interacting and negotiating with each other to bid for jobs and make decisions. On the one hand, this system optimizes the utilization of manufacturing resources and on the other hand, it also provides a platform where the reconfiguration of manufacturing systems can be assessed. This system has been implemented on a Java platform and a case study is provided to elaborate on this system and evaluate its implementation.     

车间调度中的数据挖掘技术研究

基于Multi-Agent System（MAS）的人机合作技术适合于解决复杂调度问题。为了使人与机能够更好地合作来完成高效、准确的车间调度,引入C4.5算法,建立并实现了基于机器学习和MAS的人机合作车间调度系统仿真模型。在Java环境下,以Weka、JADE为开发平台,以Eclipse为开发工具,Access为后台数据库,完成了系统的开发。通过实例仿真和结果分析,运用机器学习算法动态调度的结果稍优于最佳的静态调度结果,证明了系统的正确性和优越性。     

基于遗传算法的多性能目标网格服务调度算法

在分析状态图工作流模型的基础上，提出了一种网格环境下多QoS（服务质量）约束的组合服务模型，根据提出的模型归纳出了动态服务调度问题的形式化描述，并提出了一种基于遗传算法的动态服务调度算法进行求解.该算法采用基于服务区域及服务实例个数的编码方式，以组合方案的有效性和组合服务的综合QoS参数的效用值作为适应度函数，从而保证组合服务调度的全局QoS要求.与其它算法进行了比较.实验结果显示该算法是可行和有效的．     

基于OPM/MAS 的钢铁企业多agent 生产调度模型

现有的面向agent建模方法在统一性、灵活性、交互能力、逻辑验证能力等方面存在很多不足,阻碍了多agent系统的研究和设计.为此,引入对象过程/多智能体系统(OPM/MAS)的建模方法,将系统的功能、结构和动态行为集成在统一的模型中,用图形和自然语言共同表达复杂系统的抽象概念,可进行逻辑验证,并具有灵活性强、表意清晰等优势.通过在钢铁企业生产调度中的应用,验证了OPM/MAS在多agent等复杂系统建模中的有效性.     

MAS动态协作任务求解模型与算法

针对网格环境的自治性、动态性、分布性和异构性等特征.提出基于多智能体系统(mutil agent system, MAS) 博弈协作的资源动态分配和任务调度模型,建立了能够反映供求关系的网格资源调度动态任务求解算法,证明了资源分配博弈中Nash均衡点的存在性、惟一性和Nash均衡解.该方法能够利用消费者Agent的学习和协商能力,引入消费者的心理行为,使消费者的资源申请和任务调度具有较高的合理性和有效性.实验结果表明,该方法在响应时间的平滑性、吞吐率及任务求解效率方面比传统算法要好,从而使得整个资源供需合理、满足用户QoS要求.     

基于多Agent柔性制造单元的生产调度研究

针对基于制造单元的作业车间的生产调度问题进行了研究,结合多代理的智能性、灵活性和遗传算法的智能优化能力,建立基于多智能体的柔性制造单元的作业车间的调度系统模型.然后,提出了集成多智能体和遗传算法的动态调度策略和调度协商机制;最后,应用此方法完成了常规调度和异常调度的仿真算例.结果表明所开发系统可以解决基于加工单元的制造...     

一种新的基于复合弹簧网络的多Agent系统分布式问题求解方法

当多Agent系统（MAS）中Agent之间存在多种复杂的随机的社会交互行为时，当各Agent表现出不同程度的自治性和理性时，难以用现有的方法描述和求解MAS问题，即使对仅仅存在竞争和合作这两种社会交互行为，并且不考虑Agent之间自治程度的本质性差异时，现有的基于结盟的MAS问题求解算法也具有极高的计算复杂性，该文提出一种新的复合弹簧网络模型和方法，利用分布式弹性动力学方程，将MAS分布式问题求解过程转变对应的复合弹簧网络形变过程，这种模型和方法能够处理各种社会交互行为以及Agent不同程度的自治性，分析和仿真实验表明，在计算复杂性和适用性等许多方面，该文的分布并行算法优于文献[7,8]的Shehory-Kraus算法。     

一种基于博弈论的多Agent交互模型

在开放的、动态的多Agent系统(MAS)中,交互是最基本的方面,具有各自利益的多个Agent必须对其目标、资源的使用进行协调.博弈论为协调和协作的研究奠定了坚实的数学基础,把博弈论与多Agent交互相结合是目前DAI研究的新发展方向.该文提出了一种基于博弈论的多Agent交互模型(GMAIM),应用于解决不完全信息的分布式环境下多人协商决策问题,实现了在会议调度系统(MSS)中的应用.     

Integration of deep reinforcement learning and multi-agent system for dynamic scheduling of re-entrant hybrid flow shop considering worker fatigue and skill levels

In real-life manufacturing systems, production management is often affected by urgent demands and unexpected interruptions, such as new job insertions, machine breakdowns and operator unavailability. In this context, agent-based techniques are useful and able to respond quickly to dynamic disturbances. The ability of agents to recognize their environment and make decisions can be further enhanced by deep reinforcement learning (DRL). This paper investigates a novel dynamic re-entrant hybrid flow shop scheduling problem (DRHFSP) considering worker fatigue and skill levels to minimize the total tardiness of all production tasks. An integrated architecture of DRL and MAS (DRL-MAS) is proposed for real-time scheduling in dynamic environments. Two DRL models are proposed for different sub-decisions, where a reward-shaping technique combining long-term and short-term returns is proposed for the job sequence and machine selection sub-decisions, and an attention-based network is proposed for the worker assignment sub-decision for efficient feature extraction and decision making. Numerical experiments and case studies demonstrate the superior performance of the proposed DRL models compared with existing scheduling strategies.     

A multi-agent system for the decentralized resource-constrained multi-project scheduling problem

A restart evolution strategy (RES) for the resource‐constrained project scheduling problem (RCPSP), as well as its integration in a multi‐agent system (MAS) for solving the decentralized resource‐constrained multi‐project scheduling problem (DRCMPSP) will be presented. To evaluate the developed approach, problem instances of the RCPSP taken from the literature with up to 300 activities are used, as well as 80 generated instances of the DRCMPSP, with up to 20 projects and with up to 120 activities each. For 73 instances of the RCPSP, the RES found better solutions than the best ones found so far. In addition, the MAS is suitable for solving large multi‐project instances decentrally. The results for the DRCMPSP instances show that the presented decentralized MAS is competitive with a central solution approach.     

Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints

Most publications in shop scheduling area focus on the static scheduling problems and seldom take into account the dynamic disturbances such as machine breakdown or new job arrivals. Motivated by the computational complexity of the scheduling problems, genetic algorithms (GAs) have been applied to improve both the efficiency and the effectiveness for NP-hard optimization problems. However, a pure GA-based approach tends to generate illegal schedules due to the crossover and the mutation operators. It is often the case that the gene expression or the genetic operators need to be specially tailored to fit the problem domain or some other schemes may be combined to solve the scheduling problems. This study presents a GA-based approach combined with a feasible energy function for multiprocessor scheduling problems with resource and timing constraints in dynamic real-time scheduling. Moreover, an easy-understood genotype is designed to generate legal schedules. The results of the experiments demonstrate that the proposed approach performs rapid convergence to address its applicability and generate good-quality schedules.     

Dynamic workforce allocation in a constrained flow shop with multi-agent system

The present work addresses the problem of real time workforce scheduling in assembly lines where the number of operators is less to the number of workstations.The problem is faced developing a two-steps procedure made of (i) a centralized scheduling based on a constraint optimization problem (COP) for initial operator scheduling, and (ii) a decentralized algorithm performed by a multiagent system (MAS) to manage workers in case of unforeseen events.In the proposed MAS architecture, Agents represent the operators trying to find local assignments for themselves. The system is validated with a simulation model and implemented with a hardware infrastructure in a real assembly line of electromechanical components. The main original contribution of the paper consists in proving – by means of both validation through a simulation model and test in a real assembly line of electromechanical components – that (1) multi-agent systems could be successfully adopted to solve a workforce scheduling problem, and (2) a combined approach consisting of centralized + distributed approach would provide better results compared with the application of one of the two approaches alone.     

Process plan and part routing optimization in a dynamic flexible job shop scheduling environment: an optimization via simulation approach

This paper presents an optimization via simulation approach to solve dynamic flexible job shop scheduling problems. In most real-life problems, certain operation of a part can be processed on more than one machine, which makes the considered system (i.e., job shops) flexible. On one hand, flexibility provides alternative part routings which most of the time relaxes shop floor operations. On the other hand, increased flexibility makes operation machine pairing decisions (i.e., the most suitable part routing) much more complex. This study deals with both determining the best process plan for each part and then finding the best machine for each operation in a dynamic flexible job shop scheduling environment. In this respect, a genetic algorithm approach is adapted to determine best part processing plan for each part and then select appropriate machines for each operation of each part according to the determined part processing plan. Genetic algorithm solves the optimization phase of solution methodology. Then, these machine-operation pairings are utilized by discrete-event system simulation model to estimate their performances. These two phases of the study follow each other iteratively. The goal of methodology is to find the solution that minimizes total of average flowtimes for all parts. The results reveal that optimization via simulation approach is a good way to cope with dynamic flexible job shop scheduling problems, which usually takes NP-Hard form.     

一种基于历史信息的自适应动态网格作业调度方法

目前,国内外围绕着网格中的作业调度算法已做了大量研究,先后提出了很多调度算法.但是,这些算法并不能很好地适应网格的动态性、自治性和分布性等特征.对此,提出了一种动态的网格作业调度方法-基于历史信息的自适应动态网格作业调度方法ASHI.该方法利用每个资源上最近作业的执行信息自适应调整预测模型,然后再根据网格的动态性和实时性等因素,对资源进行反馈选择后将作业提交负载较轻的资源上执行.实验证明,ASHI不但能及时有效地对作业进行调度,而且还可有效提高整个网格的吞吐量和均衡系统的负载.     

A distributed multi-agent production planning and scheduling framework for mobile robots

Inspired by the new achievements in mobile robotics having as a result mobile robots able to execute different production tasks, we consider a factory producing a set of distinct products via or with the additional help of mobile robots. This particularly flexible layout requires the definition and the solution of a complex planning and scheduling problem. In order to minimize production costs, dynamic determination of the number of robots for each production task and the individual robot allocation are needed. We propose a solution in terms of a two-level decentralized Multi-Agent System (MAS) framework: at the first, production planning level, agents are tasks which compete for robots (resources at this level); at the second, scheduling level, agents are robots which reallocate themselves among different tasks to satisfy the requests coming from the first level. An iterative auction based negotiation protocol is used at the first level while the second level solves a Multi-Robot Task Allocation (MRTA) problem through a distributed version of the Hungarian Method. A comparison of the results with a centralized approach is presented.     

一种基于正关系的多Agent协调算法

多Agent之间的协调(coordination)与协作(cooperation)已经成为多Agent系统(multiagent system,MAS)中的一个关键问题。这是因为MAS的主要研究目标之一就是使得多Agent的信念、意图、期望、行为达到协调甚至协作。在开放、动态的MAS环境下,具有不同目标的多个Agent必须对其资源的使用以及目标的实现进行协调[1,4]。例如,在出现资源冲突时,若没有很好的协调机制,就有可能出现死锁。而在另一种情况下,当单个Agent无法独立完成目标,需要其它Agent帮助时,则需要协作。本文提出了一种基于正关系的多Agent协调机制和协调算法。在该算法中,通过使用这种协调机制,Agent能委托或接受交互中的子计划,从而形成系统负载均衡和有效降低系统运行开销。     

面向哈佛体系结构的集装箱码头场桥作业调度

集装箱码头堆场作业调度问题一直是国内外相关研究的热点和难点,但由于码头作业的动态性、开放性、强耦合性和复杂性,堆场主要装卸设备场桥的调度配置问题一直未能有较好的解决方案。故提出面向哈佛体系结构的基于Agent建模和仿真模式,并将计算机操作系统中的磁盘臂调度算法和基于仿真的优化思想引入到上述模型中。通过构建相应的多Agent系统仿真得出敏捷高效鲁棒的场桥调度和配置解决方案,从而帮助集装箱码头提高服务水平和竞争力。