学位论文 > 优秀研究生学位论文题录展示

具有等长工件平行批排序模型的一些结果

作　者: 孙晓梅
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 单机排序平行批工期最大延迟优先约束加权误工和
分类号: O223
类　型: 硕士论文
年　份: 2007年
下　载: 33次
引　用: 0次
阅　读: 论文下载

内容摘要

排序（SCheduling）就是在一定的约束条件下对工件和机器按时间进行分配和安排加工次序，使一个或多个目标达到最优．排序论作为运筹学的一个重要分支，目前受到国内外学者的广泛关注．本文主要对于等长工件平行批排序模型进行了研究，作了以下两方面的工作：（1）具有优先约束、到达时间、等长工件的单机平行批排序问题；（2）具有到达时间、加工时间相同，极小化加权总误工的单机平行批排序问题．一个批机器或批加工机器是指可同时将几个工件作为一批进行加工的机器，每一批的加工时间等于这批工件中最长的加工时间．一旦一批工件开始加工就不能被中断，其他工件也不能加入该批．本文中研究的问题可描述如下：假设有n个工件J₁，J₂，…J_n，一台在给定的时间内只能加工一批工件的机器．工件之间具有优先约束关系，每个工件J_j有加工时间p_j和到达时间r_j（其中p_j，r_j都为整数）．工件是成批被加工处理的，这里的一批是指工件的一个子集，这些批（子集）构成了工件集的一个划分．一个批的加工时间等于这批工件中最大的加工时间，即p_x=maX{p_j∶J_j∈B_x}．如果工件J_i，J_j有优先约束J_j（?）J_j，则要求J_j一定要在J_j真完工后加工．这意味着J_i真和J_j不能在同一批中被加工．一批的完工时间定义为该批所有工件的完工时间，即C_x=s_x+max{p_j∶J_j∈B_x}．参照文献[1]，[2]，我们称这个排序模型为平行批排序问题，记为1|prec；p-batch；r_j|f这里f是要优化的目标函数．主要结果如下：（1）具有优先约束、到达时间、等长工件的单机平行批排序问题。我们对于具有优先约束，k个不同到达时间，等长工件的最大延迟极小化单机平行批排序问题进行了研究．首先，对于有固定k个不同到达时间r_i（1≤i≤k）的平行批排序模型，给出块的概念．进而证明在最优排序中所有块的构形是这样的时间序列(r^（1），r^（2），…，r^（n_b）)（1≤n_b≤k），其中r^（i）∈{r_（1），r^<sub>（2），…，r_（k）}．其次，对于所有可能的构形进行枚举，并给出一个O（2^kn log kn²）时间的算法求解L_max最优值．最后对于问题1|prec；p-batch；p_j=p；r₍（i），i∈{1，2，…，k}|f，当f为和函数∑f_j形式，即f∈{∑ω_jC_j，∑C_j，∑U_j，∑ω_jU_j，∑T_j，∑ω_jT_j}时，给出了一个O（2^kn）时间算法．当k为一固定值时，这两个问题是多项式可解的．（2）具有到达时间，加工时间相同极小化加权总误工的单机平行批排序问题．Baptiste在[5]中给出了问题1|p-batch；b＜n；p_j=p；r_j|f，f∈{∑ω_jU_j，∑ω_jC_j，∑T_j}的一个O（n⁸）时间的动态规划算法，并指出对于目标函数∑ω_jT_j，平行批等长工件问题的计算复杂性仍是未解的。本文中，我们将讨论问题1|p-batch；b＜n；p_j=p；r_j|∑ω_jT_j，首先，我们假设ω₁≥ω₂≥…≥ω_n，且d₁≤d₂≤…≤d_n，即工件的权数与工期是反一致的．此时，通过适当的修正，∑ω_jT_j就为一个有序的目标函数，这使得我们的排序问题具有特定的优势性质．其次，建立动态规划参数及方程，给出一个O（b²n⁷）（b＜n）的时间动态规划算法求解最优值．

全文目录

摘要  4-6
Abstract  6-9
第一章引言  9-18
  §1.1 排序的介绍  9-13
  §1.2 平行批排序问题  13-15
  §1.3 排序的记号  15-16
  §1.4 已知结果及本文主要结果  16-18
第二章具有优先约束,到达时间,等长工件的单机平行批排序问题  18-27
  §2.1 相关介绍  18-21
  §2.2 主要结果证明  21-27
第三章具有到达时间,加工时间相同极小化加权总误工的单机平行批排序问题  27-36
  §3.1 基本概念  27-29
  §3.2 动态规划算法  29-36
进一步研究  36-37
参考文献  37-40
附录:硕士期间完成论文  40-41
致谢  41

具有等长工件平行批排序模型的一些结果

内容摘要

全文目录

相似论文