求解多目标流水车间调度Pareto最优解的遗传强化算法

针对多目标流水车间调度Pareto最优问题, 本文建立了以最大完工时间和最大拖延时间为优化目标的多目标流水车间调度问题模型, 并设计了一种基于Q-learning的遗传强化学习算法求解该问题的Pareto最优解. 该算法引入状态变量和动作变量, 通过Q-learning算法获得初始种群, 以提高初始解质量. 在算法进化过程中, 利用Q表指导变异操作, 扩大局部搜索范围. 采用Pareto快速非支配排序以及拥挤度计算提高解的质量以及多样性, 逐步获得Pareto最优解. 通过与遗传算法、NSGA-II算法和Q-learning算法进行对比实验, 验证了改进后的遗传强化算法在求解多目标流水车间调度问题Pareto最优解的有效性.     

求解具有混合约束流水车间调度问题的迭代贪婪算法

流水车间调度问题是具有典型工程应用背景的组合优化问题,对该问题的研究具有重要的理论意义和应用价值。基于传统的流水车间调度问题,提出一种有限等待约束、阻塞约束以及无等待约束共存的混合约束流水车间调度问题。以问题的最小化最大完工时间为目标,提出一种利用迭代贪婪算法进行求解的方法,该方法利用改进的NEH算法计算初始解,通过迭代贪婪算法进行优化,并设计多点交叉策略和插入邻域搜索策略提高解的质量。通过经典实例测试,验证了所提算法的有效性。     

大规模无等待流水调度问题的邻域迭代搜索算法

在分析大规模无等待流水调度问题特点的基础上,提出了利用相邻工件间完工时间距离求最小化完工时间的方法;通过研究工件插入和工件对的交换对最小化完工时间的影响,提出一种邻域迭代搜索算法,该算法降低了求解完工时间的时间复杂度,大大提高了算法效率;为避免算法在邻域搜索过程中陷入局部最优,将变邻域结构算法的思想应用于其中.仿真结果表明,所提出的算法能高效率解决大规模无等待流水调度问题,所得结果令人满意.     

解决具有混合约束柔性流水车间调度问题的粒子群优化算法

针对既存在阻塞限制工件又存在无等待约束工件的柔性流水车间调度问题, 提出了一种离散粒子群优化的求解方法。该方法采用基于排列的编码形式, 设计了推进—迭代算法进行解码并计算问题目标值, 利用离散粒子群优化算法进行全局优化, 利用迭代贪婪(iterated greedy, IG)算法提高种群个体的局部搜索能力。此外, 根据问题特点, 提出最早释放优先(first release first, FRF)和最早完工优先(first complete first, FCF)两种机器分配策略。仿真结果表明, 所提出的方法求解混合约束下柔性流水车间调度问题是可行的、有效的。     

蚁群优化结合变邻域搜索求解NWFS调度问题

针对NP-难的最小化时间表长为目标的无等待流水车间调度问题,将此问题转化为旅行商问题.采用蚁群优化求得初始工件排序.在提出的一种新的邻域结构基础上,迭代进行集中和分散的变邻域搜索以改善解.用Rec系列及he11和he12共计23个Benchmark算例进行计算验证,并与RAJ算法进行了比较.结果表明所提出的方法是有效的.     

一种求解无等待流水车间调度优化的启发式算法

提出了一种新的启发式算法,用于求解无等待流水车间调度问题的总流水时间指标。该算法命名为标准差启发,基于著名的NEH启发算法。首先阐述了总流水时间指标;其次描述了标准差启发算法的过程;最后用标准差启发算法求解标准实验案例,通过实验并与其他启发式算法比较,验证了标准差启发算法在求解无等待流水车间调度问题总流水时间指标的有效性。     

冷卷热处理生产调度模型的启发式算法

主要讨论某钢铁公司冷轧厂热处理车间冷卷热处理生产调度问题,将其归结为一类不允许等待的混合流水车间排序问题进行研究,建立相应的数学模型,设计求解其模型的启发式算法。     

基于混合差分进化算法的无等待流水车间总流水时间优化*

以调度的总流水时间为优化目标, 提出一种混合差分进化算法。 首先, 建立无等待流水车间调度的问题模型,并用快速方法评估总流水时间指标。 其次,采用LPV规则,实现离散问题的连续编码; 用差分进化算法对总流水时间指标执行优化;引入插入邻域和基于pairwise的局部搜索算法, 分别对差分进化算法产生的新个体和差分进化算法的最优解执行邻域搜索, 达到优化目标全局和局部的最优。 最后,通过计算标准算例, 并与其他算法比较, 验证该混合差分进化算法的有效性。     

