线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题。在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数。考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量。第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间。对两类问题讨论了最优排序的某些特征。基于对问题的分析,分别给出了求解最优资源分配的方法。结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立。     

一类资源约束单机排序问题

讨论具有连续资源的单机排序问题．在这一模型中，工件的释放时间是所消耗资源的非负严格减少连续函数，工件的加工时间是开工时间的严格增加线性函数．考虑两类问题，第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量、第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间．对两类问题讨论了最优排序的某些特征．基于对问题的分析，分别给出了求解最优资源分配的方法．结果表明，加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立。     

加工时间依赖开工时间的FlOW ShoP调度问题

讨论了加工时间依赖开工时间的Flow shop 调度问题。在这类问题中,工件的加工时间是开工时间的简单线性函数,机器间满足某种优势关系。对于这类问题,当目标函数是极小化最大完工时间时,尽管比相应的经典问题复杂,但仍存在多项式算法。如果目标函数是极小化加权完工时间和或极小化最大延误,则经典问题中的结论未必成立。     

线性加工时间的树约束单机排序问题

研究工件具有线性加工时间、工件间优先约束为树约束的单机排序问题。目标函数为极小化加权完工时间和。在工件加工时间是其开工时间的线性函数的条件下，本文证明了最大家庭树中的工件优先于家庭树中的其它工件的加工，并且其工件连续加工所得到的排序为最优排序。     

具有优势机器和恶化工件的流水作业排序问题

针对流水作业排序问题,建立了具有优势机器和恶化工件并且有无空闲限制的排序模型.在该排序模型中,机器加工工件时,工件的相邻加工工序之间不允许出现空闲,工件的加工时间是其开工时间的严格增加线性函数.其中讨论的优势机器有2种情况:机器形成增减增优势关系和机器形成减增减优势关系.考虑了多台机器的流水作业排序问题,其中,目标函数分别为极小化最大完工时间和极小化总完工时间,对于这两类问题分别给出了求解最优排序的多项式算法和它们的计算复杂性,并通过证明证实了算法的有效性.     

考虑恶化和学习效应的单机成组排序问题

讨论了工件加工时间同时具有恶化和学习效应的单机成组排序问题。在这类问题中,同一组中的工件不允许分开加工,各组之间有安装时间,其中安装时间是工件组开始加工时间的简单线性函数,各组内工件的实际加工时间是关于恶化和学习效应的函数。对目标函数为最大完工时间和总完工时间两类问题分别给出了多项式时间最优算法。     

具有学习效应的平行机排序问题

针对具有学习效应的平行机排序模型,讨论了两类问题。在这一模型中,工件的实际加工时间不仅与其所在排序中的位置有关并且与其本身的学习率有关,对于在同一台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。第1类问题的目标函数是极小化提前与延误的加权和;第2类问题的目标函数是极小化提前与误工工件数的加权和。对这两类问题分别给出了多项式算法。     

一类带有安装时间的单机成组排序问题

针对一类带有准备时间和安装时间的单机成组排序问题,给出了求解最优排序的多项式算法。其中每个工件都具有自己的准备时间,组和组之间具有安装时间,并且安装时间和已经加工完工件的加工时间有关。所有工件在机器上加工时,一次只能加工一个工件,工件不可中断,组内工件连续加工,组和组之间需要安装时间。对目标函数为极小化最大完工时间的单机成组排序问题,给出了求解最优排序的多项式算法。原问题不是成组问题,为此在原问题的基础上添加了工件的成组问题且组内每个工件都具有自己准备时间,其结果是依然能给出求解最优排序的多项式算法。     

链约束线性加工时间单机排序问题

讨论工件具有线性加工时间,工件间具有链约束的单机排序问题。目标函数为极小化加权完工时间和。在这类问题中,工件的加工时间是其开工时间的线性函数。对链不允许中断和链允许中断两种情况分别给出了最优算法。     

极小化不可行量函数的Flow Shop变异问题

讨论一类Flowshop的变异问题。在这类变异问题中 ,给定一个截止工期 ,该工期比Flowshop最优调度中的最大完工时间小。讨论的问题是在全部工件的完工时间不超过截止工期的限制下 ,极小化不可行量函数。这类问题与矩阵函数因子分解有着密切联系。基于对问题的分析 ,证明了这一问题等价于单机调度中极小化类似的延迟量函数。推广了已有的结论。     

加工时间依赖于资源消耗量的平行机调度问题

研究了一类平行机调度问题,其中假定作业加工时间是资源消耗量的线性减函数,调度的目标是在限定最大完工时间时最小化资源消耗总量. 分析了对应单机问题的最优算法和下界构造方法,进而提出了两个优化策略用于构造模拟退火算法和禁忌搜索算法.考虑了多种最大完工时间限制情形, 构造了大量随机实验数据,对算法解的精确度及计算效率进行了测试.实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.     

加工时间带恶化和指数学习效应的成组排序

本文研究了成组技术下带依靠时间的线性恶化效应和依靠位置的指数学习效应的排序问题.模型中,组安装时间是开始安装时间的线性函数,工件的加工时间带线性恶化和指数学习效应,对最小化时间表长问题和最小化总完工时间问题分别给出了多项式算法.     

带搬运时间的批量生产制造系统生产作业计划方法

为给考虑搬运时间的批量生产制造系统中的同类型工件制定生产作业计划,对批量工件的加工与搬运时间、搬运车辆调度和工件移动方式决策等问题进行深入研究.构建同类型批量工件在不同移动方式中的加工与搬运时间模型并设计相应的计算流程图.建立基于生产周期和搬运车辆总投入数量两个决策目标的工件移动方式决策模型.研究结果表明:本研究可有效选择工件移动方式,可为考虑搬运时间的同类型批量工件制定精确的生产作业计划,并可对搬运车辆进行合理调度.     

SCHEDULING TWO GROUPS OF JOBS WITH INCOMPLETE INFORMATION

In real world situations, most scheduling problems occur neither as complete off-line nor ascomplete on-line models. Most likely a problem arises as an on-line model with some partialinformation. In this article, we consider such a model. We study the scheduling problem P(n_1,n_2),where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon asall jobs in the first group are assigned, the second job group appears. The objective is to minimize thelongest job completion time(makespan). We show a lower bound of 3/2 even for very special cases.Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed forthe general case. The main contribution of this paper is to discuss the impact of the quantity ofavailable information in designing an on-line algorithm. It is interesting to note that the absence ofeven a little bit information may significantly affect the performance of an algorithm.     

An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies

This paper is concerned with the fractional version of online hierarchical scheduling problem on uniform machines. In the problem, the jobs and machines have several different hierarchies and each job can be arbitrarily split between the machines with hierarchies not above the hierarchy of the job. The objective is to minimize the makespan. The authors present an optimal algorithm for the problem with three hierarchies.     

有模具约束的平行机台最小拖期和调度问题

针对某电器企业的一个瓶颈工序来制定调度方案,该问题归纳为平行机台具有模具约束,目标为最小拖期和的调度问题．本文提出了如下的启发式算法：根据模具情况运用成组技术对工作成组并生成运行表：按运行表顺序对各个运行中的工作进行指派机台,设置禁忌模具集合,避免对运行的短视性;根据工作的交货期和加工时间选择适当的机台进行加工;在各个机台运用ＮＢＲ（ＮｅｔＢｅｎｅｆｉｔｏｆＲｅｌｏｃａｔｉｏｎ）算法调节顺序以减少拖期和．该算法在厂家的实际测试中,通过三个不同的实例与手工排程进行了比较,各项指标均有明显优势．