论文总字数：40009字

摘 要

本文首先介绍了二维条带资源调度问题的定义以及公式化，接着介绍了二维条带填充问题中的一些上下界，用以分析各近似算法和精确算法的最终结果与理论界限之间的接近程度，是衡量算法性能的一个指标。随后介绍了分支定界算法，用以求解二维条带填充问题。分支定界算法分为两个步骤，分别是分支操作和定界操作。在分支操作中，有左下角分支策略和阶梯分支策略。在定界操作中，主要有3类算法判断是否继续填充当前分支，若不满足继续填充条件，则结束当前分支节省时间开销。这3类分别是动态规划切割（DP切割），基于阶梯放置和剩余矩形的边界规则和LP切割。最后介绍了任务集排序策略，包括最大宽度（高度）优先(LWHF)，最大高度（宽度）优先(LHWF)，最大面积（高度）优先(LAHF)，最大面积（宽度）优先(LAWF)，随机序列(RL)和综合模型（Syn）。使用各排序策略再结合分支定界算法得到6种启发式算法。除此之外还对任务集进行全排列，对每一序列都应用分支定界算法，可获得条带高度最小的精确算法。

关键词：条带调度算法，分支定界，精确算法，启发式算法

Abstract

Firstly, this paper introduces the definition and formulation of two-dimensional strip resource scheduling problem. Then it introduces some upper and lower bounds of two-dimensional strip filling problem to measure the performance of each approximation algorithm and the precise algorithm. The branch and bound algorithm is introduced to solve the two-dimensional strip filling problem. It includes two steps -- one is branch operation and the other is bound operation. In the branching operation, there are left-bottom corner branching strategy and ladder branching strategy. In the bounding operation, there are mainly three kinds of algorithms to determine whether to continue filling the current branch or not. If the condition of continuing filling is not satisfied, the current branch will be terminated to save time and overhead. These three types are dynamic programming cutting, boundary rules based on step placement and residual rectangle and LP cutting. Finally, job set sorting strategies are introduced, including maximum width (height) priority (LWHF), maximum height (width) priority (LHWF), maximum area (height) priority (LAHF), maximum area (width) priority (LAWF), random sequence (RL) and synthetic model (Syn). Six heuristic algorithms are obtained by using each sorting strategy combined with branch and bound algorithm. In addition, the task set is fully arranged and the branch-and-bound algorithm is applied to each sequence to obtain the exact algorithm with the smallest strip height.

KEY WORDS: strip scheduling algorithm, branch and bound algorithm, exact algorithm, heuristic algorithm

目 录

摘 要 I

Abstract II

第一章 绪论 1

1.1引言 1

1.2公式化 2

1.3本文的主要研究内容及结构安排 3

第二章 基于分支定界的精确算法 5

2.1定义上下界 5

2.1.1上界 5

2.1.2 下界 5

2.2分支定界法 8

2.3算法规则及流程 8

2.4分支规则 9

2.4.1基于左下角的分支 10

2.4.2基于阶梯放置的分支 10

2.4.3冗余检查 13

2.5定界操作 13

2.5.1动态规划切割（DP切割） 13

2.5.2基于阶梯放置和剩余矩形的边界规则 15

2.5.3 LP切割 15

2.6任务集序列策略 16

2.6.1最大宽度（高度）优先（LWHF） 17

2.6.2最大高度（宽度）优先（LHWF） 17

2.6.3最大面积（高度）优先（LAHF） 17

2.6.4最大面积（宽度）优先（LAWF） 17

2.6.5随机序列（RL） 18

2.6.6综合模型（Syn） 18

第三章 实验验证与结果分析 19

3.1生成矩形任务集 19

3.1.1均匀分布 19

3.1.2二项分布 19

3.1.3几何分布 19

3.2实验及其结果分析 19

3.2.1测试平台介绍 19

3.2.2实验流程 19

3.2.3实验数据及分析 20

第四章 总结与展望 30

4.1总结 30

4.2展望 30

参考文献 31

致 谢 34

第一章 绪论

1.1引言

广义的二维矩形填充问题中，给出一组个矩形物品，每个物品的宽度为，高度为 ，要求将所有给定的矩形正交放置到一个矩形容器中而不重叠，以使目标函数最小化或最大化。放置规则有多种选择，例如，允许或不允许旋转矩形，容器的宽度是否固定等等。本文中，我主要研究二维条带资源调度问题，也称为二维条带填充问题，该问题中个矩形任务等待调度,每个矩形任务有资源需求，资源占用时长需求 ()。调度算法须在给定的有限资源限制下，在每个时刻选择合适的一个或多个矩形任务执行，使得所有矩形任务的总高度最小而不重叠。该问题是众所周知的组合优化问题，它要求将所有给定的矩形任务不重叠放入宽度一定的条带容器中。不失一般性，我假设矩形任务和条带的尺寸是整数。

这个问题是显然的难问题，因为它是经典的难问题——多处理器调度问题的推广，即任意任务, ，满足。因此，大多数考虑该问题的论文都是近似算法或带断头切割为约束条件的精确算法。切割问题的一个常见限制是，在每个对象中，只能使用断头台切割，也就是说，平行于对象一侧的切割，从一侧到另一侧；这种类型的问题称为二维断头台切割问题。对这些问题的另一个常见限制是分阶段的削减。k阶段切割是最多k阶段切割的序列，其每个阶段是对在前一阶段中获得的对象执行的一组平行断头台切割。显然，每个阶段的切割必须与前一阶段的切割正交。在不失去一般性的情况下，切口是无限薄的。以断头切割为约束条件的精确算法要求切割是k阶段的，并且在第一阶段（执行水平切割）中，任何两个后续切割之间的距离最多为H。这个问题对应于二维矩形开放维数问题^[1]。许多实际应用对获得最终产品的切割阶段的数量有限制，特别是当切割材料的成本与切割过程中涉及的工业成本相比较低时。在图1（b）中，有一个3阶段的断头台模式（红色区域是一个浪费的区域）。分阶段切割中，第一个切割阶段是在水平方向上进行的。

剩余内容已隐藏，请支付后下载全文，论文总字数：40009字