A GA methodology for the scheduling of yarn-dyed textile production

This paper presents a scheduling approach for yarn-dyed textile manufacturing. The scheduling problem is distinct in having four characteristics: multi-stage production, sequence-dependent setup times, hierarchical product structure, and group-delivery (a group of jobs pertaining to a particular customer order must be delivered together), which are seldom addressed as a whole in literature. The scheduling objective is to minimize the total tardiness of customer orders. The problem is formulated as a mixed integer programming (MIP) model, which is computationally extensive. To reduce the problem complexity, we decomposed the scheduling problem into a sequence of sub-problems. Each sub-problem is solved by a genetic algorithm (GA), and an iteration of solving the whole sequence of sub-problems is repeated until a satisfactory solution has been obtained. Numerical experiment results indicated that the proposed approach significantly outperforms the EDD (earliest due date) scheduling method—currently used in the yarn-dyed textile industry.     

Multi-objective optimization model for multi-project scheduling on critical chain

In this paper, a multi-project scheduling in critical chain problem is addressed. This problem considers the influence of uncertainty factors and different objectives to achieve completion rate on time of the whole projects. This paper introduces a multi-objective optimization model for multi-project scheduling on critical chain, which takes into consideration multi-objective, such as overall duration, financing costs and whole robustness. The proposed model can be used to generate alternative schedules based on the relative magnitude and importance of different objectives. To respond to this need, a cloud genetic algorithm is proposed. This algorithm using randomness and stability of Normal Cloud Model, cloud genetic algorithm was designed to generate priority of multi-project scheduling activities and obtain plan of multi-project scheduling on critical chain. The performance comparison shows that the cloud genetic algorithm significantly outperforms the previous multi-objective algorithm.     

A GA/TS algorithm for the stage shop scheduling problem

This paper presents a special case of the general shop called stage shop problem. The stage shop is a more realistic generalization of the mixed shop problem. In the stage shop problem, each job has several stages of operations. In order to solve the stage shop problem with makespan objective function, an existing neighborhood of job shop is used. In this neighborhood, few enhanced conditions are proposed to prevent cycle generation. In addition, a new neighborhood for operations that belong to the same job is presented. These neighborhoods are applied to the stage shop problem in a tabu search framework. A genetic algorithm is used to obtain good initial solutions. An existing lower bound of the job shop is adapted to our problem and the computational results have been compared to it. Our algorithm has reached the optimal solutions for more than half of the problem instances.     

组合优化问题中遗传算法的局限性及其改进模式

遗传算法在解决多峰函数求解，多目标规划和生产调度等问题时，相对其它优化算法具有一定的优势，但仍存在严重的局限性，尤其表现在组合优化的求解问题中，为此，提出一种“生物进化过程＝遗传操作＋免疫功能”的新模式，并通过生产调度的求解问题验证了该算法的有效性。     

共享汽车系统空车调度的鲁棒优化模型

面向共享汽车系统的运营商与潜在用户,针对实现最大利润的空车调度问题,同时考虑乘客需求信息的不确定性对调度过程的影响,利用基于可调决策规则的鲁棒优化方法进行建模与求解.在共享汽车系统中,乘客的出行需求是不确定的,给出相应的不确定集合描述,将乘客的出行需求限制在一定的区间内,并灵活限制时间上的乘客需求之和,以减小模型的保守性.在此基础上引入可调决策规则,使得空车调度的策略可以根据已实现的需求进行调整,提出空车调度的鲁棒优化模型及其可解的线性规划形式.仿真实验利用真实的滴滴订单信息模拟用户使用共享汽车出行的需求,展示该模型所提出的空车调度策略(相较于确定性模型)会投入更多的费用在空车调度上,使运营商在平均意义和最差情况下均获得更大的利润并满足更多的乘客需求,表明所提出模型的鲁棒性和实用性.     

A new hybrid GA solution to combinatorial optimization problems— an application to the multiprocessor scheduling problem

The multiprocessor scheduling problem is one of the classic examples of NP-hard combinatorial optimization problems. Several polynomial time optimization algorithms have been proposed for approximating the multiprocessor scheduling problem. In this paper, we suggest a geneticizedknowledge genetic algorithm (gkGA) as an efficient heuristic approach for solving the multiprocessor scheduling and other combinatorial optimization problems. The basic idea behind the gkGA approach is that knowledge of the heuristics to be used in the GA is also geneticized alongiside the genetic chromosomes. We start by providing four conversion schemes based on heuristics for converting chromosomes into priority lists. Through experimental evaluation, we observe that the performance of our GA based on each of these schemes is instance-dependent. However, if we simultaneously incorporate these schemes into our GA through the gkGA approach, simulation results show that the approach is not problem-dependent, and that the approach outperforms that of the previous GA. We also show the effectiveness of the gkGA approach compared with other conventional schemes through experimental evaluation. This work was presented, in part, at the Second International Symposium on Artifiical Life and Robotics, Oita, Japan, February 18–20, 1997     

啤酒生产调度数学模型及其优化

