双机无等待流水作业调度算法研究

考虑双机无等待流水作业调度问题,此问题中每台机器都受一个非可用时间的约束,工件都有不同的释放时间。机器的非可用性时间间隔是部分重叠并且已知。目标使Makespan(最大流程时间)最小。通过不同的方式计算上限和下限,完善分支定界法。计算机实验结果显示了所述方法的有效性。     

基于文化算法的无等待Flowshop调度

针对目标函数为最小化最大完工时间的无等待流水车间调度问题,提出了基于文化算法思想的混合遗传算法.该算法利用文化算法的知识记忆思想进行解群体的控制,构造了两个记忆器来实现这一功能,在迭代过程中继承上一代中较优解的特性,提高了搜索效率和搜索质量.算例实验证明了该算法的有效性.     

淮河群库优化调度系统的设计与实现

首次提出了采用基于并行计算技术的高性能计算方法进行加优化调度的方法,并采用客户／服务器模式在曙光１０００并行机上设计实现了淮河群库优化调度系统。结果表明：其调度的准确性大大优于常规调度,并缩短了整个决策时间,由此产生的经济效益和社会效益是难以估量的。     

基于仿射可调鲁棒优化的园区综合能源系统经济调度

新能源和负荷的不确定性给综合能源系统（integrated energy system,IES）运行带来挑战。首先,基于线性形式的能源集线器模型,对园区IES进行了建模。其次,构建了基于仿射可调鲁棒优化的园区IES两阶段经济调度模型,通过该模型可求得机组的启停及基准出力,以满足不考虑可再生能源出力的能量平衡要求,并求得机组的参与因子,使得调度方案对可再生能源出力不确定集下的任意场景均可行。最后,将该模型转化为混合整数线性规划模型（mixed integer linear programming,MILP）进行求解。算例分析结果表明：通过可调鲁棒优化的经济调度方法所求得的调度方案较经典鲁棒优化有更好的经济性与鲁棒性。     

复杂型面智能生产单元任务−刀具联合动态调度策略

以复杂型面智能生产单元为背景,针对多机器的任务?刀具联合动态调度问题展开研究。通过分析复杂型面智能生产单元的作业流程和特征,建立任务?刀具联合调度问题的数学模型。结合通过对问题进行过程分解的方式构建一种组合规则调度算法生产框架,并通过在框架中嵌入启发式规则的方式生成72种组合规则算法。设计大量的算例测试集,通过对比、分析72种算法在差异化环境配置下的仿真结果,对比不同系统指标下算法的表现情况,发现基于FNOP规则构建的算法在75%的场景中均能取得较优的求解质量。研究成果为车间生产管理人员制定任务?刀具调度策略提供一定指导作用。     

关键链上可被部分替代的受限资源动态调度

关键链上受限资源的优化调度,能有效提高系统运作效率,是关键链项目管理的重要研究方向之一.但现有研究主要针对资源能否更新,较少考虑资源的可替代性.针对此,研究了关键链上可被部分替代的受限资源调度问题,以达到提高资源利用率、降低成本等目的.采用α/β/γ三元组方法,将研究的问题描述为以最小化滞后时间和为目标,具有机器适用限制的并行异速机调度问题,并建立对应的数学模型;运用混合重调度策略和改进粒子群算法进行了算法设计;设计了仿真算例,并通过算法比较表明该方法在求解结果和问题求解规模上显著优于传统PSO、GA算法.     

人机协同的生产调度实验平台

生产调度一直以来都是生产管理的难题,同以往单纯采用算法由机器来获得调度最优解的思路不同的是,采用人机协同的思想开展对调度问题的研究,将调度任务进行分派,使凋度员和机器协同完成调度任务,建立了人机协同的生产调度实验平台.实例表明,该实验平台提供了一个训练调度员调度能力的工具,利用该实验平台,调度员和机器可较好地协同得到满意的调度解.     

考虑机器开关的并行机调度研究

目前机器调度模型对机器可用性的假定是,或者机器一直可用,或者在某些固定时候不可用.而实际应用中,工厂可通过机器的开关优化来节能减排.研究这样一种情况,机器的开关时间点和长度都不确定,需要在决策过程中决定,目标是最小化加权完成时间和节省成本.采用了基于列生成的分支定界法来求解,并结合了动态规划法来提高方法的效率.结果证明...     

水电站群隐随机优化调度方法及其软件包研制

本文在吸收目前国内外水电站群联合调度研究成果的基础上，经分析、综合、充实、完善提出了可供生产单位使用的水电站群优化调度的标准化方法及软件包，它是由水库群入库径流随机模拟、确定性库群联合优化调度及水库群最优调度规则的推求三大部分所组成。软件包采用中文菜单显示选择方式，并使用了中文方式的人机对话，软件包功能齐全，所需内存少，使用方便，标准化方法和软件包可纳入规范化成果，对提高电力系统规则、水电站设计和     

基于约束和邻域的炼钢连铸重调度算法

