A Truncated Sum of Processing‐Times–Based Learning Model for a Two‐Machine Flowshop Scheduling Problem

Scheduling with learning effects has gained increasing attention in recent years. A well‐known learning model is called “sum‐of‐processing‐times‐based learning” in which the actual processing time of a job is a nonincreasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Moreover, the concept of learning process is relatively unexplored in a flowshop environment. Motivated by these observations, this article addresses a two‐machine flowshop problem with a truncated learning effect. The objective is to find an optimal schedule to minimize the total completion time. First, a branch‐and‐bound algorithm incorporating with a dominance property and four lower bounds is developed to derive the optimal solution. Then three simulated annealing algorithms are also proposed for near‐optimal solution. The experimental results indicated that the branch‐and‐bound algorithm can solve instances up to 18 jobs, and the proposed simulated annealing algorithm performs well in item of CPU time and error percentage. © 2011 Wiley Periodicals, Inc.     

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算法.     

Two–machine flowshop minimum–length scheduling problem with random and bounded processing times

We address the two–machine flowshop scheduling problem to minimize makespan where jobs have random and bounded processing times. The probability distributions of job processing times are unknown and only the lower and upper bounds of processing times are given before scheduling. In such cases there may not exist a unique schedule that remains optimal for all possible realizations of processing times, and therefore, a set of schedules has to be considered which dominates all other schedules. In this paper, we find some sufficient conditions for the considered problem.     

基于遗传算法的混合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.     

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

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

一种求解车间调度的混合算法

针对流水车间作业调度问题, 提出了一种基于``alldifferent'约束的混合进化算法(Hybrid particle and genetic algorithm, HPGA), 将粒子群算法、遗传操作及模拟退火策略有效地结合在一起. 为了提高算法的求解质量, 引入了一种随机邻域搜索策略. 最后将此算法在不同规模的实例上进行了测试, 并与其他几种最近提出的具有代表性的算法进行了比较. 结果表明, 无论是在求解质量还是收敛速度方面都优于其他几种算法.     

The Quay Crane Scheduling Problem

The recent growth in worldwide container terminals’ traffic resulted in a crucial need for optimization models to manage the seaside operations and resources. Along with the recent increase in ship size and the container volume, the advancements in the field of Quay Crane Scheduling introduced the need for new modeling approaches. This is the motivation behind the current paper, which focuses on developing a novel yet simple formulation to address the Quay Crane Scheduling Problem (QCSP). The objective of the problem is to determine the sequence of discharge operations of a vessel that a set number of quay cranes will perform so that the completion time of the operations is minimized. The major contribution is attributed to the way that minimization is performed, which is by minimizing the differences between the container loads stacked over a number of bays and by maintaining a balanced load across the bays. Furthermore, important considerations are taken into account, such as the bidirectional movement of cranes and the ability to travel between bays even before completion of all container tasks. These realistic assumptions usually increase model complexity; however, in the current work this is offset by the novel simple objective. This paper presents a mixed-integer programming (MIP) formulation for the problem, which has been validated through multiple test runs with different parameters. Results demonstrate that the problem is solved extremely efficiently, especially for small problem sizes.     

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.     

量子萤火虫算法及在无等待流水调度上的应用

针对无等待流水车间调度问题,提出了一种新颖的量子萤火虫优化算法用于最小化总完工时间．首先,将量子进化机制嵌入萤火虫算法中,并设计一种快速的局部邻域搜索方法,在每次迭代时只搜索部分邻域,同时采用目标增量计算邻域解变化,这样极大地加快了算法迭代速度,加速了算法收敛．最后,应用Taillard基准测试实例仿真,与目前较优的启发式算法IHA（improved heuristic algorithm）和群智能算法DGSO（discrete glowworm swarm optimization）、 GA-VNS（genetic algorithm-variable neighborhood search）及DHS（discrete harmony search）相比较,产生最好解的平均百分比偏差均下降了40％以上．实验结果验证了所提算法在求解无等待流水调度中的优越性．     

实时无等待HFS调度的一种拉格朗日松弛算法

研究了实时无等待HFS调度问题,并建立一个整数规划模型,提出运用拉格朗日松弛算法来求解,在此算法中,常采用次梯度方法更新拉格朗日乘子,但它随着迭代数的增加收敛速度会减慢,因此设计了一个改进的bundle方法。将以前的次梯度累积到bundle中,以获得一个更好的乘子更新方向．仿真实验表明,与次梯度方法相比,所设计的bundle法不仅在较少的迭代数内得到了更快的收敛速度而且改进了优化性能,对于大规模问题效果更为显著。     

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.     

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

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

一种适于异构环境的任务调度算法

针对异构环境独立任务调度问题提出两个调度原则,并基于Min-min算法提出优先级最小最早完成时间算法(Priority min-min,PMM).该算法将任务在各处理机上执行时间的标准误差作为任务的优先级.选取最早完成时间较小的k个任务,优先调度其中优先级最高的一个.在实验基础上分析了参数$k$对PMM算法性能的影响. PMM算法克服了min-min算法单纯追求局部最优的局限性,更适合于异构环境.实验数据表明PMM算法能有效地降低调度跨度,其性能比min-min算法有明显提高.     

图形处理中一类 Flow-shop 问题的改进算法

考虑图形处理中的一类两台处理器上的Flow-shop调度问题, 目标是极小化最早完工时间. 每个任务包含两道工序, 第一道工序可以在两台处理器中的任何一台上处理, 而第二道则只能在第二台处理器上处理, 且必须在第一道工序完工之后才能进行. 对该问题, 设计了一个改进的多项式时间近似算法, 在绝对性能方面, 该算法的最坏情况界为3/2; 而从实例计算的平均效果方面, 该算法所得的结果比原有的贪婪算法所得的结果要好20% 左右.     

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

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

On the Use of Genetic Algorithm for Solving Re-entrant Flowshop Scheduling with Sum-of-processing-times-based Learning Effect to Minimize Total Tardiness

Most research studies on scheduling problems assume that a job visits certain machines only one time. However, this assumption is invalid in some real-life situations. For example, a job may be processed by the same machine more than once in semiconductor wafer manufacturing or in a printed circuit board manufacturing machine. Such a setting is known as the “re-entrant flowshop”. On the other hand, the importance of learning effect present in many practical situations such as machine shop, in different branches of industry and for a variety of corporate activities, in shortening life cycles, and in an increasing diversity of products in the manufacturing environment. Inspired by these observations, this paper addresses a re-entrant m-machine flowshop scheduling problems with time-dependent learning effect to minimize the total tardiness. The complexity of the proposed problem is very difficult. Therefore, in this paper we first present four heuristic algorithms, which are modified from existing algorithms to solve the problem. Then, we use the solutions as four initials to a genetic algorithm. Finally, we report experimental performances of all the proposed methods for the small and big numbers of jobs, respectively     

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

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