针对啤酒企业生产人工调度效果不理想的问题,建立了啤酒生产调度数学模型,并研究了此类间歇工业调度问题的优化方法.根据啤酒生产流程特点,将整个啤酒生产划分为糖化区、过滤包装区,分别建立相应的生产调度数学规划模型,并通过蚁群优化算法求解此类调度问题.该优化调度方案在企业中的应用结果表明,通过蚁群算法对建立的啤酒调度模型进行优化,该方法具有良好的鲁棒性与实用性,可为生产管理人员提供方便快捷的优化解决方案.     

A quantum particle swarm optimization driven urban traffic light scheduling model

Urban traffic congestion becomes a severe problem for many cities all around the world. How to alleviate traffic congestions in real cities is a challenging problem. Benefited from concise and efficient evolution rules, the Biham, Middleton and Levine (BML) model has a great potential to provide favorable results in the dynamic and uncertain traffic flows within an urban network. In this paper, an enhanced BML model (EBML) is proposed to effectively simulate the urban traffic where the timing scheduling optimization algorithm (TSO) based on the quantum particle swarm optimization is creatively introduced to optimize the timing scheduling of traffic light. The main contributions include that: (1) The actual urban road network with different two-way multi-lane roads is firstly mapped into the theoretical lattice space of BML. And the corresponding updating rules of each lattice site are proposed to control vehicle dynamics; (2) compared with BML, a much deeper insight into the phase transition and traffic congestions is provided in EBML. And the interference among different road capacities on forming traffic congestions is elaborated; (3) based on the scheduling simulation of EBML, TSO optimizes the timing scheduling of traffic lights to alleviate traffic congestions. Extensive comparative experiments reveal that TSO can achieve excellent optimization performances in real cases.

     

A collaborative scheduling GA for products-packages service within extended selling chains environment

The theory of network coordination provides theoretical foundations to explain how companies can overcome organizational boundaries and constraints to jointly manage business processes across their selling chains. In particular, this work focuses on Collaborative Scheduling, a collaboration process whereby selling chain trading partners activate either on-line or off-line inter-firm coordination mechanisms to jointly plan production activities in order to deliver the final products to end customers each one of them, being the delivery date as close to the date desired as possible. The problem of collaborative scheduling is formally defined by means of a mathematical model. In the model, the defined objective function has the goal to minimize the total weighted tardiness of the package of products acquired by the clients to be delivered in a specific date. The delivery date of each Product-Package is conditioned by the latest date established by each supplier for each product that forms part of the same one. Besides, having different process times for each product and different penalties for each Product-Package, each supplier can offer a different mix of additional products with different due date. Due to the complexity of the problem a Genetic Algorithm has been the approach taken for its resolution. The GA elements and procedures are defined and the parameters are tuned. Although the major contribution of this work focuses on the algorithmic development of a proposal in the context of operations research that could help to solve the problem also is discussed the environment in which this occurs and that justifies our interest. In order to validate the proposed solutions diverse configurations are presented and the results obtained by means of the GA and some heuristics rules are compared.     

面向温度优化的片上网络任务调度方法

随着片上网络规模的扩大和研究的逐步深入,如何将芯片上众多的任务进行合理的调度成为系统温度优化的关键之一。针对片上网络任务调度问题, 提出一种基于最短曼哈顿距离的任务调度SMDS方案。该策略充分考虑核通信图中通信节点对之间最短曼哈顿路径,通过搜索算法寻找任务调度的目的节点,使用模拟退火算法确定任务调度对。实验结果显示,与传统的分布式任务调度 DTM策略相比,针对6*6、8*8和10*10的拓扑结构,SMDS实验方案在迁移次数方面的平均优化率分别为2208%、21.74%和23.02%。在平均跳数方面的平均优化率分别为24.04%、29.18%和23.04%,实现了系统温度优化。     

混合并行机调度问题的多目标优化模型及算法

针对生产工序的合并造成一种串并联共存的生产布局,研究了一种特殊的混合并行机调度问题,并考虑以最小化总流水时间和最小化总延迟工件数量为目标的多目标调度问题,建立了混合整数规划模型.针对模型特点,设计了一种改进的非支配排序遗传算法进行求解,采用基于启发式方法的初始种群生成方式以提高种群的质量和多样性,并引入一种局域搜索策略以改善求解算法所获得的非支配解的质量及分布性.通过对大量数值算例进行仿真实验,并与典型的多目标优化算法进行比较,结果表明所提出的模型和算法在收敛性、分布性及极端点质量方面均具有优势,能够较好的解决多目标混合并行机调度问题.     

单船岸桥分配与调度集成优化模型

针对集装箱码头泊位确定条件下的单船岸桥(QC)分配和调度问题,建立了线性规划模型.模型以船舶在泊作业时间最短为目标,考虑多岸桥作业过程中的干扰等待时间与岸桥间的作业量均衡,并设计了嵌入解空间切割策略的改进蚁群优化(IACO)算法进行模型求解.实验结果表明:与可用岸桥全部投放使用的方法相比,所提模型与算法求得结果平均能够节省31.86%的岸桥资源;IACO算法与Lingo求得的结果相比,船舶在泊作业时间的平均偏差仅为5.23%,但CPU处理时间平均降低了78.7%,表明了所提模型与算法的可行性和有效性.     

