带时间维度的Packing问题的研究

摘要

近年来，随着科学技术的迅猛发展，人们逐渐意识到时间就是效益，时间就是生命线.因而，在大规模的食品加工、车床加工过程中，怎样合理安排加工序列，以使得整体的加工时间最短，成为人们不断关注的话题. 在上述加工过程中，如果去除加工时间这一属性，它就是一个Packing问题.因而，我们可以将上述加工问题看成是一个带时间维度的Packing问题.该问题的求解过程与日常生活中的烤肉过程十分类似，所以本文中，我们把该类问题称为烤肉问题. 由于Packing问题是烤肉问题的一个子问题，而Packing问题是一个NP-难问题，所以我们的烤肉问题也是NP-难问题.也就是说，烤肉问题不存在多项式时间复杂度的最优解算法。因而，对于该问题的求解，我们转向寻求次优解.通常情况下，次优解的寻找方式分为两类，一类就是启发式算法，另一类就是近似算法.这两类算法各有利弊，前者算法设计简单，但是效果欠佳；后者算法设计难度大，但是效果良好而且稳定. 在烤肉序列是有序的情况下，我们引入加工方案的概念，并证明贪心算法就是烤肉问题的最优解算法.然而，在烤肉序列是无序的情况下，烤肉问题是NP一难问题，它不存在快速有效的最优解求解算法.鉴于此，对于一维的情况下，我们设计了几个启发式算法，并给出一个最坏情况下的近似算法以及基于书架思想的几个求解策略.在多维的情况下，一维情况下得到的相应的启发式算法效果比较差.此时，我们借助条形装箱问题，来求解烤肉问题.通过一系列的分析，我们提出了几个卓有成效的求解策略，特别是重力消失策略以及水平移动策略. 最后，我们还针对多烤炉无序烤肉问题，提出了选位策略与分割策略、以及最终调整策略，取得了显著的效果.

目录

文摘

英文文摘

声明

第一章 绪论

1.1研究背景

1.1.1烤肉问题的提出

1.1.2烤肉问题的具体描述

1.1.3烤肉问题的相关应用

1.2研究现状

1.3本文的主要工作

1.4本文的组织结构

第二章有序烤肉问题

2.1有序烤肉问题的定义

2.2单烤炉有序烤肉问题最优解算法

2.1.1基本概念

2.1.2引理

2.1.3定理

2.1.4小节

2.3多烤炉有序烤肉问题求解策略

第三章单烤炉无序烤肉问题

3.1 单烤炉一维无序烤肉问题

3.1.1启发式算法

3.1.2近似算法

3.1.3二维定向条形装箱问题的求解策略

3.1.4小节

3.2二维无序烤肉问题

第四章多烤炉无序烤肉问题

4.1多烤炉一维无序烤肉问题

4.2多烤炉多维无序烤肉问题

第五章总结与展望

5.1总结

5.2展望

致谢

发表文章

研究成果

参与项目

参考文献