带有并行机的混合Job Shop调度问题

本文分析带有并行机的混合JobShop调度问题并建立其模型,利用改进的遗传算法求解问题,在算法设计中,采用基于工序的编码方式,分两步进行解码,给出相关的遗传操作,列举实例说明带有并行机的混合JobShop调度问题,并针对实例进行仿真实验验证算法和编码方式的有效性和可行性,最后指出进一步的研究方向.     

带有交货期窗口的单机加权提前／拖期调度问题研究

提前/拖期调度在JIT生产中具有重要意义,带有交货期窗口的调度问题是一个更一般的问题,但目前尚缺乏有效的求解方法.本文提出一种求解带有交货期窗口的单机提前/拖期调度问题的遗传算法,是为克服简单遗传算法的早熟收敛现象而提出的一种新型的遗传算法,并用大量随机产生的实例进行了仿真研究,结果表明,本文提出的算法是有效的.     

多群体并行遗传算法在动态车间调度中的应用

生产调度对企业的生产作业过程具有重要的作用。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。本文论述利用多群体并行遗传算法可满足动态车间调度的应用,采用一种特殊构造遗传编码方法采改进遗传算法,提供有效的最优化查询。利用MATLaB工具以实例证明该算法的有效性。该算法特别适合于job-shop调度问题。     

资源约束下多项目调度的改进遗传算法

针对资源约束下的多项目调度问题,在前人提出的有效的启发式算法研究路径基础上,本文利用遗传算法,结合进度生成机制,提出了多项目调度的改进遗传算法。与其他多项目调度启发式算法相比,该算法在平均项目延迟和最佳解比例方面都表现较好,综合利用优化后的优先规则也使得该算法更适用于不同网络复杂度和不同资源约束程度的多项目调度问题中。     

基于软逻辑关系的重复性项目调度工期:费用优化研究北大核心CSCDCSSCI

为了满足重复性项目调度对工作连续性的要求,研究基于软逻辑关系的重复性项目调度时间-费用优化问题,从重复性项目调度工期-费用效用最大化角度,分析软逻辑关系对重复性项目调度方案的影响。构建基于软逻辑关系的重复性项目调度时间-费用优化模型,引入云模型理论,利用云模型云滴的随机性和稳定倾向性的特性,对遗传算法的交叉操作和变异操作进行改进,设计能满足重复性项目调度软逻辑关系约束的云遗传算法。结果表明,引入软逻辑关系,增强了项目调度的灵活性;以工期-费用效用最大化为目标,可有效缩短项目工期并降低项目的总费用。     

基于遗传算法的资源约束型项目调度优化

资源约束型项目调度的优化是一个NP-hard问题,其求解难度随着资源约束项的增多呈指数方式增长,传统的基于Excel表的手工优化方法不能及时计算出有效的资源配置方式,从而影响项目管理人员的资源调度.针对多资源约束型项目调度的优化问题提出基于遗传算法的资源约束型项目调度的优化方法,该算法采用基于活动优先权的十进制编码方式,结合活动的存储邻接矩阵,有效地解决活动调度违例现象;运用优先抢占模式的资源分配方式安排活动资源,避免资源分配中的冲突问题;并为该算法设计了启发式遗传算法的C语言程序,通过计算机的多次迭代运算得出满足资源约束的最优工期.实践结果表明,遗传算法可以快速有效地解决企业项目调度的优化问题,适合在企业项目进度管理中推广运用.     

准时生产方式下混流装配线的调度问题

混流装配线的调度问题是 JIT生产方式中的一个重要问题 .本文建立了多级混流装配线的调度模型 ,其目标是使不同生产级上各零部件的消耗量尽可能保持均匀 ,并用遗传算法和模拟退火进行求解 .试验表明 :遗传算法和模拟退火算法的求解质量比“目标追随法”有所提高     

一种基于带熵的遗传算法在车间调度中的应用

车间调度问题是现代制造业快速发展的瓶颈因素,因此提高车间调度的效率和有效性就成了生产制造领域大家普遍关注的问题。现行的车间调度问题遗传算法已经不能满足现代制造业快速发展的要求,多因为其静态性或效率差,表现为早熟或收敛停滞,究其根本原因还是GA的最优参数的选取问题,本文引入了信息熵的概念,以动态调整交叉概率和变异概率,从而给出了可以快速获得最优解的自适应遗传算法,并对此改进算法加以实例仿真验证其有效性。     

基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

基于扩展知识遗传算法的生产调度研究

本文介绍了用于解决实际生产调度问题的一种改进的遗传算法 ,此方法基于具体问题领域知识的扩展 ,用直接染色体表示生产调度 ,设计并扩展重组算子 ,缩小寻优空间 ,提高效率 ,并用算例证实此算法具有全局寻优性和收敛性     

Separating online scheduling algorithms with the relative worst order ratio

The relative worst order ratio is a measure for the quality of online algorithms. Unlike the competitive ratio, it compares algorithms directly without involving an optimal offline algorithm. The measure has been successfully applied to problems like paging and bin packing. In this paper, we apply it to machine scheduling. We show that for preemptive scheduling, the measure separates multiple pairs of algorithms which have the same competitive ratios; with the relative worst order ratio, the algorithm which is “intuitively better” is also provably better. Moreover, we show one such example for non-preemptive scheduling.     

A Tighter Extra-Resource Analysis of Online Deadline Scheduling