A hybrid meta-heuristic algorithm for optimization of crew scheduling

Crew scheduling problem is the problem of assigning crew members to the flights so that total cost is minimized while regulatory and legal restrictions are satisfied. The crew scheduling is an NP-hard constrained combinatorial optimization problem and hence, it cannot be exactly solved in a reasonable computational time. This paper presents a particle swarm optimization (PSO) algorithm synchronized with a local search heuristic for solving the crew scheduling problem. Recent studies use genetic algorithm (GA) or ant colony optimization (ACO) to solve large scale crew scheduling problems. Furthermore, two other hybrid algorithms based on GA and ACO algorithms have been developed to solve the problem. Computational results show the effectiveness and superiority of the proposed hybrid PSO algorithm over other algorithms.     

基于多Agent的虚拟企业任务调度模型及优化

采用多钾能体技术构建虚拟企业任务调度模型,并对基于该模型的任务调度运作过程进行说明.针对调度优化问题,以资源智能体承担的生产任务为研究对象,综合考虑生产任务之间的时序逻辑关系、作业时间及资源自身已确定的生产任务等影响因素,建立以生产延续时间最小为目标的优化模型,给出粒子群优化求解算法.应用实例及数字仿真验证了模型及优化算法有效性.     

基于延迟调度策略的Reduce调度优化算法

在大规模的Hadoop集群中,良好的任务调度策略对提高数据本地性、减小网络传输开销、减少作业执行时间以及提高集群的作业吞吐量都有着重要的影响。本文针对Hadoop架构中Reduce任务的数据本地性较低问题,提出了一种基于延迟调度策略的Reduce任务调度优化算法,通过提高Reduce任务的数据本地性来减少作业执行时间以及提高作业吞吐量,该算法在Hadoop架构的Early Shuffle阶段,使用多级延迟调度策略来提高Reduce任务的数据本地性。最后重写原生公平调度器代码实现了该调度算法,并与原生公平调度器进行了对比实验分析,实验结果表明该算法明显减少了作业执行时间,提高了集群的作业吞吐量。     

应急资源联合调度博弈模型及优化

非常规突发事件爆发后, 如何使用不同的运输方式联合调度应急资源就成为急需解决的关键问题。鉴于应急资源在应急资源中心、资源中转站和需求中心之间的调运, 设计了应急资源流转过程模型。 在此基础上, 考虑到多种运输方式的联合调度问题而设计了面向非常规突发事件的应急资源联合调度博弈模型和算法。 针对经典核心法对该模型求解可能出现无解或多解的情况,提出了改进的核心法。 通过应急资源调度的算例分析与比较, 验证了所建模型与算法的有效性和求解结果作为调度策略的优越性。     

两部件系统视情维修与生产调度的联合优化模型

为了解决生产调度过程中由系统维护维修产生的资源闲置和时间成本增加问题,将系统维修与生产调度联合建模.在众多学者将系统作为整体进行生产调度与维修研究的基础上,考虑系统内各组成部件之间的复杂关系.针对具有经济相关性的两部件系统,以调度作业加工顺序、预防性维修阈值、机会维修阈值作为决策变量,考虑到两部件同时维修比单部件独立维...     

A Benders decomposition for the location-allocation and scheduling model in a healthcare system regarding robust optimization

The hospital location and service allocation is one of the most important aspects of healthcare systems. Due to lack of studies on covering location-allocation and scheduling problems with respect to the uncertain budget, this paper develops a bi-objective hybrid model to locate hospitals and allocate machines and services scheduled. The costs of establishing facilities are assumed to be uncertain, while a robust counterpart model is employed to overcome the uncertainty. Covering the demand of each service is limited as well. Moreover, hospitals have a limited space to the specialized equipment like CT scan and MRI machines, while there is a cost constraint on hospitals and the specialized equipment. The aim of this paper is to find a near-optimal solution including the number of hospitals and the specialized equipment, the location of hospitals, the assignment of demand of each service and the specialized equipment to hospitals, the determination of allowable number of each service of hospitals, the determination of demand that should be transferred from one hospital to another (patient transfer), and schedule services. As the proposed model, minimizing the total costs and the completion time of demand simultaneously, is an NP-hard problem, it is impossible to solve its large-scale version with exact methods in a reasonable time. Thus, a hybrid algorithm including simulated annealing optimization and the Benders decomposition is employed to solve it. The CPLEX optimizer verifies the presented algorithm to solve the proposed model. The sensitivity analysis is performed to validate the proposed robust model against of uncertain situations while the Monte Carlo simulation is used to analyze the quality and the robustness of solutions under uncertain situations. The results show that the uncertainty used in the proposed model properly formulates real-world situations compared to the deterministic case. Finally, the contributions and the future research are presented.