单机分族分批排序的最小误工个数问题.pdfVIP

第 2l卷第 5期 四川理工学院学报 (自然科学版) Vo1．21No．5 JOURNAL OF SICHUAN UNIVERSITY OF 2008年 10月 SCIENCEENGINEERING(NATURALSCIENCEEDITION) Oct．2008 文章编号 ：1673-1549(2008)05-0019-03 单机分族分批排序的最小误工个数问题 曹国梅 (郑州旅游职业学院，郑州450009) 摘 要：文章研究了同一族内，给出并证明了其最优排序的性质。对工件到达时间和工期相一致时的情形，得 出了一个时间复杂性为D(m6(里) 的动态规划算法。 m 关键词：排序；平行批分族排序；误工工件个数；动态规划 中图分类号：0223 文献标识码：A 引 言 (1)批 EDD序(batch—EDDOrder)：对于任意两批工 平行批排序(parallelbatchingproblems)是应用背景 件P和Q，若批 P排在批 Q之前，并且不存在工件 ，， 极强的一类最优化问题，它打破 了经典排序中一台机器 ∈尸，∈Q)使didj，则称此排序是批EDD序。 在 同一时间只能处理一个工件的约束。它要求每一批工 (2)不误工批：若在一批中，所有工件都是不误工 件一旦开始加工就不能被中断，其他工件也不能加入该 的，称此批为不误工批。 批，每批工件的加工时间是这批工件中所有工件加工时 (3)批 SPT序(batch—SPTOrder)：对于任意两批工件 间的最大者，每批工件的开工时间不小于该批中最晚到 P和Q，若批P排在批 Q之前，并且不存在工件 ，， 达的工件的到达时间，属于同一批的工件 同时开工且同 ∈蹦 ∈p)使 ，则称此排序是批SPT序。 时完工，工件的完工时间为该批所有工件的完工时间。 (4)r和 d一致：对 n个工件编号，使 r r2 … 。 本文所讨论的不相容工件族的分批排序是平行批排序 若由rlr2 …--r，可得dld2≤… ，则称r和d是 中的新概念，有其深刻的应用背景。例如，一批物质需要 一 致的，记为 agr(ri，di)。 在一个充分大的窑里加热，这时每批的批容量就没有限 本文在每一族内工件加工时间相同、工件的工期和 制，且一个窑里可以加工多种类型的产品，但不同类型 到达时间一致时，考虑了使所有误工工件的总数∑ 最 的产品不能在一起加工，否则会起化学反应。此问题的 小的最优分批和最优各批加工顺序。 一 般模型可简单描述如下：有n个工件 ，，…，要在一 此问题参照文献 【1】，采用国际上通用的三参数法可 台容量为b的批处理机上加工，这n个工件分别属于m 表示为 lflamily-jobs；P-batch；arg(P)I∑ 。 个互不相容的工件族 ，，…，，它们分别有nbrt，…，n 由于分批排序的应用背景，误工总数问题受到了广 个工件 (在这里n=n+n+…+n2，其构成形式为 = l1，J 泛的关注，国际上许多专家投身于此，新的成果不断涌 ㈣…，叫}，1 m。若工件 的工期(交货期)为 ，加 现。Brock等在文献2【】中给出了问题 1IP-batch，rj∈{r。 工时间为％ ，到达时间为 ，完工时间为C㈤。设批B r2 … rm}I∑ 的时问复杂性为O(B22~n2)的动态规划 的加工时间为P(，则P(B)=maxlP@： E 定义工件的 算法；Li和Lee在文献3【】中证明了当r与d或P与d相 误