共查询到20条相似文献,搜索用时 802 毫秒
1.
带公共交货期窗口的提前/拖期非等同多机调度问题 总被引:2,自引:0,他引:2
提出了公共交货期窗口下提前 /拖期惩罚的多台不同设备情形的零件排序模型 .在分析相应单机问题最优排序和最优交货期性质的基础上 ,证明该多机零件问题实际上蕴含着使系统 makespan达最小的多机零件排序问题 .由于使系统 makespan达最小的并行多机零件排序问题已被证明是 NP完全问题 ,因此提出了求解该零件排序问题的一个启发式算法 ,该算法计算复杂性低且对并行多机零件排序问题同样适用 .最后给出了两个数值例子 . 相似文献
2.
讨论具有随机加工时间的单机调度问题,目的是确定n个工件的一个排序使得完成时间与一公共交货期差的绝对值加权和的期望最小,在假定加工时间和交货期都服从负指数分布时,建立了此随机调度问题等价的确定形式,并讨论了最优解的∧形特征,然后,在一定条件下将上述结果推广到机器随机故障的情形。 相似文献
3.
讨论具有随机加工时间的单机调度问题,目的是确定n个工件的一个排序使得完成时间与一公共交货期差的绝对值加权和的期望最小.在假定加工时间和交货期都服从负指数分布时,建立了此随机调度问题等价的确定形式,并讨论了最优解的Λ形特征.然后,在一定条件下将上述结果推广到机器随机故障的情形. 相似文献
4.
讨论一类具有随机加工时间的单机调度问题,所有工件设置一个公共交货期窗口,每个工件的加工时间服从正态分布,目标是确定n个独立工件的一个排序,使工件的提前/延期之和与完工时间之和的线性组合之期望值最小。问题的最优解具有v-型特征。 相似文献
5.
具有窗口式交货期的加工排序问题是一个强NP困难问题,传统方法的计算效果往往不能令人满意.采用基于整数编码的单亲遗传算法较成功地解决了这类窗口式交货期的单机和多机加工排序问题,并讨论了该算法的计算复杂性是属可计算的.文中的算例表明,该算法是实际有效的. 相似文献
6.
加工时间服从指数分布单机随机调度 总被引:3,自引:0,他引:3
讨论加工时间服从指数分布的单机随机调度问题,目标是实现工件完成时间与公共交货期偏差的加权和期望最小化。此问题是JIT(Just-In-Time)生产环境下的典型调度模型。结果表明问题的最优解关于权值与加工时间均值的商具有∧形特征。 相似文献
7.
针对一类带有准备时间和安装时间的单机成组排序问题,给出了求解最优排序的多项式算法。其中每个工件都具有自己的准备时间,组和组之间具有安装时间,并且安装时间和已经加工完工件的加工时间有关。所有工件在机器上加工时,一次只能加工一个工件,工件不可中断,组内工件连续加工,组和组之间需要安装时间。对目标函数为极小化最大完工时间的单机成组排序问题,给出了求解最优排序的多项式算法。原问题不是成组问题,为此在原问题的基础上添加了工件的成组问题且组内每个工件都具有自己准备时间,其结果是依然能给出求解最优排序的多项式算法。 相似文献
8.
本文利用HLP不等式,讨论了同类工件FoleShopE/T调度问题,目的是确定工件的最优交货期和最优排序。 相似文献
9.
具有交货期窗口满意数最大的排序问题算法复杂性 总被引:2,自引:1,他引:1
讨论这样一类单机排序问题:每个工件联系一个交货期窗口;如果工件的完工时间落在该工件的交货期窗口内,则称该工件的完工是满意的;排序的优化准则是完工为满意的工件个数最大.本文证明了上述排序模型是强NP困难的. 相似文献
10.
交货期服从指数分布的单机随机调度问题 总被引:2,自引:1,他引:1
工件完成时间与交货期差的绝对值加权和最小化单机随机调度问题是JIT(just-in-time)生产环境下的典型调度模型,是NP-hard问题,然而,当工件权值与加工时间成正比时,LPT(largest processing time)工件调度是问题的最优解,讨论了该问题加工时间和交货期都为随机变量,其中交货期服从指数分布,且工件权值与加工时间成正比的情形,给出了问题的最优解,并在一定条件下将结果推广到机器随机故障的情形。 相似文献
11.
一类单机随机调度问题解的特征 总被引:2,自引:0,他引:2
讨论了加工时间随机的单机调度问题,工件的加工时间服从指数分布,目标函数具有一般形式,涉及工件完成时间与交货期偏差的正规和非正规目标函数,如工件关于交货期拖后时间期望和,工件完成时间关于交货期绝对偏差的期望和等,都是其特殊情形.给出了最优解的特征,包括SEPT(shortest expected pro—cessing time)调度,LEPT(largest expected processing time)调度和关于加工时间参数的A形调度,这些特征可用于确定问题的最优解。 相似文献
12.
13.
讨论优先约束条件为树型,目标函数为带有折扣的加权完工时间的单机排序问题l|outtree|∑wj(1-e-rCj),并给出了求解该问题的一个算法复杂性为O(n2)的最优算法. 相似文献
14.
15.
以往对单机作业排序的研究大都限于单目标问题,而在实际的生产调度和计划管理中绝大多数情况需要进行多目标作业排序。本文运用模糊综合评判方法,提出一种单机多目标作业排序的遗传优化算法。 相似文献
16.
带有交货期窗口的调度问题及算法 总被引:4,自引:1,他引:3
对不同交货期窗口下的提前/拖期单机调度问题进行了分析,给出了最优序列中相邻工件对所满足的必要条件,提出了两个优先级法则,并利用优先级法则设计出遗传算法的交叉算子,在文章的最后,给出了实验结果和结论. 相似文献
17.
18.
基于JIT的多目标并行多机调度问题的混合遗传算法 总被引:3,自引:0,他引:3
针对一类极小化 makespan和延迟区间的并行多机零件排序问题 ,设计了一个混合遗传算法 .该算法的特点是充分利用求解单机问题的最优有效算法 ,设计了一种简单的编码方案 ,简化了算法的实现难度 ,提高了算法的执行效率 .数值仿真实验表明 ,该算法具有收敛速度快、优化效果好等特点 ,且适合于求解大规模问题 . 相似文献
19.
单机加权成套订单数遗传算法研究 总被引:10,自引:0,他引:10
从实际应用出发,提出了使成套订单数最大的单机排序新问题,建立了该问题的0-1整数规划模型,相应设计了求解的遗传算法,并通过一个算例对这类排序问题和所提出的算法进行了说明,计算结果表明了算法的有效性。 相似文献
20.
链优先约束工件单机随机排序问题 总被引:7,自引:0,他引:7
讨论单机随机排序问题,目标函数为确定工件的排列顺序使工件的加权完工时间和的数学期望最小。设工件问具有平行链优先约束,机器发生随机故障。考虑两种情况,第一种情况是链不允许中断.第二种情况是链允许中断,对两种情况分别给出最优算法。 相似文献