针对机器故障扰动,研究了炼钢连铸重调度问题及其求解算法。通过将机器故障映射为资源约束,建立了基于动态约束满足的炼钢连铸重调度模型,模型以最大化连浇量与调度方案相似度为目标。针对问题的模型及其特点,采用约束满足和邻域搜索相结合的混合算法对其进行了求解。仿真实验表明本文提出的模型和算法是有效的。     

A scheduling model for systems with task and health dependent remaining useful life prognostics

When we schedule a system to perform a task, a factor that should be taken into account is the remaining useful life prognostics of the system. This prognostics of the system may depend not only on the health state of the system, but also on the characteristics of the task to be performed. Assuming such prognostics is available at the time of system scheduling, the problem is to find a method to schedule the system, which can improve the expected profit rate. Two system life models were proposed for the case considered in this paper. Due to the dynamic nature of the problem, a global optimal policy is hard to find, we proposed an approach based on the approximated expected profit rate to schedule the systems. The approach is validated through simulations compared with a number of other task scheduling rules to show the advantage of the proposed approach. We also find the optimal global stationary result by exhaustive search of small scheduling problems of few systems and tasks to compare with the proposed approximate one. Further numerical analyses are presented to demonstrate the process of determining a decision variable and the sensitivity analysis in terms of a cost parameter.     

Decision-making on multi-mould maintenance in production scheduling

The reliability of a critical tool like a mould on a machine affects the productivity seriously in many manufacturing firms. In fact, its breakdown frequency is even higher than machines. The decision-making on when mould maintenance should be started become a challenging issue. In the previous study, the mould maintenance plans were integrated with the traditional production schedules in a plastics production system. It was proven that considering machine and mould maintenance in production scheduling could improve the overall reliability and productivity of the production system. However, the previous model assumed that each job contained single operation. It is not workable in other manufacturing systems such as die stamping which may contain multiple operations with multiple moulds in each job. Thus, this study models a new problem for multi-mould production-maintenance scheduling. A genetic algorithm approach is applied to minimise the makespan of all jobs in 10 hypothetical problem sets. A joint scheduling (JS) approach is proposed to decide the start times of maintenance activities during scheduling. The numerical result shows that the JS approach has a good performance in the new problem and it is sensitive to the characteristic of the setup time defined.     

A neural network decision-making model for job-shop scheduling

Scheduling in a job-shop system is a challenging task. Simulation modelling is a well-known approach for evaluating the scheduling plans of a job-shop system; however, it is costly and time-consuming, and developing a model and interpreting the results requires expertise. As an alternative, we have developed a neural network (NN) model focused on detailed scheduling that provides a versatile job-shop scheduling analysis framework for management to easily evaluate different possible scheduling scenarios based on internal or external constraints. A new approach is also proposed to enhance the quality of training data for better performance. Previous NN models in scheduling focus mainly on job sequencing and simple operations flow, and may not consider the complexities of real-world operations. The proposed model’s output proved statistically equivalent to the results of the simulation model. The study was accomplished using sensitivity analysis to measure the effectiveness of the input variables of the NN model and their impact on the output, revealing that the batch size variable had a significant impact on the scheduling results in comparison with other variables.     

Scheduling of machines and automated guided vehicles in FMS using differential evolution

This paper addresses the problem of simultaneous scheduling of machines and two identical automated guided vehicles (AGVs) in a flexible manufacturing system (FMS). For solving this problem, a new meta-heuristic differential evolution (DE) algorithm is proposed. The problem consists of two interrelated problems, scheduling of machines and scheduling of AGVs. A simultaneous scheduling of these, in order to minimise the makespan will result in a FMS being able to complete all the jobs assigned to it at the earliest time possible, thus saving resources. An increase in the performance of the FMS under consideration would be expected as a result of making the scheduling of AGVs as an integral part of the overall scheduling activity. The algorithm is tested by using problems generated by various researchers and the makespan obtained by the algorithm is compared with that obtained by other researchers and analysed.     

Integrated process planning and scheduling using an imperialist competitive algorithm

Effective performance of modern manufacturing systems requires integrating process planning and scheduling more tightly, which is consistently challenged by the intrinsic interrelation and intractability of these two problems. Traditionally, these two problems are treated sequentially or separately. Integration of process planning and scheduling (IPPS) provides a valuable approach to improve system performance. However, IPPS is more complex than job shop scheduling or process planning. IPPS is strongly NP-hard in that, compared to an NP-hard job shop scheduling problem with a determined process plan, the process plan for each job in IPPS is also to be optimised. So, an imperialist competitive algorithm (ICA) is proposed to address the IPPS problem with an objective of makespan minimisation. An extended operation-based representation scheme is presented to include information on various flexibilities of process planning with respect to determined job shop scheduling. The main steps of the proposed ICA, including empires construction, assimilation, imperialistic competition, revolution and elimination, are elaborated using an illustrative example. Performance of the proposed ICA was evaluated on four sets of experiments taken from the literature. Computational results of the ICA were compared with that of some existing algorithms developed for IPPS, which validates the efficiency and effectiveness of the ICA in solving the IPPS problem.     