工件可拒绝的有限等待置换流水车间调度算法

有限等待限定了工件在相邻机器间的等待时间上下限,普遍存在于中间产品性质不稳定且存在运输作业的车间环境中.工件可拒绝的有限等待置换流水车间调度是对工件拒绝和工件调度的联合决策,要求确定拒绝工件集合并给出被接受工件的调度方案.针对这一联合决策问题,以最小化总拒绝成本与总拖期成本之和为目标,并为最大完工时间(Makespan)设置上限约束,结合问题特征提出一种协同进化遗传算法.该算法将染色体编码分解为工件拒绝和工件序列两个子集,基于调度规则生成初始种群,引入协同进化策略依次进化子集种群,并提出基于记忆的动态概率参数设计方法以确定遗传算子的执行概率,设计解码规则以保证解的可行性并优化总成本.最后,通过数据实验验证了所提出算法及相关策略的可行性和有效性,并分析了问题参数对算法性能的影响.     

求解FFS问题的混合搜索机制粒子群算法

针对柔性流水车间调度(flexible flow shop scheduling,FFS)问题,提出了一种混合搜索机制粒子群算法(multi-search mechanism particle swarm optimization algorithm,MMPSO),以期获得柔性流水车间调度问题的优化解。在分析柔性流水车间调度问题特点的基础上,设计了针对该问题的粒子信息编码方案,提出了瓶颈机器消除算法以提升初始种群的质量;同时在个体极值搜索中采用NEH-Greedy搜索算法,在全体极值搜索中采用SADA(simulated snnealing disturb algorithm)搜索算法以扩大搜索范围,提高可行解质量,加快收敛速度,在算法迭代搜索过程中对全体极值进行RPA(random perturbation algorithm)操作以避免算法陷入局部最优。实验结果表明,MMPSO算法能够以较快的收敛速度获得柔性流水车间调度问题的一个较好的优化解。     

Makespan distribution of permutation flowshop schedules

The makespan distribution of permutation flowshop schedules has been a topic of debate for almost fifty years. Many researchers have confirmed or doubted the famous claim that the makespan distribution of permutation flowshop schedules is asymptotically normal if the number of jobs is sufficiently large. This paper theoretically and empirically investigates the makespan distribution of permutation flowshop schedules and shows that the normality claim is not valid for the job-dominated and machine-dominated flowshops. Errors in the proof of normality of the makespan distribution of permutation flowshop schedules are pointed out. It is shown that the makespan distribution of a permutation flowshop scheduling problem depends on the number of jobs as well as the number of machines.     

A new heuristic and dominance relations for no-wait flowshops with setups

The two-machine no-wait flowshop problem, where setup times are considered separate from processing times and sequence independent, is addressed with respect to minimizing total flowtime. A local and a global dominance relation are developed and a new heuristic is provided. Furthermore, a lower bound is obtained and used along with the dominance relations in a branch-and-bound algorithm in order to evaluate the efficiency of the heuristic. Computational experience demonstrates the superiority of the local dominance relation and the new heuristic.Scope and purposeNo-wait flowshop problems, where jobs have to be processed without interruption between consecutive machines, represent an important area in scheduling. There are several industries where the no-wait flowshop problem applies including the metal, plastic, and chemical industries. For instance, in the case of steel production, the heated metal must continuously go through a sequence of operations before it is cooled in order to prevent defects in the composition of the material. Another important area arises when setup time is considered separate from processing time. Such a consideration is particularly justified when the ratio of setup to processing time is non-negligible. Many applications warrant separate consideration of setup; examples include the re-tooling of multi-tool equipment. Other applications can be found in textile, plastic, chemical, and semi-conductor industries. This paper develops a new heuristic and dominance relations for the two-machine no-wait separate setup flowshop problem, where the performance criterion is total flowtime.     

An approximation scheme for two-machine flowshop scheduling with setup times and an availability constraint

This paper studies the two-machine permutation flowshop scheduling problem with anticipatory setup times and an availability constraint imposed only on the first machine. The objective is to minimize the makespan. Under the assumption that interrupted jobs can resume their operations, we present a polynomial-time approximation scheme for this problem.     

Flowshop scheduling of deteriorating jobs on dominating machines

