以延迟和延误为第1目标的约束多目标排序问题

多目标排序是研究多个优化目标的排序问题,它在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。1956年Smith研究在没有工件误工的、所谓"完美的"(perfect)排序中寻找使平均完工时间为最小的排序问题,开创了研究多目标排序的先河。然而,在实际问题中往往是允许工件误工的,也就是说,工件可以在交货期之后完工,即允许工件有延迟或者延误,只是针对不同的问题对工件的延迟或者延误有不同的要求。研究以延迟和延误为第1目标的四个约束多目标排序问题,在最大延迟L_(max)、总延迟∑L_j、最大延误T_(max)或者总延误∑T_j不超过给定的量的约束条件下,寻找使平均完工时间为最小的排序,分别提出相应的算法。     

在误工工件个数最少的条件下使最大延误为最小的分支定界算法

多目标排序是研究多个优化目标的排序问题,在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。2007年有文献证明以误工工件个数最少为第l目标、使总完工时间最小或者使总延误最小的多重目标排序问题1‖（∑Cj／∑uj）或者1‖（∑Tj／∑Uj）都是NP困难的。然而,迄今为止,对于以误工工件个数最少为第1目标、使最大延误最小的多重目标排序问题1‖（Tmax／∑Uj）的计算复杂性还不清楚。给出了这个多重目标排序问题1‖（Tmax/／∑Uj）的分支定界算法,借助几个性质,得到较好的上下界,能够较快地得到最优解。     

误工工件个数最少的多目标排序问题

考虑在误工工件个数最少的约束条件下使得工件集合的总完工时间为最小的单台机器多目标排序问题.首先要使得误工工件个数∑Uj为最少,著名的Moore-Hodgson算法得到的排序就是一个可行解,并且该算法在遇到误工工件时总是尽可能把加工时间最长的工件放到误工工件集合L中,这也符合使总完工时间∑Cj为最小的目的.然而以往文献中的例子显示,这样得到的解并不总是最优解,这就暗示了该问题的复杂性,因此给出了不同于以往文献的分支定界算法及其Matlab解,简化了计算过程.     

交货时间区间内完工工件个数最多的近似算法

在现代生产管理中,合理安排工件使所加工的工件准时交货是极其重要的,工件提前完工和延误完工都会增加费用,使尽量多的工件在其对应交货时间区间内完工的排序问题是NP困难的。本文讨论了m台平行机交货时间区间内完工工件个数最多的排序问题,给出了一个求解这一问题的多项式时间近似算法。     

基于累计按期完工概率增量的一个排序算法

讨论工件加工时间为随机变量的单机静态列表排序极大化期望按期完工工件数问题。对于单机排序加工时间为独立同分布随机变量问题1／Xi-F／E∑Uj以及EXi≥EXjD di≤dj时，该文给出了预期按期完工工件和预期误工工件的最优划分算法。对于一般问题，对给定的置信度，该文采用倒序算法逐个剔除累计按期完工概率增量最大工件，完成预期按期完工工件集与预期误工工件集的划分，并以此为依据给出排序，最后通过搜索最优置信系数得出排序结果。     

两个代理的单机排序问题研究

研究了两个代理的单机排序问题.其中第一个代理以完工时间和为目标函数,第二个代理以误工工件个数为目标函数.排序问题的目标是寻找一种排序,使得在第二个代理的目标函数不超过给定上界的情况下,第一个代理的目标函数最小.本文还对这一问题设计了一个拟多项式时间算法.     

工件可拒绝的单机无界平行批排序

首次考虑了目标函数为极小化最大延误与被拒绝工件的惩罚费用之和的单机无界平行批排序问题.证明了问题1｜B≥n,rej｜ Tmax+ TCP为NP-困难的,针对该问题给出了基于动态规划的伪多项式时间算法.     

加工时间基于学习因素的一类排序问题最优算法的证明

