等待时间受限的流水车间调度问题的启发式算法

针对等待时间受限的流水车间调度问题,分析了等待时间上限与可行解的解析关系以及目标函数的特殊性质,以此为基础,提出了一种启发式算法.算法采用贪婪与插入相结合的启发式规则构造工件加工序列,通过递归回溯解消其等待时间受限约束.仿真实验表明,该启发式工件排序规则在等待时间约束较紧或问题规模较大时,较其他几种常用排序规则具有更好的效果.     

启发式算法求解等待时间受限的两阶段流水车间调度问题

等待时间受限的两阶段流水车间调度问题具有强NP难的复杂性,有必要探索问题特征来开发近似求解算法。本文分析了此问题与一般两阶段流水车间调度和无等待两阶段流水车间调度的关系,给出了两类特殊问题的多项式求解方法,探讨了最优调度的工件序列特征。在此基础上,设计了基于排列排序的启发式算法,算法应用Gilmore-Gomory启发式生成初始序列,构造调度解的可替换集合实现迭代寻优,并利用工件序列特征调整工件顺序以优化当前调度。通过对算法的求解性能进行理论分析和实验验证,进一步表明了该算法的有效性。     

缓冲区有限的两阶段置换流水车间调度问题性质分析

本文针对缓冲区有限的两阶段置换流水车间调度问题的基本性质进行了分析,指出了缓冲区的大小对于问题最优解的影响并证明了该问题的复杂性.通过对原问题及其特例在目标函数之闽关系方面的研究.为算法获得较好的初始解提供了依据.这些性质为设计求解算法提供了理论依据.     

具有缓冲区约束的流水车间调度问题综述

首先介绍了具有缓冲区约束的流水车间调度问题的一般框架、算法及其分类,主要针对启发式算法进行分析和总结,并进一步介绍了如何合理设置缓冲区以及存储时间有限的情况,最后,探讨了在此研究领域中的未来发展趋势.     

有顾客时间窗和发货量变化的紧急车辆调度研究

对紧急车辆调度系统进行了研究,探讨了紧急车辆调度问题实现的关键技术.对有顾客时间窗和发货量变化的紧急车辆调度问题,运用了禁忌算法(TS)进行优化.算法基于实数编码,应用GENI插入法产生初始解和进行邻域操作,设计了三种邻域,利用容量约束控制单条路径配送点数,采用惩罚函数处理时间窗约束,通过设计虚拟车场等方法实现了车辆的紧急调度.本文给出了一个具有代表性的算例试验结果,算例结果及其分析表明了此方法对优化紧急车辆调度问题的有效性.     

资源约束下多项目调度的启发式算法

讨论了目前RCPSP领域的研究现状,建立了一种针对单模式资源受限下多项目调度问题的数学模型,并提出一种解决该问题的启发式算法,给出了具体的算法步骤以及算例,结果表明该算法可以得到可行解.     

等待时间受限的两阶段流水车间调度问题性质研究

对等待时间受限的两阶段流水车同调度问题的基本性质进行了研究.在问题的复杂性方面.证明了任何基于排列排序的调度规则都不能保证具有最优性,而且问题是强NP难的.在原问题和排列排序问题之间的关系方面,证明了满足排列排序要求的任一工件加工序列均可构成相应的可行调度;当满足一定条件时,排列排序的最优解也是原问题的最优解.这些性质为设计求解算法提供了理论基础.     

一种求解Job shop调度问题的启发式组合邻域交换算法

针对job shop调度问题提出一种启发式组合邻域交换算法(HCNA).首先从对任意给定的初始可行调度利用本文提出的最大完工时间贪心算法(CMA)计算出初始可行解,然后利用组合条件邻域交换策略不断地产生新的调度.每当一个新调度形成就调用GMA作可行性判断,过滤掉不可行方案或计算出最大完工时间.对可行方案则反复调用改进的关键路径法(CPA)进行局部优化.文中证明了一个关于调度可行性的定理,指出调度方案的可计算性是其可行性的充要条件.对现有的一些Benchmark问题进行了测试计算,与国内外同类算法最新研究文献中给出的结果作了比较.表明无论从计算时间还是计算精度该算法都占有一定的优势.     

BAB算法中集成CPT求解job-shop调度问题

