首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 82 毫秒
1.
并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。  相似文献   

2.
万龙 《运筹学学报》2015,19(2):54-60
研究了两个单机两代理排序问题.在第一个两代理排序问题中,代理A的目标函数为极小化所有工件的加权完工时间总和,代理B的目标函数为极小化最大工件费用.在第二个两代理排序问题中,代理A的目标函数为极小化所有工件的加权完工时间总和,代理B的目标函数为极小化所有工件的最大完工时间.证明了第一个问题是强NP-难的,改进了已有的一般意义NP-难的结果;对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.  相似文献   

3.
考虑带有退化效应和序列相关运输时间的单机排序问题.工件的加工时间是其开工时间的简单线性增加函数.当机器单个加工工件时,极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的,EDD序对于极小化最大延迟问题不是最优排序,另外,就交货期和退化率一致情形给出了一最优算法.当机器可分批加工工件时,分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.  相似文献   

4.
极小化加权总完工时间的分批排序问题   总被引:11,自引:0,他引:11  
本文讨论了分批排序中极小化加权总完工时间的两个问题.就所有工件的加工时间都相等这一特殊情况,分别给出两个算法,并证明了算法的最优性.  相似文献   

5.
讨论了两类机器带准备时间的同类机分批排序问题.对工件无到达时间及有常数个到达时间,目标函数为极小化加权总完工时间这两类问题进行研究,给出了两个最优算法,并对算法及其计算复杂性给予了分析与证明.  相似文献   

6.
本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了p_(ij)=p_i(i=1,…,m;j=1,…,n)这种情况,当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.  相似文献   

7.
排序中以工件迟后范围作为极小化的目标函数体现了生产中对顾客的平等对待,对此目标函数以往的研究局限于非成批加工.随着成批加工大量出现于柔性制造系统中,其它一些目标函数如加权完工时间之和,最大迟后己出现在成批加工问题中,但还无人讨论工件迟后范围问题.本文对工件加工顺序给定时如何使迟后范围极小的最优分批问题建立了所需时间为多项式的动态规划算法,并进一步给出了一些性质.  相似文献   

8.
考虑了两类有一般加工时间函数的排序问题. 工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和. 对加工时间依赖开工时间的模型,证明了一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的. 对加工时间依赖开工位置的模型,给出极小化最大完工时间和极小化总完工时间的最优序,同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法.  相似文献   

9.
研究工件可提前预知信息的在线分批排序问题,工件的预知信息时间依时间到达,目标为极小化最大完工时间.已知从工件的信息可预知到该工件可加工需要时间a,所有工件的最大加工时间为p_(max),多个工件可以作为一批被机器同时加工,批的加工时间为该批工件中最长加工时间.对于批容量无限的单机问题给出一个在线算法γH~∞,并证明其竞争比和问题的下界都为1+γ,其中γ=(-1+(1+(4p_(max))/(p_(max)+a)))/2,进而算法是最优的.  相似文献   

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

11.
The Coordination of Scheduling and Batch Deliveries   总被引:2,自引:0,他引:2  
This paper considers several scheduling problems where deliveries are made in batches with each batch delivered to the customer in a single shipment. Various scheduling costs, which are based on the delivery times of the jobs, are considered. The objective is to minimize the scheduling cost plus the delivery cost, and both single and parallel machine environments are considered. For many combinations of these, we either provide efficient algorithms that minimize total cost or show that the problem is intractable. Our work has implications for the coordination of scheduling with batch delivery decisions to improve customer service.  相似文献   

12.
本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足$0\leq\alpha\leq 1$。  相似文献   

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

14.
We study the on-line scheduling on an unbounded batch machine to minimize makespan. In this model, jobs arrive over time and batches are allowed limited restarts. Any batch that contains a job which has already been restarted once cannot be restarted any more. We provide a best possible on-line algorithm for the problem with a competitive ratio .  相似文献   

15.
We address a single-machine batch scheduling problem to minimize total flow time. Processing times are assumed to be identical for all jobs. Setup times are assumed to be identical for all batches. As in many practical situations, batch sizes may be bounded. In the first setting studied in this paper, all batch sizes cannot exceed a common upper bound. In the second setting, all batch sizes share a common lower bound. An optimal solution consists of the number of batches and their (integer) size. We introduce an efficient solution for both problems.  相似文献   

16.
The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job's processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs) for the considered problems.  相似文献   

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

18.
本文研究一类具有线性恶化效应的单机在线分批排序问题,工件$J_j$的加工时间为$p_j=b_j+\alpha t$, 其中$b_j$为基本加工时间, $\alpha>0$为恶化率, $t$是开工时间. 工件的到达时间是未知的, 工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工, 批的加工时间为该批中工件最大加工时间.本文对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法$\beta H^\infty$,并证明其竞争比和问题的下界相同, 进而算法是最优的.  相似文献   

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

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