This paper is concerned with online algorithms for scheduling jobs with deadlines on a single processor. It has been known for long that unless the system is underloaded, no online scheduling algorithm can be 1-competitive, i.e., matching the performance of the optimal offline algorithm. Nevertheless, recent work has revealed that some online algorithms using a moderately faster processor (or extra processors) can guarantee very competitive performance Kalyanasundaram and Pruhs, 2000 or even be 1-competitive Koo et al., 2002; Lam and To, 2001. This paper takes a further step to investigate online scheduling algorithms with an even higher performance guarantee (i.e., better than 1-competitive algorithms) and in particular, presents an extra-resource analysis of the earliest-deadline-first strategy (EDF) with respect to such a higher performance guarantee.A preliminary version of this paper has been accepted by The Australian Theory Symposium on Computing, 2004.This research was supported in part by Hong Kong RGC Grant HKU-7024/01E.     

Randomized Online Scheduling with Delivery Times

We study one of the most basic online scheduling models, online one machine scheduling with delivery times where jobs arrive over time. We provide the first randomized algorithm for this model, show that it is 1.55370-competitive and show that this analysis is tight. The best possible deterministic algorithm is 1.61803-competitive. Our algorithm is a distribution between two deterministic algorithms. We show that any such algorithm is no better than 1.5-competitive. To our knowledge, this is the first lower bound proof for a distribution between two deterministic algorithms.     

Semi-online scheduling with “end of sequence” information

We study a variant of classical scheduling, which is called scheduling with “end of sequence” information. It is known in advance that the last job has the longest processing time. Moreover, the last job is marked, and thus it is known for every new job whether it is the final job of the sequence. We explore this model on two uniformly related machines, that is, two machines with possibly different speeds. Two objectives are considered, maximizing the minimum completion time and minimizing the maximum completion time (makespan). Let s be the speed ratio between the two machines, we consider the competitive ratios which are possible to achieve for the two problems as functions of s. We present algorithms for different values of s and lower bounds on the competitive ratio. The proposed algorithms are best possible for a wide range of values of s. For the overall competitive ratio, we show tight bounds of ϕ + 1 ≈ 2.618 for the first problem, and upper and lower bounds of 1.5 and 1.46557 for the second problem. The authors would like to dedicate this paper to the memory of our colleague and friend Yong He who passed away in August 2005 after struggling with illness. D. Ye: Research was supported in part by NSFC (10601048).     

Two new robust genetic algorithms for the flowshop scheduling problem

The flowshop scheduling problem (FSP) has been widely studied in the literature and many techniques for its solution have been proposed. Some authors have concluded that genetic algorithms are not suitable for this hard, combinatorial problem unless hybridization is used. This work proposes new genetic algorithms for solving the permutation FSP that prove to be competitive when compared to many other well known algorithms. The optimization criterion considered is the minimization of the total completion time or makespan (_Cmax$C_{\max }$). We show a robust genetic algorithm and a fast hybrid implementation. These algorithms use new genetic operators, advanced techniques like hybridization with local search and an efficient population initialization as well as a new generational scheme. A complete evaluation of the different parameters and operators of the algorithms by means of a Design of Experiments approach is also given. The algorithm's effectiveness is compared against 11 other methods, including genetic algorithms, tabu search, simulated annealing and other advanced and recent techniques. For the evaluations we use Taillard's well known standard benchmark. The results show that the proposed algorithms are very effective and at the same time are easy to implement.     

决策支持系统的自适应建模研究及应用实例分析

在进行决策的过程中 ,建立正确的系统模型是解决问题的关键 .由于多方面的原因 ,有时要针对研究对象选用适用的模型来进行分析是很困难的 .本文根据遗传算法在程序设计中的应用 ,探讨了基于遗传算法的自适应建模方法 ,并对实际应用中自适应建模的算法存在的问题提出了改进方法 .最后应用自适应建模方法对全国的集装箱与外贸数据进行了建模分析 ,应用实例表明自适应建模方法对于解决难以选择合适的模型进行建模分析时是很有效的     

Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability

In this paper, we present closed-form expressions, wherever possible, or devise algorithms otherwise, to determine the expectation and variance of a given schedule on a single machine. We consider a variety of completion time and due date-based objectives. The randomness in the scheduling process is due to variable processing times with known means and variances of jobs and, in some cases, a known underlying processing time distribution. The results that we present in this paper can enable evaluation of a schedule in terms of both the expectation and variance of a performance measure considered, and thereby, aid in obtaining a stable schedule. Additionally, the expressions and algorithms that are presented, can be incorporated in existing scheduling algorithms in order to determine expectation-variance efficient schedules.     

项目调度中的时间-费用权衡问题研究综述

项目管理中,通过增加额外费用来加速执行项目的某些活动,以此达到缩短项目工期的目的,这就是在项目调度文献中被广泛研究的时间-费用权衡问题.这篇文章将时间-费用权衡问题分为两类来研究:第一类是活动的执行时间和费用之间有连续函数关系的连续时间-费用权衡;第二类为时间和费用之间没有函数关系的离散时间-费用权衡.详细介绍离散时间-费用权衡问题近10年的研究进展,包括问题的求解算法、模型改进等.从更贴近实际项目实施的角度,介绍了具有时间转换约束的离散时间-费用权衡问题.最后,指出了时间-费用权衡问题需要进一步研究的几个方向.     

Almost optimal solutions for bin coloring problems

In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT+2 and OPT+1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio. The research of this paper was partially supported by an NSF CAREER award CCF-0546509.