基于改进的RA逄法的混合Flowshop调度问题的求解

针对混合Flowshop系统的最小化akespan调度问题，提出基于改进的RA斜度指标的启发式算法来对工件进行排序，采用FAM算法来分配设备，并给出最优值的下界检验该算法。仿真结果表明，该方法优于目前最好的启发式算法，能较好地解决混合Flowshop的调度问题。     

并行流程车间调度问题及其概率学习进化算法

并行Flowshop调度问题兼有并行机器和流程车间调度问题的特点,是一类新型的调度问题.针对最小化最大完工时间目标函数,建立了一般并行Flowshop调度问题的整数规划模型.鉴于问题的求解复杂性,设计了基于概率学习的求解算法.对随机生成的测试问题进行求解,实验结果显示出该算法求解并行Flowshop调度问题的良好潜能.     

应用Agent理论的生产调度系统研究

生产调度问题,一般可根据生产流程的不同分为Job-shop调度和Flowshop调度两大类(也有学者认为,存在两者相结合的第三类—混合调度)。该文研究以最小化Makespan为目标的Flowshop调度问题。基于Agent理论,提出采用Flowshop复合代理体(Flowshop-Compound-Agent,FSCA)求解Flowshop调度问题的方法。在给出FSCA的结构及其实现的基础上,通过毛纺企业制条车间的实例说明了使用FSCA解决Flowshop调度问题的有效性。     

基于遗传算法的某航空发动机装配车间优化调度

航空发动机装配车间装配生产线的调度问题,是一类比较典型的混合Flowshop问题,同时还带有工件可重人等特点,这就区别于一般的Flowshop和Jobshop调度问题,因此,将可重入混合车间调度问题划为第三类调度问题。关于重入式混合车间生产调度的优化问题通常来说都是属于NP难问题。文中通过某航空发动机装配车间生产线的研究,以最小化最大完工时间为目标函数,借助随机矩阵的编码方式和改进的交叉方法与变异方法,提出了基于遗传算法的调度优化方法。最后实验结果表明,文中提出的改进算法能够有效地实现装配车间调度的优化。     

应用Agent理论的生产调度系数研究

生产调度问题，一般可根据生产流程的不同分为Job-shop调度和Flowshop调度两大类（也有学者认为，存在两者相结合的第三类－混合调度）。该文研究以最小化Makespan为目标的Flowshop调度问题。基于Agent理论，提出采用Flowshop复合代理体（Flowshop-Compond-Agent,FSCA)求解Flowshop调度问题的方法，在给出FSCA的结构及其实现的基础上，通过毛纺企业制度车间的实例说明了使用FSCA解决Flowhop调度问题的有效性。     

一类Job- shop 车间生产计划和调度的集成优化

讨论一类Job—shop车间的生产计划和调度的集成优化问题，给出了该问题的非线性混合整数规划模型，并采用混合遗传算法进行求解。该模型利用调度约束来细化生产计划，以保证得到可行的调度解。在混合算法中，利用启发式规则来改善初始解集，并采用分段编码策略将计划和调度解映射为染色体。算例研究表明，该算法对求解该类问题具有很好的效果。     

基于联姻遗传算法的混合FloWshop提前/拖期调度问题

混合流水车间(Flowshop)提前／拖期调度问题的目标是4~_r-件的提前／拖期惩罚成本最小，这是一个NP完全问题，很难用一般的方法解决。文中首先给出了问题的数学模型，然后采用联姻遗传算法求解该问题。仿真结果表明此算法能有效地解决该类复杂调度问题。     

基于复合代理体（Agent）的纺纱车间调度系统研究

毛纺企业的纺纱车间生产调度问题是一种复杂的Flowshop调度问题，针对这类问题， 本文提出采用Flowshop复合代理体（FSCA）求解的方案，其中使用了GA算法．在讨论了FSCA 的结构、实现和详细调度算法的基础上，通过纺纱车间调度实例研究说明了使用FSCA解决Fl owshop调度问题的有效性．     

多机Flow shop加权完成时间调度问题的启发式算法分析

因实际生产中调度问题的规模很大，分析其近似算法的绝对性能比很难，有时甚至不可行，所以研究近似算法的渐近性能比就很有必要，本文针对多机Flowshop加权完成时间调度问题，使用单机松弛和概率分析方法，证明了基于加权最短处理时间需求的启发式算法是渐近最优的．     

三峡工程两坝联合通航调度的混合模拟退火算法

对三峡大坝和葛洲坝的一共5座船闸进行统一的船舶通航调度管理,是提高长江三峡水域航运能力的关键,然而其优化调度算法还缺乏必要的研究.本文首先提出了该问题的混合整数非线性规划模型,在实际通航调度环境中,该模型属于强NP-hard复杂度的大规模组合优化问题,因此设计了一种混合模拟退火算法来搜索次优化调度方案,该算法将解分解为闸次时间表和船舶调度计划两部分,在搜索过程中用启发式规则对闸次时日表进行调整,然后用深度优先搜索(DFS)算法根据闸次时间表求解船舶调度计划,最后根据Metropolis规则对当前解进行更新.针对实际通航数据的测试结果表明其优化效果明显优于原有的启发式算法.目前该算法已经成功地应用于实际的两坝联合通航调度系统中.     

