带配送时间在线分批调度问题

《带配送时间在线分批调度问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、曲阜师范大学硕士学位论文带配送时间的在线分批调度问题摘要排序问题是一类重要的组合优化问题，它被广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域，一直受到国内外学术界的重视．分批排序问题和在线排序问题是两类新兴的现代排序模型，有着重要的应用背景，而带配送时间的在线分批排序问题是排序论在供应链理论中应用的重要体现．本文主要研究带配送配送时间的在线分批排序问题．论文共分为三章：・第一章主要介绍了排序问题产生的背景，计算复杂性理论，分批排序，在线与半在线排序的概念以及本文的主要结果和创新点．第二章主要对分批加工在两种配送模型下的在线算法

2、进行了分析．这两种模型分别为：分批加工、独立配送模型以及分批加工、按批配送模型．首先证明了在独立配送模型下我石，２一个半在线理论；首次提出了一种新的配送模型：按批配送模型，并对按批配送与独立配送的同一个算法的竞争比进行了分析．第三章首次研究了成比例排序问题ＢＰＰ的同类机分批排序，目标函数为极小化工件的最大完工时间，这类问题也是Ｎ卜完备的．我们对同类机的情形给出了近似算法ＱＢＦＦ和Ｄ１ＱＭ，并且证明了它们的竞争比分别不超过＝＋１（其中口＝ｍｉｎ｛ａｊ｝）和妄＋ｐ（其中ｐ＝（ｍ－１）ＳＬｉＺｓ，）．ｆ皇ｌ关键词分批排序：在线排序：竞争比：近似算法

3、：配送时间们考虑的两个问题的竞争比均为ｌ＋万，其中艿：掣；并首次提出了独立配送模型下的曲阜师范大学硕士学位论文Ｏｎ－－ｌｉｎｅｂａｔｃｈｓｃｈｅｄｕｌｉｎｇｗｉｔｈｄｅｌｉｖｅｒｙｔｉｍｅＡｂｓｔｒａｃｔＳｃｈｅｄｕｌｉｎｇｉｓａｌｌｉｍｐｏｒｔａｎｔｒｅｓｅａｒｃｈｆｉｅｌｄｏｆｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｔｉｓｗｉｄｅｌｙｕｓｅｄｉｎｓｃｉｅｎｔｉｆｉｃｍａｎａｇｅｍｅｎｔ，ｃｏｍｐｕｔｅｒｓｃｉｅｎｃｅ，ｉｎｄｕｓｔｒｉａｌａｎｄａｇｒｉｃｕｌｔｕｒａｌｐｒｏｄｕｃｔｉｏｎ，ｔｒａｎｓｐｏｒｔｉｏｎａｎｄ

4、ｏｔｈｅｒｓｅｃｔｏｒｓ．Ｂａｔｃｈｓｃｈｅｄｕｌｉｎｇａｎｄｏｎ—ｌｉｎｅｓｃｈｅｄｕｌｉｎｇａｒｅｔｗｏｎｅｗｋｉｎｄｓｏｆｍｏｄｅｍｓｃｈｅｄｕｌｉｎｇｍｏｄｅｌｓ．Ｔｈｅｙｂｏｔｈｈａｖｅｖｅｒｙｉｍｐｏｒｔａｎｔａｐｐｌｙｉｎｇｍｅａｎｉｎｇｓ．Ｗｈｉｌｅｔｈｅｏｎ—ｌｉｎｅｂａｔｃｈｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓｗｉｔｈｄｅｌｉｖｅｒｙｔｉｍｅｉｓａｎｉｍｐｏｒｔａｎｔｍａｎｉｆｅｓｔａｔｉｏｎｏｆｔｈｅａｐｐｌｉｃａｔｉｏｎｉｎｓｕｐｐｌｙ－ｃｈａｉｎｔｈｅｏｒｙ．Ｔｈｉｓａｒｔｉｃｌｅｉｓａｂｏｕ

