并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

一种求解单机成组作业优化调度的启发算法

优化目标为总流程时间的单机成组作业优化调度问题，明显是NP－hard的。该文在利用优化性质的基础上，提出了一种构造性的启发算法。该算法计算量小，可应用于大规模优化调度问题，仿真结果表明该算法能够找到次优解，其性能优于已的启发算法。     

改进的蚁群算法求解多目标车间作业调度问题

目前已经有许多解决作业车间调度问题的启发式求解方法,但这些方法多数局限于单目标,因此不能满足现实生活中多目标作业车间调度问题的应用需求。提出一种改进的蚁群算法启发式地搜索多目标车间作业调度问题的近似最优解以满足实际的应用需求。通过对转移概率以及信息素更新方式进行改进,并融合交叉策略,确保算法在加快搜索收敛速度的同时又避免陷入局部最优。仿真实验证明,改进的算法具有较好的性能,能够解决实际生活中的多目标作业车间调度问题。     

改进的蚁群算法求解多目标车间作业调度问题

目前已经有许多解决作业车间调度问题的启发式求解方法,但这些方法多数局限于单目标,因此不能满足现实生活中多目标作业车间调度问题的应用需求.提出一种改进的蚁群算法启发式地搜索多目标车间作业调度问题的近似最优解以满足实际的应用需求.通过对转移概率以及信息素更新方式进行改进,并融合交叉策略,确保算法在加快搜索收敛速度的同时又避免陷入局部最优.仿真实验证明,改进的算法具有较好的性能,能够解决实际生活中的多目标作业车间调度问题.     

灾变遗传算法求解带时间窗的车辆调度问题

提出一种可以有效求解带时间窗的车辆调度问题的灾变遗传算法.遗传算法作为一种高效的启发式算法被用于解决这类组合优化问题,但是该算法存在过早收敛、易陷入局部最优等缺陷.针对此问题,在搜索过程中采用灾变算子使遗传算法跳出局部最优,并针对车辆调度问题设计一种可以直接产生可行解的交叉算子,避免染色体交叉过程中产生不可行的子代.通过仿真算例验证了所提出的算法求解带时间窗的车辆调度问题的有效性;通过与标准遗传算法、改进遗传算法和粒子群算法的比较,进一步验证了灾变遗传算法在优化性能以及算法鲁棒性方面的优势.     

作业车间调度转换瓶颈算法可行性研究*

讨论了转换瓶颈( SB) 算法在解作业车间调度问题时需要解决的子问题。转换瓶颈算法是解决作业车间调度最小makespan( 完工时间) 问题的有效启发式算法。它是基于反复地解决某些单机调度问题这样的子问题。然而所解决的单机调度问题的解可能会导致算法最终得不到可行解, 即使是单机调度最优解也可能得到不可行解。为此, 给出了一个简单的反例证明了产生不可行解的情况, 并对产生不可行解的原因作了详细分析。该研究有利于对转换瓶颈技术进行更好的理解和应用。     

自适应超启发式遗传算法求解随机型生产调度问题

不确定型车间作业调度问题是由确定型车间作业调度问题转化而来的一个随机规划问题.针对目前求解SJSSP问题的启发式算法存在的一些局限,利用目标函数理想最值的条件,以最大加工时间最小化的期望为目标函数,提出了自适应超启发式遗传算法(Adaptive Hyper-Heuristics genetic algorithms,AHHGA),解决此类问题.在上层利用目标函数理想最值的条件,对于不同的场景选用不同的启发式规则.在下层根据上层选择的启发式规则,构造可行解,然后搜索获取最优解.通过上下两层的协同搜索,确保在有限的搜索范围内,找到性能更为优良的解,与此同时,尽可能的减少运算时间.仿真分析表明,对于FT类基准问题,当加工时间服从正态分布时,本文提出算法较目前求解此类问题的同类方法的求解质量具有一定的改进.     

作业车间调度转换瓶颈算法的不可行解问题

文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发式算法。它是基于反复的解决某些单机调度问题。然而在转换瓶颈算法中用Carlier算法解单机调度问题并不总能得到可行解,文中给出了一个反例证明了有产生不可行解的情况。另外,文章还以简洁的方法证明了转换瓶颈算法若用Schrage算法替代Carlier算法解单机调度问题不会产生不可行解。     

求解一类并行多机调度问题的混合启发式算法

该文研究了一类工件具有不同释放时间的并行多机调度问题，调度目标为使总流程时间最小。针对该类调度问题具有强NP—hard的特点，首先构造了的一种启发式算法，该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降，结合遗传算法的全局搜索能力，提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点，能够在较短的时间内求解较大规模的调度问题，算法的计算量小，鲁棒性好。     

具有最大作业延迟的生产调度优化算法及仿真

成组作业优化调度问题中的作业根据其加工特点要求可分成若干作业类。同一类的作业连续加工，其后的作业不需要机器设置花费，而不同类的作业连续加工，其后的作业需要机器设置花费。当优化目标是最大作业延迟时，单机成组作业优化调度是HP—hard。本文在利用优化性质的基础上，提出了一种适于大规模优化调度问题的多项式时间算法。仿真实验表明该算法具有良好的性能。     

解决并行多机提前/拖后调度问题的混合遗传算法方法

研究了带有公共交货期的并行多机提前/拖后调度问题.提出了一种混合遗传算法 方法,以便于确定公共交货期和每台机器上加工的任务代号及其加工顺序,即找到一个最优 公共交货期和最优调度,使加工完所有任务后交货期安排的成本、提前交货成本和拖后交货 成本的总和最小.数值计算结果表明了该混合遗传算法优于启发式算法,并能适用于较大规 模并行多机提前/拖后调度问题.算法计算量小,鲁棒性强.     

Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems

