共查询到18条相似文献,搜索用时 156 毫秒
1.
研究了共同宽容交货期的单机排序问题,即加工时间是位置的函数,所有工件的提前/延误费用相同,共同宽容交货期的开始时间和大小待定,目标函数最小化的总惩罚费用(包括提前、延误、宽容交货期的定位和大小费用四部分).并给出了最优排序的性质,提出了一个多项式时间算法. 相似文献
2.
研究有组安装任务的单机窗时排序问题,所有工件的提前/延误惩罚费用相同;公共交货期窗口大小给定但位置待定,由线性定位费用衡量;最优排序是使所有这些费用的和最小.给出了最优排序的一些性质,提出一个多项式时间算法. 相似文献
3.
4.
杨汉兴 《武汉科技大学学报(自然科学版)》1995,(3)
求解具有公共交货和提前-滞后惩罚的单机排序问题是很困难的,其计算复杂性是强NP完全问题.作者研究这类问题的最优解的结构特征,得出了对于完工时间比公共交货期大的工件按WSPT序排列,对于完工时间少于公共交货期的工件按WLPT序排列,一般情况下的最优解具有V形结构的结论。 相似文献
5.
考虑n个独立工件单机作业排序,每个工件设置NOP交货期.目标是确定NOP交货期的最优工序数乘子和工件的最优排序,使得由交货期、提前及延误构成的费用函数最小.先提出这个问题的线性规划模型,然后通过线性规划的对偶问题推导出最优工序数子及工件的最优排序. 相似文献
6.
讨论带有退化效应的多个交货期窗口的单机排序问题。其目标函数有2种:第1种是带有提前、延误、交货期的开始位置、交货期的大小及最大完工时间的总费用;第2种是带有提前、延误、交货期的开始位置、交货期的大小和所有工件完工时间之和的总费用。目标是找到多个交货期窗口的最优位置、交货期的大小、属于每个交货期窗口的工件集合和工件的最优排序,使目标函数值最小。将该问题转化为指派问题,并证明其多项式时间可解。 相似文献
7.
本文讨论带有学习及退化效应和资源分配的交货期指派的单机排序问题。所有工件有一个公共的交货期,如果工件在交货期内完工将不产生任何费用,但是在交货期之前或之后完工将产生相应的提前或延误费用。工件的实际加工时间是与开工时间、在排序中位置和资源分配有关的函数。目标是确定最优交货期的位置、交货期的大小、工件的最优排序和最优资源分配,最小化包括提前、延误、交货期大小、交货期位置和资源消耗的总费用。证明了带有学习及退化效应和资源分配的交货期指派问题仍然是多项式可解的,并且最优算法是可以在O(n3)时间内求出最优解。
相似文献
相似文献
8.
本文讨论带有学习及退化效应和资源分配的交货期指派的单机排序问题。所有工件有一个公共的交货期,如果工件在交货期内完工将不产生任何费用,但是在交货期之前或之后完工将产生相应的提前或延误费用。工件的实际加工时间是与开工时间、在排序中位置和资源分配有关的函数。目标是确定最优交货期的位置、交货期的大小、工件的最优排序和最优资源分配,最小化包括提前、延误、交货期大小、交货期位置和资源消耗的总费用。证明了带有学习及退化效应和资源分配的交货期指派问题仍然是多项式可解的,并且最优算法是可以在O n()3时间内求出最优解。 相似文献
9.
本文考虑了一个包含工件生产和工件送货的单机调度问题。目标是寻找所有工件的公共交货期和每个工件的送货时间使得工件所受到惩罚(提前/拖后惩罚,送货费用等)的值最小。完成的工件按照批次进行送货,所有在公共交货期前完工的工件在最优交货期时间一起交付,对批次送货没有量的约束。本文确定了最优公共交货期,并给出了相应的排序。 相似文献
10.
研究有公共交货期窗口的单机排序问题,其目标是最小化提前和延误的赋权工件数.首先考虑交货期窗口大小给定的情况,进而讨论了当其大小待定且有线性时间惩罚的情形.分别给出最优排序的一些性质,根据这些性质提出了多项式时间的最优算法以最小化所有费用的和. 相似文献
11.
研究退化条件下的工期指派的单机排序问题。每个工件均有一个关于工期的连续非减的惩罚函数。工件的加工时间是退化的,即工件的加工时间是其开始加工时间的一个线性增函数,所有工件都有一个相同的退化率。目标是确定工件的最优加工顺序、最优工期和最优开始加工时间,使总工期、误工工件数及总完工时间之和最小。工件在工期之后完成则称为误工工件,工件在工期之前完成则是提前工件。工期指派分两种情况,一种是所有的工件工期都相等,另一种是不同的工件有不同的工期。对于上述两种情况分别给出了最优解的3个性质,并且证明了这个问题是多项式时间可解的。 相似文献
12.
结合窗时排序与同时加工排序,考虑单机器上批容量有限的情形,为享有公共交货期窗口[e,d]的n个工件分批并排序,以最小化总的赋权提前和延误的工件个数;将最早交货期e和窗口大小K作为未知参数,与最优序列一起确定使得总费用最小。在给出的最优排序的若干性质基础上提出了多项式时间算法。 相似文献
13.
研究了网络化集成制造模式下的JOB-SHOP调度问题,即各任务有具体交货期约束的提前/拖期不同惩罚系数的复杂调度问题;提出了一种新的编码方案和相应的交叉算子,进而提出混合遗传算法;成功解决了上述问题,即找到一个最优调度,使在交货期窗口外完工的任务所受到的提前/拖期惩罚的总和最小.该算法解码复杂度低、通用性强、罗拔性强,最后用算例说明了算法的有效性并指出了工件车间调度问题中尚待解决的问题. 相似文献
14.
JIT系统下的单机提前/拖期调度问题 总被引:2,自引:1,他引:1
分别研究了交货期及交货期窗口下的单机调度问题,目标是寻找一个最优调度极小化提前/拖期任务数。假设如何任务在交货期或交货期窗口内完工,则不受处罚;否则,就要受到一个固定的提前/拖期惩罚;提出了在交货期及交货期窗口下的寻找最优调度的多项式算法,并以两个实例说明了算法。 相似文献
15.
考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。 相似文献
16.
研究了一类分族分批排序最小误工个数问题,给出并证明了最优排序的性质,证明了此问题是NP-困难的.对工件的到达时间和工期一致时的情形,给出了一个时间复杂性为O(mb(n/m)^2m)的动态规划算法. 相似文献
17.
单机分族分批排序的最小误工个数问题 总被引:1,自引:0,他引:1
曹国梅 《四川理工学院学报(自然科学版)》2008,21(5)
文章研究了同一族内,给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O(mb(n/m)2m)的动态规划算法。 相似文献