CSP(constraintsatisfactoryproblem)的优势在于能够处理复杂约束,获得一个满足约束的解,但难以保证解的质量.OR(operationresearch)的优点是获得最优解或近优解,但它求解复杂约束的优化问题非常困难.CPT(constraintpropagationtechnique)是CSP的主要搜索技术,BAB(branch_and_bound)是OR常用的优化算法.提出了一种将CPT集成于BAB中的混合算法,从一个新的角度解决具有一般性与挑战性的job shop调度问题.其主要特点是,通过在BAB算法中嵌入动态可调的时间窗口约束和加强一致性CPT搜索方法,融合BAB的优化能力和CPT处理复杂约束的能力,提高BAB的优化性能及实际应用能力.实验结果令人满意,证明了算法的有效性.     

基于离散粒子群优化的轧辊热处理调度方法

以某轧辊企业铸钢分厂的轧辊热处理调度问题为实际背景,研究了两阶段及三阶段无等待混合流水车间调度问题.针对问题中工件加工无等待特点,设计了分阶段实现的无等待算法;在此基础上,结合离散粒子群优化算法对建立的整数规划模型进行优化求解.通过对真实数据仿真实验所得结果的比较与分析,验证了算法的可行性和有效性,并给出了具有实际参考价值的设备改进策略,对生产决策者合理安排生产具有一定的指导意义.     

An iterated greedy algorithm for the flowshop scheduling problem with blocking

This paper proposes an iterated greedy algorithm for solving the blocking flowshop scheduling problem for makespan minimization. Moreover, it presents an improved NEH-based heuristic, which is used as the initial solution procedure for the iterated greedy algorithm. The effectiveness of both procedures was tested on some of Taillard’s benchmark instances that are considered to be blocking flowshop instances. The experimental evaluation showed the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. In addition, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.     

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising.     

基于风险的考虑成本和允许等待的车辆运输调度问题研究

本文同时考虑了成本约束和允许等待情形,研究了最小化风险的车辆运输调度问题,其中运输风险是随时间不同而变化的,即研究在时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的顶点上决定的出发和等待时间的综合问题。建立了相应的混合整数规划模型,设计了相应的算法,并分析了算法复杂性,最后通过算例验证了该算法的有效性和可行性。     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

考虑交货因素的热轧无缝钢管订单排程模型与算法

无缝钢管的市场需求具有多品种、小批量的特点，为了在满足客户需求的同时保证高效连续化生产，文章在满足生产工艺特征的基础上将配送地址和交货期等合同因素引入热轧无缝钢管订单排程问题中，建立了以适期交货、订单集中生产配送和最小化机器设备调整为优化目标的订单排程优化模型，并设计了两阶段求解算法：首先，以订单交货期与配送地址差异最小为目标，基于凝聚策略设计了订单聚类算法，将具有相同工艺约束、相似合同要求的订单进行聚类，并形成初始轧制计划；然后，以设备调整和提前/拖期最小为目标，设计混合变邻域搜索算法，对初始轧制批次进行排程优化。基于实际订单数据的实验结果表明，模型和算法对问题的描述和求解是可行有效的。     

考虑实时预倒箱的出口箱堆场多场桥调度优化

在出口集装箱堆场的实际作业过程中，倒箱是制约场桥作业效率的瓶颈之一。为提高出口箱堆场的作业效能，减少船舶装船作业时间，采用实时预倒来降低倒箱的影响，研究出口箱堆场多场桥调度优化问题。考虑待提箱作业次序固定、场桥间保持安全距离及不可跨越的现实约束，兼顾内集卡的等待上限，侧重场桥作业过程中的实时预倒箱，构建了以带惩罚因子的内集卡总等待时间最少为目标的混合整数线性规划模型。基于问题自身的特点设计了混合和声模拟退火算法，得出了各场桥的行走路径与实时预倒箱方案。在算例实验中，通过与不考虑实时预倒箱的方案、FCFS方案以及下界进行对比，验证了考虑实时预倒箱的场桥调度模型及算法的有效性，为集装箱码头出口箱堆场的场桥调度提供参考。     

New high performing heuristics for minimizing makespan in permutation flowshops

The well-known NEH heuristic from Nawaz, Enscore and Ham proposed in 1983 has been recognized as the highest performing method for the permutation flowshop scheduling problem under the makespan minimization criterion. This performance lead is maintained even today when compared against contemporary and more complex heuristics as shown in recent studies. In this paper we show five new methods that outperform NEH as supported by careful statistical analyses using the well-known instances of Taillard. The proposed methods try to counter the excessive greediness of NEH by carrying out re-insertions of already inserted jobs at some points in the construction of the solution. The five proposed heuristics range from extensions that are slightly slower than NEH in most tested instances to more comprehensive methods based on local search that yield excellent results at the expense of some added computational time. Additionally, NEH has been profusely used in the flowshop scheduling literature as a seed sequence in high performing metaheuristics. We demonstrate that using some of our proposed heuristics as seeds yields better final results in comparison.     

