若干批处理机排序与装箱问题的算法研究

论文题目: 若干批处理机排序与装箱问题的算法研究

论文类型: 博士论文

论文专业: 运筹学

作者: 石永强

导师: 姚恩瑜,张国川

关键词: 批处理机排序,在线算法,竞争比,变尺寸装箱,装箱,渐进性能比

文献来源: 浙江大学

发表年度: 2005

论文摘要: 本文主要研究了批处理机排序和装箱问题的一些新模型．排序问题和装箱问题都是经典的组合优化问题，受到众多学者的关注。随着社会的发展，又不断地产生一些新模型．批处理机排序问题就来源于现实生活中的半导体以及大规模集成电路生产中的产品检验阶段，一台机器可以同时对多个工件进行加工，只要工件的尺寸和不超出机器的容量．同时加工的工件称为一批，其加工时间是批中最长的工件的加工时间。我们对两种单台批处理机排序的在线模型进行了研究。变尺寸装箱问题来源于运输公司货车的调度问题，不同货车所需的费用不同，如何安排才能使费用尽可能少；而Open-end装箱则来源于香港市民日常乘坐地铁，市民的地铁票在最后一次使用时允许金额不足而不需再追加缴费，最少买几张票就可以满足市民的日常需求。我们研究了相应的算法并对算法进行了分析。全文共分六章。第一章介绍组合优化问题的一些基本概念、算法及其性能衡量，并简要介绍本文的工作。其余五章可分为两部分，第一部分由第二、三、四章组成，第二章对已有的批处理机排序问题的历史文献以及相关的研究结果进行详细的综述，三、四章则讨论了两种批处理机排序问题的模型；第二部分为第五、六章，分别讨论了装箱问题的两个模型：变尺寸装箱和Open-end装箱。单台批处理机在线排序问题描述如下：给定一台批处理机M，它的容量为B；又给定工件集L，每个工件有加工时间p_j、到达时间r_j和尺寸s_j(0＜s_j≤B，(?)_i=1，2，…，n)，工件到达前信息未知。M能够同时加工多个工件，只要这些工件的尺寸总和不超过B，这些同时加工的工件称为一批，它们同时开始加工，同时结束；加工过程中不允许中断，也不允许放入或拿出工件；将批中最长工件的加工时间记为该批的加工时间。目标是极小化最大完工时间(makespan)。我们是最早对工件尺寸不同的在线模型进行研究的。我们首先讨论了工件加工时间相同的模型，

论文目录:

摘要

Abstract

第一章绪论

1.1 组合优化问题

1.1.1 排序问题

1.1.2 装箱问题

1.2 算法的分类及性能

1.3 论文概述

第二章批处理机排序问题综述

2.1 背景与问题描述

2.1.1 背景

2.1.2 问题描述

2.2 成组分批排序

2.2.1 单台机

2.2.2 平行机

2.2.3 作业问题

2.2.4 同一组中的工件完全一样

2.2.5 满足batch availability假设

2.3 批处理机排序

2.3.1 离线模型

2.3.2 在线模型

2.3.3 工件尺寸不同的模型

第三章工件加工时间相同尺寸不同的单机在线批处理机排序问题

3.1 问题模型

3.2 贪婪算法

3.3 一个改进算法

第四章一般的单机在线批处理机排序问题

4.1 问题模型

4.2 预备知识

4.3 工件只有不同的两个到达时间

4.4 工件有多个到达时间的一般情形

第五章变尺寸装箱问题

5.1 问题概述

5.2 原始的变尺寸装箱问题

5.2.1 几个在线算法的绝对比

5.2.2 自行设计箱子容量的模型

5.3 广义的变尺寸装箱问题

5.3.1 两个启发式算法

5.3.2 特殊情形的问题

5.3.3 一般情形研究

第六章 Open-end装箱问题

6.1 问题概述

6.2 一个引理

6.3 性能比分析

参考文献

致谢

攻读博士期间完成的文章

发布时间: 2006-09-05

参考文献

[1].二维装箱问题的非线性优化方法[D]. 于洪霞.大连理工大学2006
[2].与装箱相关的几类问题[D]. 余国松.浙江大学2009

若干批处理机排序与装箱问题的算法研究

猜你喜欢