5、ｔｔｈｅｓｔｕｄｙｆｏｒｔｈｉｓｐｒｏｂｌｅｍ．Ｔｈｅｒｅａｒｅｔｈｒｅｅｃｈａｐｔｅｒｓｉｎｔｈｉｓｐａｐｅｒ．Ｉｎｔｈｅｆｉｒｓｔｃｈａｐｔｅｒ，ｓｏｍｅｎｏｔａｔｉｏｎｓ，ｄｅｆｉｎｉｔｉｏｎｓａｎｄｂａｓｉｃｂａｃｋｇｒｏｕｎｄｉｎｆｏｒｍａｔｉｏｎａｂｏｕｔｔｈｅｓｃｈｅｄｕｌｉｎｇｔｈｅｏｒｙａｒｅｉｎｔｒｏｄｕｃｅｄ．Ｗｅｍａｉｎｌｙｉｎｔｒｏｄｕｃｅｔｈｅｃｏｍｐｕｔａｔｉｏｎａｌｃｏｍｐｌｅｘｉｔｙｔｈｅｏｒｙ，ｂａｔｃｈｓｃｈｅｄｕｌｉｎｇ，ｏｎ—ｌｉｎｅｓｃｈｅｄｕｌｉｎｇｍａｉｎｒｅｓｕｌｔｓａｎｄｉｎｎｏｖａ

6、ｔｉｏｎｓｏｆｔｈｉｓｐａｐｅｒ．ａｎｄｔｈｅＩｎｔｈｅｓｅｃｏｎｄｃｈａｐｔｅｒ，ｗｅｍａｉｎｌｙａｎａｌｙｚｅｔｈｅｏｎ－ｌｉｎｅａｌｇｏｒｉｔｈｍｓｏｆｔｗｏｍｏｄｌｅｓｗｉｔｈｄｅｌｉｖｅｒｙｔｉｍｅａｎｄｂａｔｃｈｐｒｏｃｅｓｓｉｎｇ．Ｔｈｅｙａｒｅｉｎｄｅｐｅｎｄｅｎｔｄｅｌｉｖｅｒｙｍｏｄｅｌａｎｄｂａｔｃｈｄｅｌｉｖｅｒｙｍｏｄｌｅｗｉｔｈｂａｔｃｈｐｒｏｃｅｓｓｉｎｇ．Ｗｅｐｒｏｖｅｔｈａｔｔｈｅｃｏｍｐｅｔｉｔｉｖｅｒａｔｉｏｏｆｔｗｏｓｐｅｃｉａｌｐｒｏｂｌｅｍｓｉｎｉｎｄｅｐｅｎｄｅｎｔｄｅｌｉｖｅｒ

7、ｙｍｏｄｅｌｂｏｔｈａｒｅ１＋８，ｗｈｅｒｅ万＝丁，ｆ５－１．Ｗｅｐｒｅｓｅｎｔａｓｅｍｉ。ｎ－ｌｉｎｅｔｈｅｏｒｙｆｏｒｔｈｅｉｎｄｅｐｅｎｄｅｎｔｄｅｌｉｖｅｒｙｍｏｄｅｌｆｏｒｔｈｅｆｉｒｓｔｔｉｍｅ，ａｎｄａｌｓｏｗｅｆｉｒｓｔｌｙｐｒｅｓｅｎｔａｎｅｗｄｅｌｉｖｅｒｙｍｏｄｅｌ，ｔｈａｔｉｓｂａｔｃｈ曲阜师范大学硕士学位论文ｄｅｌｉｖｅｒｙｍｏｄｅｌ．Ｉｎｔｈｅｅｎｄｗｅａｎａｌｙｚｅｔｈｅｃｏｍｐｅｔｉｔｉｖｅｒａｔｉｏｏｆｔｈｅｓａｍｅａｌｇｏｒｉｔｈｍｆｏｒｔｈｅｔｗｏｍｏｄｅｌｓ．Ｉｎｔｈｅｔｈｉｒｄｃｈａｐ

8、ｔｅｒｗｅｃｏｎｓｉｄｅｔｈｅｐｒｏｐｏｒｔｉｏｎｅｄｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓＢＰＰｉｎｂａｔｃｈｉｎｇｕｎｉｆｏｍｐａｌｒａｌｍａ