On-Line Scheduling with Rejection on Identical Parallel Machines

In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.     

相同并行机上工件排序问题的一种新算法

根据工件排序问题的特点,建立了在相同种类的并行机上加工一批相同种类工件的优化数学模型。在蚂蚁系统的基础上对其进行了改进,并把改进的蚂蚁系统用于工件排序问题的优化中。通过与其他算法的仿真比较表明,该基于蚂蚁系统的算法是有效的,特别是问题规模很大时更显示其较快的收敛速度和较高的精度。     

同类机半在线排序问题及其近似算法

研究两台同类机系统两个半在线排序问题 .第一个为总加工时间已知 ,第二个为最大工件加工时间已知 .对这两个问题 ,文章给出了各自的近似算法 ,证明了它们的最坏情况界分别为 3和3/2 .文章还研究了上述问题的下界并与我们的算法的最坏情况界进行了比较.     

A Job Scheduling Model and Heuristic Algorithm for Minimizing the Range of Lateness and Makespan on Parallel Machines

ＡＪｏｂＳｃｈｅｄｕｌｉｎｇＭｏｄｅｌａｎｄＨｅｕｒｉｓｔｉｃＡｌｇｏｒｉｔｈｍｆｏｒＭｉｎｉｍｉｚｉｎｇｔｈｅＲａｎｇｅｏｆＬａｔｅｎｅｓａｎｄＭａｋｅｓｐａｎｏｎＰａｒａｌｅｌＭａｃｈｉｎｅｓ⒇ＨＵＡＮＧＤｅｃａｉＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉ...     

最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法

分析了岸桥支援对船舶装卸作业效率的影响,指出减少岸桥等待时间,有利于加强岸桥支援,并能提高码头整体运作效率。考虑岸桥作业不可相互穿越与安全距离等特有约束,建立了岸桥作业调度双目标混合整数规划模型,其优化目标是最小化最大完工时间与岸桥等待时间。针对该问题的NP-hard特性,设计了一种遗传算法,对算法搜索空间进行了讨论,并推导了问题的一个下界。数据实验表明,所建立的模型能够在最小化最大完工时间的同时,有效地减少岸桥等待现象的发生,其算法在允许的运算时间内能获得稳定的满意解。     

含有到达时间的最大完成时间同类机调度算法

研究了目标函数是最小最大完成时间的同类机调度问题,其中作业到达时间可能不同。此问题被证明是NP-hard问题。通过对单机和同型机的相应问题研究成果的推广,提出5个启发式算法,给出算例及其计算结果,并通过实验对算法的性能及算法适应的情形进行了分析,与现有Koulamas＆Kyparisis的算法进行了比较。     

混合装配流水线上最小makespan的协同优化

混合装配流水线是实现快速响应的一种多品种小批量的生产组织方式,流水线平衡和产品排序是紧密相关而且对目标值存在交互影响作用的两个NP-hard问题.文章分析了流水线平衡与产品排序对流水线的makespan目标的交互影响,建立了优化模型;基于两个问题的交互影响,采用协同进化算法,并行协同地优化混合装配流水线上的makespan.通过对经典流水线问题的计算实验,并与串行独立优化方法对比,结果表明:并行协同优化是一种全局优化方法,能够克服后者的局限性,改善优化的结果,进一步地,文中对混合装配流水线上makespan的协同优化方法可以推广到Flowshop的优化中去.     

On-Line Scheduling of Unit Time Jobs with Rejection on Uniform Machines

The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is 1/2 （2 W √3） ≈ 1.86602.     

Semi On-Line Scheduling Problem for Maximizing the Minimum Machine Completion Time on Two Uniform Machines

Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi. Our goal is to maximize the Cmin. We give a Cmin 2 algorithm and prove its competitive ratio is at most 2s＋1/s＋1 We also claim the Cmin 2 algorithm is tight and the gap between the competitive ratio of Cmin2 algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s =1.     

并行多机加权成套订单数极大化的混合遗传算法

从实际应用出发,提出了在相同的并行机上加权成套订单数极大化的排序问题,建立了该问题的整数规划模型,并设计了一种有效的混合遗传算法.还通过一个算例对这类排序问题和所提出的算法进行了说明,计算结果表明了该算法的有效性.     

Heuristics for Online Scheduling on Identical Parallel Machines with Two GoS Levels

