A branch-and-bound algorithm for the three-machine flowshop scheduling problem with bicriteria of makespan andtotal flowtime

This paper addresses the three‐machine flowshop scheduling problem with a bicriteria of minimizing a weighted sum of makespan and total flowtime. Three lower bounds, an upper bound, and several dominance relations are developed. The upper bound is developed using a two‐phase hybrid heuristic method. A branch‐and‐bound algorithm, incorporating the developed bounds and dominance relations, is presented. An extensive computational analysis on randomly generated problems is conducted. The analysis indicates that the proposed bounds, dominance relations, and branch‐and‐bound algorithm are efficient.     

一个求解无等待流水调度问题混合算法

针对以总完工时间最小为目标的无等待流水调度问题提出一个启发式算法和禁忌搜索算法相结合的混合禁忌搜索算法HTS(Hybrid Taboo Search):以启发式算法产生的解作为初始解,通过禁忌搜索提高解的质量.实验结果表明:提出的HTS性能上优于经典的RC1、RC2、PH1(p)和DS算法.     

基于遗传算法的混合Flowshop调度

混合Flowshop调度问题,是一个NP完全问题,很难用一般的方法解决,文章提出了遗传算法求解混合Flow-shop调度问题的方法,给出了一种染色体表示方法,设计了相应的交叉和变异操作算子,这两种算子很容易保证个体的合法性,同时又具有遗传算法本身所要求的随机性。最后给出了一个较大规模的计算实例,仿真结果表明此算法是有效的。     

An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion

An ILS algorithm is proposed to solve the permutation flowshop sequencing problem with total flowtime criterion. The effects of different initial permutations and different perturbation strengths are studied. Comparisons are carried out with three constructive heuristics, three ant-colony algorithms and a particle swarm optimization algorithm. Experiments on benchmarks and a set of random instances show that the proposed algorithm is more effective. The presented ILS improves the best known permutations by a significant margin.     

Scheduling with general position-based learning curves

Learning effect in scheduling problems has received growing attention since Biskup [3] introduced the position-based model, where the learning curve is expressed as a power function of a job position. Hurley [11] pointed out that the actual processing time of a given job drops to zero precipitously as the number of jobs increases in the standard power model. Moreover, the learning rates show considerable variation within industries or firms. The variation extends not only across firms at a given time, but also within firms over time. For instance, the learning curves usually have an initial downward concavity, and no further improvements are made after some amount of production. Beside the standard power model, learning curve is seldom discussed in scheduling. In this paper, we offer a surprising simple yet realistic learning effect model which has the flexibility to describe different learning curves easily. For instance, the standard power model, the well-known S-shaped and the plateau functions are special cases of the proposed model. We then present the optimal solution for some scheduling problems.     

Scheduling algorithms for a semiconductor probing facility

This paper focuses on a scheduling problem in a semiconductor wafer probing facility. In the probing facility, wafer lots with distinct ready times are processed on a series of workstations, each with identical parallel machines. We develop a heuristic algorithm for the problem with the objective of minimizing total tardiness of orders. The algorithm employs a bottleneck-focused scheduling method, in which a schedule at the bottleneck workstation is constructed first and then schedules for other workstations are constructed based on the schedule at the bottleneck. For scheduling wafer lots at the bottleneck workstation, we consider prospective tardiness of the lots as well as sequence-dependent setup times required between different types of wafer lots. We also present a rolling horizon method for implementation of the scheduling method on a dynamic situation. The suggested methods are evaluated through a series of computational experiments and results show that the methods work better than existing heuristic methods.     

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

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

基于遗传算法的车间作业调度问题求解

文章提出了一个求解车间作业调度问题的完备的、强壮的遗传算法。在分析车间作业调度问题的数学模型的基础上,给出了:(1)采用分段结构的染色体编码思想;(2)生成可行调度的算法;(3)计算调度目标函数的算法;(4)三种遗传算子及其辅助算子———修正算子的设计。最后,通过仿真验证了算法的有效性和稳定性。     

Two-Machine Stochastic Flow Shops With Blocking and the Traveling Salesman Problem

The paper deals with the problem of minimizing the expected makespan in a two-machine flow shop with blocking and random job processing times. It is well known that it reduces to an instance of the traveling salesman problem (TSP). Assuming that the job processing times can be stochastically ordered on both machines, we show that the problem under study is equivalent to TSP on a permuted Monge matrix. This allows us to prove that it is NP-hard for the independently and exponentially distributed job processing times, and identify a new class of efficiently solvable special cases.     

Job-shop调度问题的一种遗传算法表示方法

提出了一种新的染色体表示方法以及相应的遗传操作算子,它们与少许的调整工作相结合,既使得在每次操作算子作用之后产生的新的个体是合法的,也使染色体与时间表产生一一对应的关系,完满地解决了Job-shop问题中关键的表示和操作问题。     