求解多目标PFSP的改进遗传算法

针对多目标置换流水车间调度问题（PFSP）提出了一种改进的遗传算法,用于优化最大完工时间和总完工时间。该算法采用启发式算法和随机算法相结合产生初始种群,以保持种群多样性;通过选择、交叉、变异操作以及群体更新策略完成进化过程;当种群进化停滞时,引入群体重新初始化机制恢复多样性。此外,设计了一种变邻域搜索算法,加速种群收敛并跳出局部最优。通过基准测试问题实验以及与其他几个优化算法比较,结果表明,提出的算法无论在求解质量还是稳定性方面都优于其他算法。     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing

This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver.     

An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes

We consider the problem of minimizing the makespan on a single batch machine with non-identical job sizes, where several jobs can be simultaneously processed as a batch. We formulate makespan minimization as a problem of minimizing the wasted space. Applying a candidate set strategy to narrow the search space, combined with a wasted-space-based heuristic to update the pheromone information, an improved max–min ant system algorithm is presented. A specific local search method is incorporated to gain better performance. Appropriate parameter settings in the proposed algorithm are determined by extensive experiments. The experimental results show that the proposed algorithm outperforms several previously studied algorithms.     

An improved heuristic for minimizing makespan among m identical parallel processors

A simple heuristic for minimizing makespan among identical processors assigned independent tasks is presented and explored. The heuristic initially assigns jobs to processors by applying a quick and effective algorithm which at present is commonly applied to this problem. The heuristic then seeks to identify pairs of jobs that may be interchanged between processors to improve the solution. The conditions under which an optimal makespan may be achieved by such an interchange are derived for the case of two processors. The procedure is then extended to three or more processors. Results of 700 randomly generated problems are reported. The heuristic achieved an optimal solution for most of the problems. The worst case performance for the heuristic has not been established; however, evidence is presented that the worst case for the heuristic is considerably smaller than that of algorithms presently used.     

An artificial neural network based heuristic for flow shop scheduling problems

The objective of this paper is to find a sequence of jobs in the flow shop to minimize makespan. A feed forward back propagation neural network is used to solve the problem. The network is trained with the optimal sequences of completely enumerated five, six and seven jobs, ten machine problem and this trained network is then used to solve the problem with greater number of jobs. The sequence obtained using artificial neural network (ANN) is given as the initial sequence to a heuristic proposed by Suliman and also to genetic algorithm (GA) as one of the sequences of the population for further improvement. The approaches are referred as ANN-Suliman heuristic and ANN-GA heuristic respectively. Makespan of the sequences obtained by these heuristics are compared with the makespan of the sequences obtained using the heuristic proposed by Nawaz, Enscore and Ham (NEH) and Suliman Heuristic initialized with Campbell Dudek and Smith (CDS) heuristic called as CDS-Suliman approach. It is found that the ANN-GA and ANN-Suliman heuristic approaches perform better than NEH and CDS-Suliman heuristics for the problems considered.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

基于改进蛙跳算法的分布式两阶段混合流水车间调度

针对考虑顺序相关准备时间的分布式两阶段混合流水车间调度问题,提出一种改进的蛙跳算法以同时最小化拖后工件数和最大完成时间.该算法通过启发式方法和随机方法对种群进行初始化,采取基于种群和记忆的种群划分方法,同时给出模因组质量评价方法,并根据模因组质量将所有模因组划分为最优模因组、最差模因组和其他模因组,每种类型的模因组分别采取不同的搜索策略,并分配不同的搜索次数,其中最优模因组不参与种群划分.选用一种多目标经典算法和两种近5年提出的算法作为对比算法,并与改进蛙跳算法的变体进行比较以验证模因组搜索新策略的有效性.通过对大量实例的计算实验结果表明,模因组搜索新策略有效,改进蛙跳算法能有效求解分布式两阶段混合流水车间调度问题.     

作业车间调度问题的一种混合式算法

描述了一种解决作业车间调度最短完工时间问题的混合式算法．该算法基于禁忌搜索和转换瓶颈技术．算法中利用了多种禁忌搜索方法．为了得到更好的结果，算法中还引入了倒转技术．从对一组问题基准实例的实验计算结果看，该算法在合理的计算时间内，对多个实例得到比当前解决该问题的最高效的启发式算法之一的TSSB算法更好的结果．     

Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem

We consider the problem of scheduling a number of jobs on a number of unrelated parallel machines in order to minimize the makespan. We develop three heuristic approaches, i.e., a genetic algorithm, a tabu search algorithm and a hybridization of these heuristics with a truncated branch-and-bound procedure. This hybridization is made in order to accelerate the search process to near-optimal solutions. The branch-and-bound procedure will check whether the solutions obtained by the meta-heuristics can be scheduled within a tight upper bound. We compare the performances of these heuristics on a standard dataset available in the literature. Moreover, the influence of the different heuristic parameters is examined as well. The computational experiments reveal that the hybrid heuristics are able to compete with the best known results from the literature.