考虑了一类工件的加工时间基于学习因素,目标函数为极小化最大完工时间的单机排序问题,即随着加工时间的增加。工件的加工时间将减少．对于文献[Kuo Wen-Hung,Yang Dar-Li. Minimizing the makespan in a single machine scheduling problem with a time-based learning effect[J]. Information Processing Letters,2006,97（2）：64-67．仲提出的最优多项式时间算法,给出了一种更为简洁的证明．     

一类工件有尺寸且分两次到达的在线分批排序

研究了工件有尺寸大小,有到达时间的在线分批排序,目标函数为工件的极大完工时间。就所有工件有2个到达时间的在线分批排序,给出算法,并证明了算法的竞争比不超过3。     

有到达时间的可控的分批排序问题

把分批排序和可控排序问题相结合,讨论了加工时间可控的分批排序问题．目标函数是使最大完工时间和加工时间可控所需费用的总和最小．对工件具有动态的到达时间,设计多项式时间的动态规划算法。     

考虑第二优化目标的动态单机排序问题

对以最大滞后时间以及带权加工时间和为第二优化目标的动态单机排序问题１｜ｒｊ｜Ｃｍａｘ分别进行了探讨,并给出了相应的多项式算法。     

预防性维修计划和生产调度的多目标优化

为了降低设备故障对生产成本和生产时间的影响,建立了单台设备预防性维修计划和生产调度的多目标联合优化模型.将维修成本、生产任务的最大完成时间、加权总完工时间及加权总延迟时间作为优化目标.采用了多目标遗传算法,同时对预防性维修计划和生产调度进行优化.通过实例,将预防性维修计划、生产调度的多目标联合优化方法分别与单目标联合优...     

改善式BVEDA求解多目标调度问题

针对以最小化最大完工时间、最小化最大拖期和最小化总流程时间为目标的置换流水车间调度问题(permutation flow shop scheduling problem, PFSP),基于双变量分布估计法(bi-variable estimation of distribution algorithm, BVEDA)提出改善式双变量分布估计算法(Improved BVEDA, IBVEDA)进行求解。利用BVEDA中双变量概率模型进行区块构建,根据组合概率公式进行区块竞争和区块挖掘,借用高质量的区块组合人造解,提高演化过程中解的质量;针对算法多样性较差的特点,设计在组合人造解的过程中加入派工规则最短处理时间、最长处理时间和最早交货期,将上述方法并行演化,通过top10的权重适度值总和动态调整上述方法处理的解的数量,最后利用帕累托支配筛选和保存非支配解。试验使用C++代码在Taillard标准算例上测试,IBVEDA与SPGAⅡ和BVEDA比较,并绘制解的分布图证实算法的有效性。     

基于遗传算法的TMD系统参数优化和设计

为了达到调频质量阻尼系统最佳减振效果，需要对系统的参数进行优化，即求出最优频率比和最优阻尼比，通过引进遗传算法，针对目标函数采用惩罚函数和适值标定有效引导遗传搜索，从而达到最优解，计算结果表明了该算法对求解复杂优化问题的优越性。     

基于独立大粒度任务网格调度算法的分析比较

独立任务在异构环境下的调度问题已经得到了广泛的研究，已提出了许多启发式任务调度算法，其中包括静态调度算法和动态调度算法．对目前已提出的6种启发式任务调度算法进行了分析和研究，重点介绍了轮循（RR）算法．为了更好的比较这6种算法，采用了一种叫做处理器消耗周期（TPCC）的标准，并通过仿真，将算法进行了性能对比．     

JIT方式下的单机分批调度问题研究

准时生产意义下的调度问题，是当前调度领域研究的一个主要方面，针对单机分批作业准时生产方式，研究了不允许出现拖期的批调度问题，目标是使得加工总成本最小，目标函数不仅考虑了提高惩罚，还考虑了机器的加工费用，为了确定最优分批与各批次的开始时间，给出了两个推理的三个规则，并根据推理规则给出了一个有效的启发式算法，使得目标函数最小，应用实例说明了该算法的正确性与有效性。     

基于CPM的非流水作业排序启发式算法

通过对ｎ种零件需经ｍ类机器加工的复杂非流水型作业排序这一ＮＰ问题的分析,以误工时间最短为目标建立了数学模型,并采用 ＣＰＭ方法构造了一个优度较高的启发式算法．实际应用表明,该算法很适于单件、小批生产类型的生产进度计划．     

单台机器总完工时间随机排序问题的反问题

运筹学和最优化的种种问题(“正问题”)是在已知各有关参数或者数据的条件下,找出最优(最快、成本最省或者效益最大)的方案。所谓的“反问题”,是指已经有一个方案,但在目前的情况下,该方案并非最优,需要考虑如何最小限度地改变现有参数,使这个方案成为最优的方案。如果说“正问题”的研究有助于一个新系统的设计和确定,那么“反问题”的研究对改善现有系统的性能具有重要的意义。文章以数学规划为工具,研究单台机器以带权总完工时间为优化目标的随机排序问题1‖∑E(wjCj)关于加工时间分布参数的反问题,并给出不带权的情况1‖E(∑Cj)的反问题及其最优解。     

An optimal algorithm for a class of tardiness scheduling problem

0　ＩＮＴＲＯＤＵＣＴＩＯＮＳｃｈｅｄｕｌｉｎｇｎｉｎｄｅｐｅｎｄｅｎｔｔａｓｋｓｏｎｍｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｔｏｍｉｎｉｍｉｚｅｔｈｅｔｏｔａｌｔａｒｄｉｎｅｓｓｉｓａｆｕｎｄａｍｅｎｔａｌｐｒｏｂｌｅｍｏｆｄｅｔｅｒｍｉｎｉｓｔｉｃｓｃｈｅｄｕｌｉｎｇｔｈｅｏｒｙ.ＴｈｉｓｉｓａｎＮＰｈａｒｄｐｒｏｂｌｅｍ[1]ｆｏｒｗｈｉｃｈｉｔｉｓｉｍｐｏｓｓｉｂｌｅｔｏｆｉｎｄａｐｏｌｙｎｏｍｉａｌｔｉｍｅｏｐｔｉｍａｌａｌｇｏｒｉｔｈｍ,ｔｈｅｒｅｆｏｒｅ,ａｎｅａｒｏｐｔｉｍａｌａｌｇｏｒｉｔｈ…