多处理器任务调度问题的新近似算法

研究任务有多种处理方式的多处理器任务调度问题（MTS）的求解算法，给出求解这种问题的二阶段方法：第1阶段为指派问题，第二阶段调度问题Pm｜fixj｜Cmax，从而得到一个新的求解Pm｜setj｜Cmax。近似算法的方法，并针对P4｜fixj｜Cmax给出了具体算法，证明这种近似算法是一个2-逼近度算法，是文献中在4-处理器问题上的推广。     

瓶颈指向的启发式算法求解混合流水车间调度问题

针对以最小化时间表长为目标的复杂混合流水车间调度问题,提出了一种将机器布局和工件加工时间特征紧密结合的启发式算法.首先,充分利用各阶段平均机器负荷一般不相等的特点确定瓶颈阶段,构建初始工件排序.其次,针对在瓶颈阶段前加工时间较短而瓶颈阶段后加工时间相对较长的工件,在第1阶段优先开始加工.同时,在瓶颈阶段前的每一个阶段,每当有工件等待加工或同时完工时,优先选择瓶颈阶段前剩余加工时间最短的工件加工;在瓶颈阶段以及瓶颈阶段之后,则优先选择这台机器后剩余加工时间最长的工件加工.最后,采用工件交换和插入操作改进初始调度.用Carlier和Neron的Benchmark算例测试提出的启发式算法.将计算结果与NEH启发式算法进行了比较,平均偏差降低了0.0555%,表明这个启发式算法是有效的.     

A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application

The assembly flowshop scheduling problem has been addressed recently in the literature. There are many problems that can be modeled as assembly flowshop scheduling problems including queries scheduling on distributed database systems and computer manufacturing. The problem has been addressed with respect to either makespan or total completion time criterion in the literature. In this paper, we address the problem with respect to a due date-based performance measure, i.e., maximum lateness. We formulate the problem and obtain a dominance relation. Moreover, we propose three heuristics for the problem: particle swarm optimization (PSO), Tabu search, and EDD. PSO has been used in the areas of function optimization, artificial neural network training, and fuzzy system control in the literature. In this paper, we show how it can be used for scheduling problems. We have conducted extensive computational experiments to compare the three heuristics along with a random solution. The computational analysis indicates that Tabu outperforms the others for the case when the due dates range is relatively wide. It also indicates that the PSO significantly outperforms the others for difficult problems, i.e., tight due dates. Moreover, for difficult problems, the developed dominance relation helps reduce error by 65%.     

改进遗传算法及其在带有目标是最小平均总流程时间的流水调度排序中的应用

提出了一个改进遗传算法的结构,并且应用于带有目标是最小平均总流程时间的流水调度排序中.为了改进一般遗传算法的程序,两个新的操作被引进到这个操作中.这两个操作为:1) 过滤操作:过滤掉在每一代中的最坏的个体,用前一代中的最好的个体替代它;2) 培育操作:当在一定代数内算法不改进时,选择一个培育操作用于培育最有希望的个体.通过大量的随机产生的问题的例子的计算机实验显示出,提出的算法的性能明显好于一般遗传算法,并且和此问题的最好的专门意义的启发式算法相匹配.新的MGA框架很容易扩展到其它最优化当中,只是实施的详细的步骤有所不同.     

多阶段混合Flow Shop调度问题及其遗传求解算法

针对多阶段混合Ｆｌｏｗ Ｓｈｏｐ 调度问题的一般结构和不同的调度目标函数,提出混合整数规划模型,并基于问题的结构特点设计了遗传求解算法。计算实验结果表明,遗传算法对于不同规模和结构的问题具有良好的适应性和求解性能     

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

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

A genetic algorithm for the Flexible Job-shop Scheduling Problem

In this paper, we present a genetic algorithm for the Flexible Job-shop Scheduling Problem (FJSP). The algorithm integrates different strategies for generating the initial population, selecting the individuals for reproduction and reproducing new individuals. Computational result shows that the integration of more strategies in a genetic framework leads to better results, with respect to other genetic algorithms. Moreover, results are quite comparable to those obtained by the best-known algorithm, based on tabu search. These two results, together with the flexibility of genetic paradigm, prove that genetic algorithms are effective for solving FJSP.     

求解车间调度问题的2阶段混合粒子群优化算法

针对车间调度问题,提出了一种2阶段混合粒了群算法(TS-HPSO).该算法在第1阶段为每个粒子设置较大的惯性系数w,同时去掉了粒子的社会学习能力,从而保证每个微粒在局部范围内充分搜索.第2阶段的混合粒子群算法以第1阶段每个粒子找到的最好解作为初始解,同时以遗传算法中的变异操作保证粒了多样性;为保证算法的寻优能力,对全局gbest进行贪婪邻域搜索.计算结果证明了本算法的有效性.