带时间延迟的极小化总完工时间的单机排序问题

带时间延迟的极小化总完工时间的单机排序问题胡觉亮;王焕男;蒋义伟【摘要】研究工件带有两道工序的单台机排序问题.在该问题中,工件的第一道工序先于第二道工序加工,并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间,目标是极小化所有工件的总完工时间.文章考虑所有工件相同且两道工序的加工时间均为单位时间的情形.通过引入k-连续加工的概念和分析最优解的性质,根据延迟时间的大小,分别设计了两个算法并证明了算法所得的排序为最优排序.【期刊名称】《浙江理工大学学报》【年(卷),期】2014(031)001【总页数】5页(P83-87)【关键词】单台机;时间延迟;总完工时间;算法设计与分析;最优排序【作者】胡觉亮;王焕男;蒋义伟【作者单位】浙江理工大学理学院,杭州310018;浙江理工大学理学院,杭州310018;浙江理工大学理学院,杭州310018【正文语种】中文【中图分类】O233本文主要研究带延迟时间的单机排序问题。

每个工件Jj有两道工序aj和bj，第一道工序先于第二道工序加工，第一道工序的完工时间与第二道工序的开工时间之间至少存在lj个单位时间延迟，也就是说第二道工序至少等待lj个单位时间才能开工。

此类问题在一些产品制造工艺流程、布匹印染和服装订单的生产中有重要的应用背景。

对于带有延迟的排序问题，主要分为两类，一类是工件Jj前后两道工序的延迟时间恰好为lj，本文称之为精确延迟排序；另一类是两道工序间的延迟时间至少为lj，称之为至少延迟排序。

关于精确延迟的排序问题，Orman等［1］证明了单台机的一些特殊情况是多项式可解的，并证明即便所有工序的加工时间相同，该问题还是强NP-难的。

Leung等［2］利用贪婪算法研究延迟非增的情形，给出了问题F2｜，aj=a，bj=b，a≥b｜∑Cj的最优排序，并对问题F2｜，aj=a，bj=b，a＜b｜∑Cj给出了一个2-近似算法。

Ageev等［3］分别研究了单台机和两台流水作业机器问题的一些近似算法。

