首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
本文研究具有可拒绝的两代理分批配送排序问题,两个代理竞争一台机器的使用,每个代理有自己的工件集合.工件生产完后需要分批配送到代理处,每一批需要花费一定的时间和费用.我们的目标是在保证一个代理的目标函数不超过给定值的前提下,极小化另一个代理的目标函数.对于排序理论中主要的目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对具体的问题给出了它们的最优算法.  相似文献   

2.
文章研究了工件可拒绝的单机双代理排序问题.可拒绝意味着决策者会选择拒绝一些获利较小耗费资源多的工件,但拒绝会产生相应的拒绝费用.第一个代理工件可拒绝,目标函数为总误工、总权误工损失、总完工时间与拒绝费用之和.在第二个代理工件的总权误工工件数不超过定值的情况下,寻找一个使得第一个代理的目标函数值最小的排序方案.文章提出了相应排序问题的最优性质及伪多项式时间动态规划算法,分析了算法的时间复杂度,最后通过算例来说明了算法的可行性.  相似文献   

3.
研究了单机环境下生产与配送的协同排序问题.有多个工件需要在一台机器上进行加工,加工完的工件需要分批配送到一个客户.每批工件只能在固定的几个配送时刻出发,不同的配送时刻对应着不同的配送费用.我们的目标是找到生产与配送的协同排序,极小化排序的时间费用与配送费用的加权和.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对于配送费用单调非增的情况给出了它们的最优算法.  相似文献   

4.
具有退化工件和老化效应的单机可拒绝排序问题   总被引:2,自引:0,他引:2  
研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加工的效率;机器进行维修活动后将恢复到初始状态,老化效应也将重新开始。目标是确定拒绝哪些工件、何时进行维修活动以及接受工件集中工件的次序,以便极小化接受加工工件的最大完工时间与拒绝加工工件总处罚费用的和。证明得到了所研究的问题是NP-难解的,并给出了解决问题的一个全多项式时间近似方案(FPTAS)算法。  相似文献   

5.
研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题。在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定。然而,在工件正式开始加工时,工件集中的部分工件由于延误不能按时到达,这对初始排序的执行产生了干扰,所以需要对初始排序进行调整,即重新排序。为了保证服务水平,允许对延误工件拒绝加工,但需支付相应的拒绝费用。调整后的重新排序的目标是在保证接受工件集中工件的最大延误不超过给定的上界的约束下,使得接受工件集的赋权完工时间和,拒绝工件集的拒绝费用和以及接受工件集中工件的最大延误的赋权惩罚费用之和达到极小。对该问题,设计了一个伪多项式时间动态规划精确算法,并利用稀疏技术得到了一个完全多项式时间近似方案。  相似文献   

6.
研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。  相似文献   

7.
考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝...  相似文献   

8.
文章研究了工件可拒绝的双代理单机多任务排序问题,双代理之间不可打扰,考虑了最大完工时间为目标的模型.给定总拒绝成本的允许上限,每个工件有两个选项:接受或拒绝.由于该问题是NP难的,为该问题设计了伪多项式动态规划算法,■近似算法以及完全多项式时间近似方案.  相似文献   

9.
考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.  相似文献   

10.
研究了带有拒绝的单机和同型机排序问题. 对于单机情形, 工件的惩罚费用是对应加工时间的alpha倍.如果工件有到达时间, 目标为最小化时间表长与惩罚费用之和, 证明了这个问题是可解的.如果所有工件在零时刻到达, 目标为最小化总完工时间与惩罚费用之和, 也证明了该问题是可解的.对于同型机排序问题, 研究了工件分两批在线实时到达的情形, 目标为最小化时间表长与惩罚费用之和.针对机器台数2和m, 分别给出了竞争比为2和4-2/m的在线算法.  相似文献   

11.
提出了一类可变加工时间的单台机器排序问题,着重考虑如下的目标函数:最小化工件排序长度、完工时间之和误工工件数等等,且用受束的等规模划分问题证明了可变加工时间的单台机器排序问题是NP-完全的。  相似文献   

12.
一个不同时刻加工成本有差异的单机排序问题   总被引:2,自引:0,他引:2  
考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置, 由此来最小化总额外加工成本.文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法, NP-hardness的证明及伪多项式时间算法.  相似文献   

13.
工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.  相似文献   

14.
本文考虑带重入的单台机排序问题,重入是指每个工件在机器上加工不止一次.通过把重入模型转化为带平行链约束的排序问题,我们成功地获得了单机重入问题的两个目标函数的多项式时间最优算法,一个是总带权完工时间∑ωjCj,另一个是最大费用函数hmax.  相似文献   

15.
主指标为最大延迟的主次指标分批排序问题   总被引:1,自引:0,他引:1  
研究现代排序问题—主指标为最大延迟的主次指标分批排序问题.这里利用动态规划的递推法给出了次指标分别为最大完工时间和误工总数时的多项式时间算法,并给出了次指标为关于工件完工时间的任意正规函数时的拟多项式时间算法.  相似文献   

16.
We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine. The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint. Three problems are considered:(1) minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2) minimize the makespan of accepted jobs sub...  相似文献   

17.
A batch is a subset of jobs which must be processed jointly in either serial or parallel form. For the single machine, batching, total completion time scheduling problems, the algorithmic aspects have been extensively studied in the literature. This paper presents the optimal batching structures of the problems on the batching ways: all jobs in exactly N(arbitrary fix batch number and 1 < N < n) batches.  相似文献   

18.
研究具有禁用区间的单机最小化加权完工时间和排序问题.在该问题中,有一些禁用区间已经固定在机器上,工件将被安排在其余自由区间内进行加工且不能与禁用区间重叠.在文献中已经证明,该问题是强NP-困难的,并且在P不等于NP的假设下,该问题不存在2~(q(n))-近似算法.其中,n是工件个数,而q(n)是n的任一多项式.但是,其精确最优算法尚属未知.给出了该问题的一个动态规划最优算法.当禁用区间的数目是固定常数时,该算法是拟多项式的.  相似文献   

19.
带到达时间的单机排序中的资源分配问题   总被引:1,自引:0,他引:1  
讨论两个单机排序的资源分配问题1|rj,pj=bj-ajuj,Cmax≤|∑uj和1|rj,prec,pj=bj-ajuj C max≤|∑uj并给出求其最优资源分配的多项式算法.  相似文献   

20.
Single Machine Scheduling with Learning Effect Considerations   总被引:11,自引:0,他引:11  
In this paper we study a single machine scheduling problem in which the job processing times will decrease as a result of learning. A volume-dependent piecewise linear processing time function is used to model the learning effects. The objective is to minimize the maximum lateness. We first show that the problem is NP-hard in the strong sense and then identify two special cases which are polynomially solvable. We also propose two heuristics and analyse their worst-case performance.  相似文献   

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

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