Effective heuristics for the blocking flowshop scheduling problem with makespan minimization

The blocking flowshop scheduling problem with makespan criterion has important applications in a variety of industrial systems. Heuristics that explore specific characteristics of the problem are essential for many practical systems to find good solutions with limited computational effort. This paper first presents two simple constructive heuristics, namely weighted profile fitting (wPF) and PW, based on the profile fitting (PF) approach of McCormick et al. [Sequencing in an assembly line with blocking to minimize cycle time. Operations Research 1989;37:925-36] and the characteristics of the problem. Then, three improved constructive heuristics, called PF-NEH, wPF-NEH, and PW-NEH, are proposed by combining the PF, wPF, and PW with the enumeration procedure of the Nawaz-Enscore-Ham (NEH) heuristic [A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA-International Journal of Management Science 1983;11:91-5] in an effective way. Thirdly, three composite heuristics i.e., PF-NEH_LS, wPF-NEH_LS, and PW-NEH_LS, are developed by using the insertion-based local search method to improve the solutions generated by the constructive heuristics. Computational simulations and comparisons are carried out based on the well-known flowshop benchmarks of Taillard [Benchmarks for basic scheduling problems. European Journal of Operation Research 1993;64:278-85] that are considered as blocking flowshop instances. The results show that the presented constructive heuristics perform significantly better than the existing ones, and the proposed composite heuristics further improve the presented constructive heuristics by a considerable margin. In addition, 17 new best-known solutions for Taillard benchmarks with large scale are found by the presented heuristics.     

Scheduling Methods for Efficient Stamping Operations at an Automotive Company

We consider scheduling issues at Beyçelik, a Turkish automotive stamping company that uses presses to give shape to metal sheets in order to produce auto parts. The problem concerns the minimization of the total completion time of job orders (i.e., makespan) during a planning horizon. This problem may be classified as a combined generalized flowshop and flexible flowshop problem with special characteristics. We show that the Stamping Scheduling Problem is NP‐Hard. We develop an integer programming‐based method to build realistic and usable schedules. Our results show that the proposed method is able to find higher quality schedules (i.e., shorter makespan values) than both the company's current process and a model from the literature. However, the proposed method has a relatively long run time, which is not practical for the company in situations when a (new) schedule is needed quickly (e.g., when there is a machine breakdown or a rush order). To improve the solution time, we develop a second method that is inspired by decomposition. We show that the second method provides higher‐quality solutions—and in most cases optimal solutions—in a shorter time. We compare the performance of all three methods with the company's schedules. The second method finds a solution in minutes compared to Beyçelik's current process, which takes 28 hours. Further, the makespan values of the second method are about 6.1% shorter than the company's schedules. We estimate that the company can save over €187,000 annually by using the second method. We believe that the models and methods developed in this study can be used in similar companies and industries.     

Managing appointments with waiting time targets and random walk-ins

The random arrivals of walk-in patients significantly affect the daily operations of healthcare facilities. To improve the performance of outpatient departments, this paper attempts to make an appointment schedule by considering walk-ins and the waiting time target (WTT) for appointment patients. A stochastic programming model is proposed to solve this problem with the objective of minimizing the weighted patient waiting and makespan cost. A non-decreasing waiting cost function is used to capture the WTT fulfillment of appointment patients, whereas walk-ins incur a linear waiting cost. A finite-horizon Markov Decision Process model is formulated to establish the optimal real-time scheduling policy under a given appointment schedule. The appointment schedule is determined by a two-stage stochastic programming approximation and a local search improvement. Structural properties of the optimal appointment scheduling and real-time scheduling policies are established. In particular, it is shown that appointment overbooking is allowed only at the end of the regular session, and the optimal real-time scheduling policy is an easy-to-implement threshold policy with bounded sensitivity. Numerical experiments based on real data are performed to investigate the influence of different parameters and to compare different schedules. The optimal schedule demonstrates superior performance by allowing reasonable waiting times for appointment patients depending on their WTTs. Managerial insights are also provided to hospital managers. Finally, the basic model is extended by incorporating random service times and random arrivals of appointment patients. The latter includes the random number of patients that show up for service or call for appointments, and the random arrival time (unpunctuality). Appointment overbooking strategies are shown to have different structures under some stochastic factors.