Earliness/tardiness scheduling problems with undetermined common due date which have wide application background in textile industry, mechanical industry, electronic industry and so on, are very important in the research fields such as industry engineering and CIMS. In this paper, a kind of genetic algorithm based on sectional code for minimizing the total cost of assignment of due date, earliness and tardiness in this kind of scheduling problem is proposed to determine the optimal common due date and the optimal scheduling policy for determining the job number and their processing order on each machine. Also, simulated annealing mechanism and the iterative heuristic fine-tuning operator are introduced into the genetic algorithm so as to construct three kinds of hybrid genetic algorithms with good performance. Numerical computational results focusing on the identical parallel machine scheduling problem and the general parallel machine scheduling problem shows that these algorithms outperform heuristic procedures, and fit for larger scale parallel machine earliness/tardiness scheduling problem. Moreover, with practical application data from one of the largest cotton colored weaving enterprises in China, numerical computational results show that these genetic algorithms are effective and robust, and that especially the performance of the hybrid genetic algorithm based on simulated annealing and the iterative heuristic fine-tuning operator is the best among them.     

Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an \(O(n\log n+nF)\) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.     

Two-machine flowshop scheduling with job class setups to minimize total flowtime

This paper studies the two-machine flowshop scheduling problem with job class setups to minimize the total flowtime. The jobs are classified into classes, and a setup is required on a machine if it switches processing of jobs from one class to another class, but no setup is required if the jobs are from the same class. For some special cases, we derive a number of properties of the optimal solution, based on which we design heuristics and branch-and-bound algorithms to solve these problems. Computational results show that these algorithms are effective in yielding near-optimal or optimal solutions to the tested problems.     

Two-machine flow shop scheduling integrated with preventive maintenance planning

This paper investigates an integrated optimisation problem of production scheduling and preventive maintenance (PM) in a two-machine flow shop with time to failure of each machine subject to a Weibull probability distribution. The objective is to find the optimal job sequence and the optimal PM decisions before each job such that the expected makespan is minimised. To investigate the value of integrated scheduling solution, computational experiments on small-scale problems with different configurations are conducted with total enumeration method, and the results are compared with those of scheduling without maintenance but with machine degradation, and individual job scheduling combined with independent PM planning. Then, for large-scale problems, four genetic algorithm (GA) based heuristics are proposed. The numerical results with several large problem sizes and different configurations indicate the potential benefits of integrated scheduling solution and the results also show that proposed GA-based heuristics are efficient for the integrated problem.     

Single machine scheduling to minimize total weighted late work: a comparison of scheduling rules and search algorithms

In this research the problem of scheduling n jobs to minimize the Total Weighted Late Work (TWLW) is evaluated within the single machine context. As the problem complexity increases, so does the solution complexity, and often the objective is to identify a heuristic or algorithm that may return a near optimal solution. Various scheduling rules, heuristics and algorithms, including the weighted shortest processing rule, a variation of the modified due date rule, a genetic algorithm, neighborhood job search, and space smoothing with neighborhood job search, are empirically evaluated using different parameters to determine the utility of each approach.     

考虑恶化效应的MapReduce模型下的同类机调度

本文研究了MapReduce模型中考虑恶化效应的同类机调度问题. 在MapReduce模型中每个工件加工必须经 过两道工序. 其中在第1道工序中每个工件加工任务可分割成若干个子任务且能并行加工, 当某个工件中的所有子 任务全部完成后, 才允许启动第2道工序, 且第2道工序只能在一台机器上连续加工. 本文考虑了工件实际加工时间 与其开工前的等待时间呈线性函数关系的恶化效应, 构建了以最小化所有工件的逗留时间和为目标函数的混合整 数规划模型, 同时给出了问题的一个下界, 最后设计了采用正余弦差分扰动机制的改进蝙蝠优化算法来求解模型. 通过数值仿真对蝙蝠优化算法、遗传算法、CPLEX结果与下界进行对比, 验证了模型的正确性和改进算法的有效 性.     

The Machine Duplication Problem in a Job Shop with Two Jobs

This paper addresses a problem related to the classical job shop scheduling problem with two jobs. The problem consists in concurrently determining the best subset of machines to be duplicated and the optimal scheduling of the operations in order to minimize completion time. Such a problem arises in the tool management for a class of flexible manufacturing cells. The job shop with two jobs is first reviewed, the application of the classical search algorithm A* to this problem is discussed and its performance compared with a previous approach. The complexity of the machine duplication problem is then analysed. The problem is proved to be in general NP-hard in the strong sense, but in a class of special cases, relevant from the applications viewpoint, it can be solved in polynomial time by a dynamic programming algorithm. A heuristic based on such an algorithm and on A* is proposed for the general problem; the results are satisfactory in terms of both efficiency and quality of the solution.     

Single machine scheduling with job delivery to multiple customers

We investigate a single machine scheduling problem with job delivery to multiple customers. In this problem, each job needs to be processed on the single machine, and then delivered by a single vehicle to its customer, where the job has a physical size representing the fraction of space it occupies on the vehicle. The vehicle delivers a shipment from the machine to a customer and has to return back to the machine for delivering the next shipment. It takes different constant time for the round trips between the machine and the different customers. The goal is to minimize the makespan, by that time all the jobs are processed and delivered to their respective customers, and the vehicle returns back to the machine. We propose a 2-approximation algorithm for the general case; when there are only two customers, we present an improved 5/3-approximation algorithm. The design and performance analysis of these two algorithms integrate several known results and techniques for the single machine scheduling problem, the bin-packing problem, and the knapsack problem.