首页 | 本学科首页   官方微博 | 高级检索  
    检索          
共有20条相似文献,以下是第1-20项 搜索用时 187 毫秒

1.  具有优先约束的不完全恒速机排序问题  
   赵玉芳《运筹与管理》,1999年第8卷第2期
   讨论了任务具有优先约束的可中断不完全恒速机排序问题,若处理机具有不同开始加工时间的可中断排序问题存在最优算法,则相应的不完全恒速机排序问题也有最优算法。    

2.  P_m,a_i‖C_(max)问题的A_(kk)算法的最坏情况性能比  
   石锐  赵传立《数学的实践与认识》,2008年第38卷第13期
   讨论任务的加工是不可中断,机器速度相同且机器具有不同开始加工时间的排序问题,目标函数是极小化最大完工时间.对于一般情况,给出了关于Akk算法的最坏情况性能比.    

3.  带有分批费用的容量有界的单机平行分批排序问题  
   张喆  冯琪  李文华《数学的实践与认识》,2014年第21期
   考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b~2m~22~m).    

4.  一个带退化工件的单机准时生产制问题  
   刘静  闵啸《浙江大学学报(理学版)》,2010年第37卷第1期
   研究带退化工件的单机排序问题,即工件的加工时间是其开始加工时间的线性递增函数,且不同的工件具有不同的退化率.要求为所有工件寻找一共同的最优交货期和最优序,以极小化这些工件的共同交货期、超前罚和迟后罚之和.给出了一O(nlogn)时间的最优算法.    

5.  带有多次速率改变行为的单机排序问题  
   张安  何勇《浙江大学学报(理学版)》,2006年第33卷第3期
   研究机器带有多次速率改变行为的单机排序问题.机器可以通过不超过t个时段的中断来调整加工速度, 即每个工件在每次中断时段前后加工的加工时间可能不同.因此问题就需要决定是否中断,以及何时中断,使得最大完工时间、完工时间总和、加权完工时间总和等尽可能小.对任意固定的t,关于最大完工时间和完工时间总和目标分别给出了多项式时间最优算法,对满足正则假设的加权完工时间总和目标也给出了一个多项式时间最优算法.    

6.  带有多次速率改变行为的单机排序问题  
   张安  何勇《浙江大学学报(理学版)》,2006年第33卷第3期
   研究机器带有多次速率改变行为的单机排序问题.机器可以通过不超过t个时段的中断来调整加工速度, 即每个工件在每次中断时段前后加工的加工时间可能不同.因此问题就需要决定是否中断,以及何时中断,使得最大完工时间、完工时间总和、加权完工时间总和等尽可能小.对任意固定的t,关于最大完工时间和完工时间总和目标分别给出了多项式时间最优算法,对满足正则假设的加权完工时间总和目标也给出了一个多项式时间最优算法.    

7.  一个不同时刻加工成本有差异的单机排序问题  被引次数:2
   顾燕红  甘小冰《运筹学学报》,2006年第10卷第2期
   考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置, 由此来最小化总额外加工成本.文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法, NP-hardness的证明及伪多项式时间算法.    

8.  处理机具有准备时间的Qm,aj|pj=1|Cmax排序问题  
   赵玉芳 赵传立 等《运筹与管理》,1999年第8卷第3期
   讨论了处理机具有准备时间的Qm,aj|pj=1|Cmax排序问题,通过这一问题的一个下界,给出了一个最优算法,算法的复杂性为O(m^2)。    

9.  排序问题P2|prmp|Cmax在中断—重复模型下的调度  
   杨斌鑫  刘小冬  成龙《运筹与管理》,2006年第15卷第6期
   对于传统的中断-恢复模型下的P2|prmp|Cmax问题,已有最优调度规则。但中断-恢复模型并不是一般意义下的中断模型。在某些情况下,被中断的任务不能被简单的恢复加工,而是在该任务被重新加工之前必须有一定的延迟时间。延迟可能是该项任务的一部分(或者是全部)需要返工的时间。本文在研究了排序问题P2|prmp|Cmax在中断-重复模型下的调度,指出对于选择哪一个任务被中断的问题是NP—hard的;而对于如何处理被中断的任务的问题,指出当被中断任务的最初被加工时间由Xj增加为Xj+△xj=Xj/(1-1/2aj)时,可使得两台处理机的时间表长相等,从而达到最优。最优时间表长为:Cmax^*=1/2n∑j=1pj+ajxj/(2-aj)。最后给出了在中断-重复模型下的调度规则。    

10.  排序的贪婪算法的参数上界  被引次数:3
   何勇 唐国春《运筹学学报》,1999年第3卷第1期
   本文研究平行机排序中最著名的贪婪算法─LPT算法的性质.经典排序中机器随时可以开始加工.本文研究机器不都是从开始就可以加工,而是需要一个准备时间,也就是说本文研究各台机器最早可以开工的时间可以不同的同型号平行机(ideaticalParallel)的排序问题,分析LPT算法得到的近似解的参数上界.    

11.  极小化总完工时间的同时加工排序  
   田乐  赵传立《数学的实践与认识》,2009年第39卷第20期
   讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.    