Optimisation of the reverse scheduling problem by a modified genetic algorithm

Traditional scheduling methods can only arrange the operations on corresponding machines with appropriate sequences under pre-defined environments. This means that traditional scheduling methods require that all parameters to be determined before scheduling. However, real manufacturing systems often encounter many uncertain events. These will change the status of manufacturing systems. These may cause the original schedule to no longer be optimal or even to be infeasible. Traditional scheduling methods, however, cannot cope with these cases. New scheduling methods are needed. Among these new methods, one method ‘reverse scheduling’ has attracted more and more attentions. This paper focuses on the single-machine reverse scheduling problem and designs a modified genetic algorithm with a local search (MLGA) to solve it. To improve the performance of MLGA, efficient encoding, offspring update mechanism and a local search have been employed and developed. To verify the feasibility and effectiveness of the proposed MLGA, 27 instances have been conducted and results have been compared with existing methods. The results show that the MLGA has achieved satisfactory improvement. This approach also has been applied to solve a real-world scheduling problem from one shipbuilding industry. The results show that the MLGA can bring some benefits.     

Hybrid simulated annealing with memory: an evolution-based diversification approach

This study presents an efficient metaheuristic approach for combinatorial optimisation and scheduling problems. The hybrid algorithm proposed in this paper integrates different features of several well-known heuristics. The core component of the proposed algorithm is a simulated annealing module. This component utilises three types of memories, one long-term memory and two short-term memories. The main characteristics of the proposed metaheuristic are the use of positive (reinforcement) and negative (inhibitory) memories as well as an evolution-based diversification approach. Job shop scheduling is selected to evaluate the performance of the proposed method. Given the benchmark problem, an extended version of the proposed method is also developed and presented. The extended version has two distinct features, specifically designed for the job shop scheduling problem, that enhance the performance of the search. The first feature is a local search that partially explores alternative solutions on a critical path of any current solution. The second feature is a mechanism to resolve possible deadlocks that may occur during the search as a result of shortage in acceptable solutions. For the case of job shop scheduling, the computational results and comparison with other techniques demonstrate the superior performance of the proposed methods in the majority of cases.     

A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the SS problem in a single model. Based on TCPN modelling, SS is performed using a hybrid heuristic search algorithm to find optimal or near-optimal schedules by searching through the reachability graph of the TCPN with heuristic functions. Large-sized instances are solved in relatively short computation times, which were a priori unsolvable with conventional search algorithms. The algorithm’s performance is evaluated on a benchmark of 82 test problems. Experimental results indicate that the proposed algorithm performs better than the conventional ones and compares favourably with other approaches.     

Divergent production scheduling with multi-process routes and common inventory

This research considers a scheduling problem in a divergent production system (DPS) where a single input item is converted into multiple output items. Therefore, the number of finished products is much larger than the number of input items. This paper addresses two important challenges in a real-life DPS problem faced by an aluminium manufacturing company. One challenge is that one product can be produced following different process routes that may have slightly different capabilities and capacities. The other is that the total inventory capacity is very limited in the company in the sense that a fixed number of inventory spaces are commonly shared by raw materials, WIP (work-in-process) items and finished products. This paper proposes a two-step approach to solving this problem. In the first step, an integer programming (IP) model is developed to plan the type and quantity of operations. In the second step, a particle swarm optimisation (PSO) is proposed to schedule the operations determined in the first step. The computational results based on actual production data have shown that the proposed two-step solution is appropriate and advantageous for the DPS scheduling problem in the company.     

Adaptive scheduling and tool flow control in flexible job shops

The recent manufacturing environment is characterized as having diverse products due to mass customization, short production lead-time, and ever-changing customer demand. Today, the need for flexibility, quick responsiveness, and robustness to system uncertainties in production scheduling decisions has dramatically increased. In traditional job shops, tooling is usually assumed as a fixed resource. However, when a tooling resource is shared among different machines, a greater product variety, routing flexibility with a smaller tool inventory can be realized. Such a strategy is usually enabled by an automatic tool changing mechanism and tool delivery system to reduce the time for tooling set-up, hence it allows parts to be processed in small batches. In this paper, a dynamic scheduling problem under flexible tooling resource constraints is studied and presented. An integrated approach is proposed to allow two levels of hierarchical, dynamic decision making for job scheduling and tool flow control in flexible job shops. It decomposes the overall problem into a series of static sub-problems for each scheduling horizon, handles random disruptions by updating job ready time, completion time, and machine status on a rolling horizon basis, and considers the machine availability explicitly in generating schedules. The effectiveness of the proposed dynamic scheduling approach is tested in simulation studies under a flexible job shop environment, where parts have alternative routings. The study results show that the proposed scheduling approach significantly outperforms other dispatching heuristics, including cost over time (COVERT), apparent tardiness cost (ATC), and bottleneck dynamics (BD), on due-date related performance measures. It is also found that the performance difference between the proposed scheduling approach and other heuristics tend to become more significant when the number of machines is increased. The more operation steps a system has, the better the proposed method performs, relative to the other heuristics.