This paper considers the online scheduling problem on m(m ≥ 3) parallel machines(the first k machines with grade 1 and the remaining m-k machines with grade 2) with two Go S levels and makespan as the objective function. The jobs arrive over time with grade 1 or 2 and an arrival job can be assigned to a machine only when the grade of the job is no less than the grade of the machine. Three cases are considered:(i) For k = 1, the authors present an online algorithm with competitive ratio of9/5.(ii) For 1 k m-1, an online algorithm with competitive ratio of 2.280 is proposed.(iii)For k = m-1, an online algorithm is presented with competitive ratio of 2. All the three algorithms are based on greedy algorithm with a similar structure. At last, numerical instances are given and the average competitive ratios of the instances show good performance of the proposed algorithms.     

不确定加工时间下同型并行机的鲁棒排程

在现实作业排程中,工件加工时间常常是不确定的。考虑到同型并行机的现实和理论意义,本文研究了加工时间不确定情况下以工期(最大完工时间)为目标的同型并行机排程问题。为了确定最优鲁棒排程,采用最小最大遗憾准则。其中,加工时间没有给出概率信息,而是用区间表示。经证明,该问题是一个NP-难问题且求解困难。为简化问题便于求解,本文给出了最大遗憾的计算公式,还证明出最坏情景出现在端点值,即各工件加工时间不是取区间上界就是下界。然后,提出了一种可以求出该问题最优解的迭代松弛算法并分析了其计算量。最后总结了本文的主要研究工作以及未来的研究方向。     

带强制工期的单机排序问题

讨论了带强制工期的n个工件在单机上加工,在允许机器空闲的条件下,使得最大提前完工时间最小。由于工件不允许延迟,问题可能会无可行排序。先讨论问题的可行性。如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后判断预排序列是否为最优,如果不能直接确定为最优,则给出一个算法在多项式时间内尝试由预排序列开始,通过不断调整工件的次序来获得最优排序。     

并联系统预防性维修费用的优化方法

主要针对并联系统建立了有限时间区间的预防性维修优化模型，该模型充分考虑到预防维修可以提高系统生产效益的同时，其故障率会随着维修次数的增加而上升，引入役龄回退因子对预防维修活动前后系统性能的动态变化进行了描述，而且还将系统可靠度作为约束条件。在运用遗传算法进行优化求解的基础上，研究了系统总维修费用随可靠度的变化率，对其进行了深入分析，实例验证了该优化模型的正确性。     

A Heuristic for the Job Scheduling Problem with a Common Due Window on Parallel and Non-Identical Machines

1. INTroDUCTIONThe emergence of JIT (Just in Time) management tee~gy opens up a recency research field for the jobscheduling and production managemellt. As its farther develOPment, the earnness-tardiness job schedulingproblem becomes a hot research point over y6ars. conference [1] gives a review on job scheduling problem withearnness and tardiness penalties. Reference [2] p~s another scheduling problem for minimizing the rangeof lateness on a single machine, and reference [3] giVes a he…     

一类有动态时间窗的并行多机启发式调度算法

航班过站服务中的货邮装卸作业调度是一类有时间窗和作业调整时间的多目标多设备并行作业动态排序问题，其特点是作业时间窗和服务作业时间动态变化。在分析区别于一般制造业生产作业排序特点的基础上，建立了服务作业的调度模型．提出了设备能力差的概念．给出一个考虑不同设备加工能力的启发式分配法。当时间窗或服务时间发生变化时，算法只需要修改判断矩阵中的一行或一列数据，而对算法运行的效率没有影响。算例分析显示，能力差分配算法在减少航班延误数量、时间压设备生产能力平衡上均优于目前使用的先到先服务和最小负荷调度的混合算法。     

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

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

一类带缓冲区的连续生产过程的最速生产调度

研究了一类有分段式生产任务并带缓冲区域束的连续生产最早完工（Ｍａｋｅｓｐａｎ）指标调度问题,对积分形式约束和专注生产的约束进行有效转化,将原调度总理２转换为线性规划问题,仿真算表明了文中方法是可行的。     

基于JIT的多目标并行多机调度问题的混合遗传算法

针对一类极小化 makespan和延迟区间的并行多机零件排序问题 ,设计了一个混合遗传算法 .该算法的特点是充分利用求解单机问题的最优有效算法 ,设计了一种简单的编码方案 ,简化了算法的实现难度 ,提高了算法的执行效率 .数值仿真实验表明 ,该算法具有收敛速度快、优化效果好等特点 ,且适合于求解大规模问题 .     

用遗传算法解决在并行机上带有不同交货期窗口的Job-Shop调度问题

本文讨论了不同交货期窗口下的提前／拖期并行机调度问题,提出了染色体用工件编号进行编码规则,给出了用稳步遗传算法求解上述问题的方法,仿真实验表明了算法及编码规则的可行性和有效性。