12.  具有机器故障的单机随机JIT排序问题  
   唐恒永  赵传立  程从电《中国科学A辑》,2007年第37卷第10期
   对中断-继续和中断-重复两种模型研究具有机器故障的单机随机JIT排序问题, 目标函数是期望完工时间 与工期方差和. 对中断-继续模型证明SSDE问题的最优排序具有关于期望加工时间的V-形性质, 并给出了一个拟多项式 的动态规划算法. 同时对SSDE问题和ESSD问题 进行了比较, 证明了SSDE问题的最优解是一个非常好的ESSD问题的近似最优解. 在一定的条件下, SSDE问题 的最优解就是ESSD问题的最优解. 对中断-重复模型, 由于完工时间的方差无法求出, JIT排序问题至今没得到解决, 故从实际 应用角度用SSDE问题替代ESSD问题, 证明了SSDE问题最优解具有关于期望占用机器时间的V-形性质, 并给出了 一个拟多项式的动态规划算法, 提出了一个研究JIT问题的中断-重复模型的新思路.    

13.  带强制工期的可中断平行机排序问题  
   钟雪灵  王国庆  程明宝  李晓春《系统科学与数学》,2011年第31卷第7期
   讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.    

14.  可中断半在线排序问题  被引次数:1
   朱熙  杨启帆《浙江大学学报(理学版)》,2006年第33卷第1期
   讨论两台同型机上的可中断半在线排序问题,目标函数为极大化最小的机器完工时间Cmin.首先考虑已知所有工件的加工时间在p和rp(p〉0,r≥1)之间的情形,对任意的参数r,设计了最优半在线算法.接着。对已知最大工件加工时间的情形作了研究,得到了一个竞争比为5/4的最优半在线算法.    

15.  可中断半在线排序问题  被引次数:1
   朱熙  杨启帆《浙江大学学报(理学版)》,2006年第33卷第1期
   讨论两台同型机上的可中断半在线排序问题,目标函数为极大化最小的机器完工时间Cmin.首先考虑已知所有工件的加工时间在p和rp(p〉0,r≥1)之间的情形,对任意的参数r,设计了最优半在线算法.接着。对已知最大工件加工时间的情形作了研究,得到了一个竞争比为5/4的最优半在线算法.    

16.  恶化率与工件无关的线性加工时间调度问题  被引次数:3
   赵传立  唐恒永《数学的实践与认识》,2005年第35卷第3期
   讨论恶化率与工件无关的线性加工时间调度问题 .对于工件间具有平行链约束 ,目标函数为极小化最大完工时间的单机问题 ,分别就链不允许中断和链允许中断两种情况给出了最优算法 .对于工件间没有优先约束 ,目标函数为极小化完工时间和的平行机问题 ,证明了工件按基本加工时间不减排列可以得到最优调度 .    

17.  带机器故障的两台机带权误工数排序问题  
   胡觉亮  张玮虹  蒋义伟《高校应用数学学报(A辑)》,2010年第25卷第4期
   讨论机器带故障中断的两台平行机排序问题,工件加工时间均为单位时间,目标是极小化带权误工工件数.当转移时间t=0时给出了最优的算法.当t≠0时,给出了一个多项式时间的近似算法,并证明算法解与最优解至多相差一个带权误工数.    

18.  带权的误工排序问题的最优算法  被引次数:1
   陈小林《运筹与管理》,2009年第18卷第3期
   研究工件有不同的权(重要性)、但是与工件加工时间有反向"一致性"关系,并且在保证工件的一个子集T中的工件必须不误工的前提下,使得带权的误工工件的个数(误工造成损失的费用)为最少的排序问题1∣T,(pi≤pj ) (wi≥wj)∣∑wjUj ;提出该问题的最优算法,证明提出的算法得到的排序是最优排序,而且证明这个最优排序在所有最优排序中不误工工件总的加工时间为最小.    

19.  柔性Flow shop最小和调度问题的启发式研究  
   古春生  陈华平《运筹与管理》,2005年第14卷第3期
   本文研究有n个作业须在s个处理机中心进行加工,处理机中心i由l1个同速机组成的非抢占式柔性nowshop加权完成时间调度问题。每个作业有同样的加工路径通过每个处理机中心,但只需在处理机中心的任一台机器上加工处理,作业到达时间相同。目的是确定一个作业在每个处理机中心机器上的可行调度序列,使所有作业在最后处理机中心的加权完成时间总和最小化。在作业处理时间和权重有界、每个作业的工序处理时间为同分布的随机变量、不同作业的处理时间相互独立时,通过分组这种机器环境,我们证明该问题在作业数趋于无究时,一个基于加权最短处理时间的启发式算法是渐近最优的。    

20.  两类加工时间是一般函数的单机排序问题  
   王成飞  张玉忠  苗翠霞《运筹学学报》,2011年第15卷第2期
   考虑了两类有一般加工时间函数的排序问题.工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和.对加工时间依赖开工时间的模型,证明了一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的.对加工时间依赖开工位置的模型,给出极小化最大完工时间和极小化总完工时间的最优序,同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法.    

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号