In this paper we consider the general, no-wait and no-idle permutation flowshop scheduling problem with deteriorating jobs, i.e., jobs whose processing times are increasing functions of their starting times. We assume a linear deterioration function with identical increasing rates for all the jobs and there are some dominating relationships between the machines. We show that the problems to minimize the makespan and the total completion time remain polynomially solvable when deterioration is considered, although these problems are more complicated than their classical counterparts without deterioration.     

Permutation flowshop scheduling problems with maximal and minimal time lags

In this paper, we study permutation flowshop problems with minimal and/or maximal time lags, where the time lags are defined between couples of successive operations of jobs. Such constraints may be used to model various industrial situations, for instance the production of perishable products. We present theoretical results concerning two-machine cases, we prove that the two-machine permutation flowshop with constant maximal time lags is strongly NP-hard. We develop an optimal branch and bound procedure to solve the m$m$-machine permutation flowshop problem with minimal and maximal time lags. We test several lower bounds and heuristics providing upper bounds on different classes of benchmarks, and we carry out a performance analysis.     

Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time

We study a two-agent scheduling problem in a two-machine permutation flowshop with learning effects. The objective is to minimize the total completion time of the jobs from one agent, given that the maximum tardiness of the jobs from the other agent cannot exceed a bound. We provide a branch-and-bound algorithm for the problem. In addition, we present several genetic algorithms to obtain near-optimal solutions. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.     

Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications

The multimedia data objects scheduling problem for WWW applications is modeled using the two-machine flowshop problem of minimizing maximum lateness with separate setup times. We establish three dominance relations, and propose four heuristics. Also, we conduct computational experiments to compare the performance of the proposed heuristics and that of existing ones in the literature. The results of the computational experiments show that the proposed heuristics are quite efficient.Scope and purposeA two-machine flowshop scheduling problem involves scheduling a number of jobs on the machines in order to optimize a given criterion. The majority of research assumes that setup times are negligible or can be combined with the processing times. However, the latter assumption is invalid since it may lead to more idle time on the second machine. In the literature, the separate setup times problem has been mainly addressed with the completion-time-related objective functions such as makespan. However, there are many real-life situations in which a due-date-related objective function such as maximum lateness is more appropriate. The problem with maximum lateness objective has received limited attention from researchers as indicated by a recent survey paper. In this paper, we show a real-life situation in the Internet where the two-machine flowshop problem of minimizing maximum lateness with separate setup times can be used to model the multimedia object scheduling problem. We propose new improved heuristics for this problem and compare with existing ones in the literature.     

Non-permutation flowshop scheduling with dual resources

Typically, in order to process jobs in a flowshop both machines and labor are required. However, in traditional scheduling problems, labor is assumed to be plentiful and only machine is considered to be a constraint. This assumption could be due to the lower cost of labor compared to machines or the complexity of dual-resource constrained problems. In this paper a mathematical model is developed to minimize the work-in-process inventory while maximizing the service level in a flowshop with dual resources. The model focuses on optimizing a non-permutation flowshop. There are different skill levels considered for labor and the setup times on machines are sequence-dependent. Jobs are allowed to skip one or more stages in the flowshop. Job release and machine availability times are considered to be dynamic. The problem is solved in two layers. The outer layer is a search algorithm to find the schedule of jobs on the machine (traditional flowshop scheduling problem) and the inner layer is a three-step heuristic to find a schedule of jobs on labor in accordance to the machine schedule. Three different search algorithms are developed to solve the proposed NP-hard problem. First algorithm can solve a permutation flowshop while the other two are developed to solve a non-permutation flowshop. The comparison between the optimal solution and the search algorithms in small examples shows a good performance of the algorithms with an average deviation of only 2.00%. An experimental design analyzes the effectiveness and efficiency of the algorithms statistically. The results show that non-permutation algorithms perform better than the permutation algorithm, although the former are less efficient. The effectiveness and efficiency in all three algorithms have an inverse relation. To the best of our knowledge, this research is the first of its kind to provide a comprehensive mathematical model for dual resource flowshop scheduling problem.     

Minimizing total completion time in two-machine flow shops with exact delays

We study the problem of minimizing total completion time in the two-machine flow shop with exact delay model. This problem is a generalization of the no-wait flow shop problem which is known to be strongly NP-hard. Our problem has many applications but little results are given in the literature so far. We focus on permutation schedules. We first prove that some simple algorithms can be used to find the optimal schedules for some special cases. Then for the general case, we design some heuristics as well as metaheuristics whose performance are shown to be effective by computational experiments.