工件有到达时间最小化最大完工时间的平行机分批排序问题刘丽丽【摘要】研究工件有到达时间的最小化最大完工时间的平行机分批排序问题.对于不同的工件到达时间的个数和机器台数都是常数的情形提出了一个伪多项式时间的动态规划算法和一个完全多项式时间框架.%The problem of scheduling jobs with release dates on parallel batch processing machines to minimize the makespan is considered. A pseudo-polynomial time dynamic programming algorithm and a fully polynomial time approximation scheme for the case with a fixed number of release dates and a fixed number of machines are developed.【期刊名称】《科学技术与工程》【年(卷),期】2011(011)031【总页数】4页(P7789-7792)【关键词】排序;批处理机器;到达时间;最大完工时间【作者】刘丽丽【作者单位】上海第二工业大学理学院,上海201209【正文语种】中文【中图分类】TH162.2Batch scheduling problems were originally motivated by the burn-inoperations in the final testing stage of semiconductor manufacturing.A batch processing machine is one that can process several jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.Once processing is begun on a batch，no job can be removed from or introduced into thebatch.Although this model is primarily motivated by the burn-in operations of semiconductor manufacturing，it can also be applied to other manufacturing environments such as heat treatment in metal working industries，and diffusion or oxidation processing in wafer fabrication of semiconductor manufacturing［1］.In this paper we study the problem of scheduling jobs with release dates on parallel batch processing machines to minimize the makespan.More precisely，there are n jobs to be processed on m parallel batch processing machines.Each job j(j=1，2，...，n)is associated with a release date rj，at which the job arrives and becomes available，and a processing time pj，which is the minimum processing time needed for this job.A batch processing machine can process up to B jobs at the same time，where B ＜n.The processing time of a batch is equal to the largest processing time of the jobs in the batch，and the completion time of a job is defined as the completion time of the batch it belongs to.If a batch contains exactly B jobs，we call it a full batch;otherwise，we call it a partial ing the three-field notation of Graham et al.［2］，the problem under study is denoted as P|rj，B|Cmax.For the problem of minimizing makespan with release dates on a singlebatch processing machine 1|rj，B|Cmax，Brucker et al.［3］ proved that it is strongly NP-hard even if B=2;Liu and Yu［4］ showed that this problem is binary NP-hard even if the jobs are subject to two distinct release dates，they presented a pseudopolynomial time algorithm for the case where there are a fixed number of distinct release dates;Independently，Deng et al.［5］ presented a pseudo-polynomial time algorithm for the same special case of the problem，based on the pseudo-polynomial time algorithm they provided，Deng et al.［5］ developed a polynomial time approximation scheme for the problem.For the problem of minimizing makespan with release dates on the parallel batch processing machinesP|rj，B|Cmax，Li et al.［6］ presented a polynomialtime approximation scheme.In this paper we provide a pseudo-polynomial time algorithm for the problem P|rj，B|Cmaxwith a fixed number of distinct release dates and a fixed number of machines.Then we develop a fully polynomial time approximation scheme based on the pseudo-polynomial time algorithm.1 Pseudo-polynomial solvable case for the problem P|rj，B|CmaxWe know that the problem P|rj，B|Cmaxis strongly NP-hard since even the problem P||Cmaxand 1|rj，B|Cmaxare NP-hard in the strong sense，which are special cases of the problem we are considering.Deng et al.［5］ and Liu and Yu［4］ presented a pseudo-polynomial time algorithm for the problem 1|rj，B|Cmaxwith a fixed number of distinct release dates independently.We propose in the following a dynamic programming algorithm for P|rj，B|Cmax，thus generalizing their results to the parallel-machine case.For the problem 1|B|Cmax，Bartholdi provided a polynomialoptimal Algorithm FBLPT in his unpublished manuscript，which first orders the jobs in non-increasing order of their processing times;then assigns adjacent B jobs as a batch from the beginning until all the jobs have been assigned;and finally arranges the batches in any arbitrary order.Thus all the batches are full except possibly one.To present a dynamic programming algorithm for the problem P|rj，B|Cmax，some notation is needed.Let k and m denote the number of distinct release dates and the number of machines，respectively，and r'1，r'2，…r'kdenote the k distinct release dates with r'1≤r'2≤…≤r'k.Without loss of generality，we assume r'1=0 and r'k+1=∞.Then the time interval ［0，+∞)can be part itioned into k disjoint time intervals as follows:［0，r'2］，［r'2，r'3］，…，［r'k，+ ∞).The job set started at or after timer'hbut strictly before time r'h+1(h=1，2，…，k)on machine l is denoted by Jlh.Therefore all the jobs can be divided into km disjoint job sets，and we have the following lemma.Lemma 1.There exists an optimal schedule in which the jobs in Jlh(l=1，2，…，m;h=1，2，…k)are arranged by Algorithm FBLPT and the batches are sequenced in non-increasing order of their processing times on every machine.Let clhdenote the total processing time of the batches in Jlh，and nlhdenote the number of jobs in thenlh≤B.Since the last batch in Jlhmay complete after time r'h+1 ，the start time of the first batch in Jl，h+1is therefore delayed.We define this delay time as dlh，out loss of generality，we assume dl1=0 for 1≤l≤m.For a given schedule，let vector slh=(dlh，clh，nlh)(1≤l≤m，1≤h≤k)denote the state of job set Jlh.We set the logic function Yj(s11，…，s1k，s21，…，s2k，…，sm1，…，smk)to 1 if there is a feasible schedule that satisfies Lemma 1，which assigns jobs 1，2，…，j to the m machines and the jobs in Jlhare in state slh(1≤l≤m，1≤h≤k);otherwise，set Yj(s11，…，s1k，s21，…，s2k，…，sm1，…，smk)to 0.To present a dynamic programming algorithm according to the above discussion，we first order the jobs in non-increasing order of their processing times such that p1≥p2≥…≥pn.The formulation of the dynamic programming algorithm based on Lemma 1 is as follows.Initial condition:Yj(s11，…，s1k，s21，…，s2k，…，sm1，…，Recursive formula:For 1≤j≤n，suppose rj=r'i.We have Where s'li=(dli，cli，nli － 1)with sli=(dli，cli，nli)and nli＞1，and s″li=(dli，cli － pj，B)withsli=(dli，cli，1).In the recursive formula，all the possible assignments of job j are considered.Since it is released at r'i，it can only be started at or after time r'i.Suppose it is assigned to job set J'lh.Because job j has the smallest processing time among all the jobs that have been scheduled，it should be inserted into the last batch of J'lhaccording to lemma 1.There are two possibilities.One is that the last batch of J'lhis not full before inserting job j into it，so inserting job j will not increase the total processing time c'lhbutwill increase the number of jobs of the last batch n'lhby one.The other is that the last batch of J'lhis full or there is no batch in J'lhat all before assigning job j.For this case job j starts the last batch and the total processing time c'lhwill increase by pj and the number of jobs of last batch n'lhbecomes one.The optimal value is equal to mindki+cki}|Yn(s11，…，smk)=1}.The time complexity of the proposed dynamic programming algorithm is O，which is pseudo-polynomial when the number of distinct job release dates and the number of machines are fixed.Theorem 1.The problem P|rj，B|Cmaxcan be solved in pseudo-polynomial time for the case where there are a fixed number of distinct job release dates and a fixed number of machines.Based on the above dynamic programming algorithm and the approximation scheme presented in ref.［5］，we develop the following fully polynomial time approximation scheme for the problemwith a fixed number of distinct release dates and a fixed number of machines，which is denoted by FP(Fully Polynomial Time Approximation Scheme for the Parallel-Machine case).Algorithm FPStep 1.For any given instance and any given ε ＞Step 2.Scale and round down the processing times and release dates of the original instance suchStep 3.Apply the dynamic programming algorithm presented above to the scaled and rounded down data and return the resulting schedule to theoriginal instance.Theorem 2.Algorithm FP is a fully polynomial time approximation scheme for the problemwith a fixed number of distinct release dates and a fixed number of machines.Proof.Sincethe time complexity of Algorithm FP for the scaled and rounded down data is as follows.Let be the optimal makespan with respect tothe original instance，andC'maxbe the optimal makespan with respect to the instance with processing times Mp'jand release dates Mr'j，and Cmaxbe the makespan obtained by Algorithm FP with respect to the original instance.Because the resulting schedule is optimal to the instance with processing times p'jand release dates r'j，it is also optimal to the instance with processing timesMp'jand release dates Mr'j.Since Mp'j≤pj＜M(p'j+1)and Mr'j≤rj＜M(r'j+1)，we haveBecause the time complexity of Algorithm FP is polynomial in the instance size and inwhen the number of distinct release dates and the number of machines are fixed，and for any given ε ＞0，it is a(1+ ε)-approximation algorithm，so it is a fully polynomial time approximation scheme. References【相关文献】1 Lee C Y，Uzsoy R.Minimizing makespan on a single batch processing machine with dynamic job arrivals.International Journal of Production Research，1999;37:219—2362 Graham R L，Lawler E L，Lenstra J K，et al.Optimization and approximation in deterministic sequencing and scheduling:a survey.Annals of Discrete Mathematics，1979;5:287—3263 Brucker P，Gladky A，Hoogevreen H，et al.Scheduling a batching machine.Journal of Scheduling，1998;1:31—544 Liu Z H，Yu W C.Scheduling one batch processor subject to job release dates.Discrete Applied Mathematics，2000;105:129—1365 Deng X T，Poon C K，Zhang Y Z.Approximation algorithms in batch processing. JournalofCombinatorialOptimization， 2003; 7:247—2576 Li S G，Li G J，Zhang S Q.Minimizing makespan with release times on identical parallel batching machines.Discrete Applied Mathematics，2005;148:127—134。

带精确时间延迟的排序问题文章主要研究带精确延迟时间的排序问题，目标是极小化加权总完工时间，分别给出了单台机和两台流水作业的最优算法。

标签：排序问题；最优算法；延迟引言精确时间延迟排序问题按机器数量分为单机问题和两台机流水作业问题。

用三参数分别表示为1|exact lj|Cmax，F2|exact lj|Cmax。

本文主要研究带精确时间延迟的单机排序问题和两台机流水作业排序问题。

每个工件Jj（j=1，2，…，n）有两道工序aj、bj，第一道工序先于第二道工序加工，第一道工序的完工时间c 与第二道工序的开始时间S之间存在一个精确的延迟时间，即S=c+lj。

所有工序操作时间都相等aj=bj=a，且精确延误时间是工序操作时间的整数倍lj=ka（k∈N+）。

现有文献考虑的目标函数大多是以最小化时间表长（makespan）为目标函数.本文所考虑的目标函数是最小化加权总完工时间（？撞wjCj）。

1 预备结果下面先给出相关的定义以及一些初步的结论。

定义1.1 将k个工件的第一道工序连续加工，再按照第一道工序的加工顺序连续加工这k个工件的第二道工序。

当第k个工件的第一道工序ak的完工时间与第一个工件的第二道工序b1的最早开工时间之间存在被迫空闲时，我们称之为被迫不连续加工（图1）。

图1 被迫不连续加工引理1.1 最优排序中，只存在被迫不连续加工和？资+1-连续加工这两种加工方式，即不存在m（m>k+1或mk+1时，精确延迟时间大于ka；当mk+1或mk+1三種情况。

情形一：当m+nk+1时，将这两组工件放在一起加工，变为一组k+1-连续加工工件和一组被迫不连续加工工件；这组被迫不连续加工的工件个数为m+n-k-1个。

这m+n个工件的总完工时间为比较这两个总完工时间知由2-（5）、2-（7）、2-（9）式可知，将第二组被迫不连续加工的工件前移，总完工时间不会变大。

即最优排序不可能存在两组或者两组以上被迫不连续加工的工件。

曲阜师范大学硕士学位论文最大延迟时间的极小化分批排序问题姓名：***申请学位级别：硕士专业：运筹学与控制论指导教师：***2002.3.20曲阜师范大学硕士学位毕业论文最大延迟时间的极小化分批排序问题摘要在实际生产中，存在大量成批加工的问题，即如何分批，以便使某一目标函数达到最优的问题，论文主要研究了目标为极小化最大延迟时间的分批排序问题．本文分三部分来介绍，第一部分（前言）介绍排序和分批排序问题的产生背景及一些基本的相关知识．第二部分对于Ｍ台同类机，工件的到达时间相同的情况，提出了分批问题ＱＩ引Ｃ．。

的算法ＢＬＳ，算法ＢＬＰＴ以及根据ＭＦ算法改进的一些算法，然后，针对这些算法，给出了分批排序问题ＱＩＢＩＬ…的最坏性能比分析．第三部分研究了单台批处理机器，工件的到达时间不同，以极小化最大延迟时间为目标的分批排序问题ｌｈ．Ｂ；￡…．论文提出了一些近似算法，给出该了问题相应的最差性能比界．算法ＢＬＳ和算法ＢＥＤＤ得到一个性能指标为Ｉ＋Ｂ．贪婪算法ＱＲＬＰＴ给出原问题的一个最差性能比为３．关键词／分批排影同类机√近似算ｉ璺；丫／ＮＰ．完备性，Ｌｓ算法，ＬＰＴ算法，最差性能｝Ｂ丫儡大延迟时间．Ｖ●第一章前言§１．１排序若干个工件要在一台或多台机器上加工，如何安排机器和工件，使得某些要求（目标函数）达到最优，这就是所谓的排序问题【３７】．排序在编制作业计划，企业管理，航空航天，医疗卫生等各个领域都有着广泛的应用．经过几十年的发展，排序理论与算法已是组合最优化中的一个重要分支，目前国际上通用的排序问题的分类方法为Ｌａｗｅｒ等（１９８９）提出的三参数分类法，即“川１，其中：Ｑ＝＆１“２指描述机器的状况，这里０２指机器数，Ｑ１∈｛０Ｐ．Ｑ．Ｒ，…），集合中各元素的含义是：０）：一台机器，记号０可以省略，Ｐ‘：同型号机器（ｉｄｅｎｔｉｃａｌｍａｃｈｉｎｅ），Ｑ：同种类机器（ｕｎｉｆｏｒｍｍａｃｈｉｎｅ），Ｒ：不同类机器（１１１１１ｎｌａｔｅｄｍａｃｈｉｎｅ）．０∈｛Ｄ．ｒ．Ｂ．ｐｌ＋ｅＣ．Ｐｊ＝１．…｝：描述工件的状况，例如Ｂ：指工件可分批加工，ｒ：指工件具有不同的准备时间ｐｒｅｃ：指工件间存在优先加工约束，Ｐ，＝１：指所有被加工的工件的加工ＢｅＮ相同．７：表示目标函数．省略号表示机器或工件的其它状况，如机器的流水，有序或自由作业和工件的打断等等，没有涉及不再陈述．本文所涉及的目标函数主要有ｃｋ…工。

带时间延迟的排序问题综述作者：王焕男来源：《科技创新与应用》2017年第07期摘要：近年来，排序问题受到多数学者的重视。

同时，在理论和实际方面出现很多新模型.关于多工序的工件排序中，通常认为前面的工序完成之后，后面的工序便可开始加工；可是现实并非如此，各工序之间也需要一定的时间延迟。

文章介绍了带时间延迟排序问题的研究现状及相关算法。

关键词：排序问题；最优算法；延迟引言对于带有时间延迟的排序问题，可分为两类，一类是对工件Jj的两道工序间至少需要延迟lj个单位时间，我们称这类问题为至少时间延迟排序。

另一类是前后两道工序间时间延迟刚好为lj个单位时间（exact delay），我们称这类问题为精确时间延迟排序。

目前，关于以上这两类问题的研究，主要集中于单台机和两台机的流水作业问题，并且，多数以极小化最大完工时间为目标（makespan），考虑总完工时间的文献很少。

多工序排序问题可以分为无时间延迟（lj=0）流水作业排序问题，带有至少lj个单位时间延迟的排序问题，带有精确时间延迟的排序问题。

1 无时间延迟排序问题对两台机流水作业问题F2|no-wait|Cmax，Johnson给出了一个O（n log n）的最优算法。

对目标函数是最小化总完工时间问题F2|no-wait|Cj，van Deman和Baker提出一个分支定界算法；Rck证明了这个问题是强NP-难的。

当每个工序的操作时间Pi，j{0，1}时，Gonzales证明F|no-wait，Pi，j{0，1}|Cj是强NP-完全问题；两台时，Sriskarajah和Ladet证明F2|no-wait，Pi，j{0，1}|Cj多项式时间可解。

Rajendran 和 Chaudhuri对无时间延迟两台机流水作业排序问题提出一个工件插入启发式算法（insertion heuristic）。

Chen et al. 对无时间延迟两台机流水作业排序问题提出一个遗传算法和一些计算结果。