带有多交货期窗口的单机排序问题

摘要

排序作为运筹学领域的一个新兴重要组成部分,现已渗透于当今社会生活的众多方面。排序问题主要研究如何通过合理地安排任务加工顺序使得相关成本最低。本文主要讨论带有多个交货期窗口的单机排序问题。主要内容有以下几个方面：
　　第一章，主要介绍该问题的研究背景、发展现状以及完成本篇论文所搜集到的相关资料。
　　第二章，主要介绍带有多个交货期窗口、退化效应与退化维护活动的单机排序问题。国内外越来越多的研究人员将交货期窗口考虑到排序问题中，本章在研究多交货期窗口的单机排序问题基础上，提出把维修活动以及任务的退化效应考虑到排序问题中。本章假设任务的实际加工时间是一个与该任务加工位置有关的函数，且任意两个交货期窗口不能重叠。对机器的维护过程结束后，机器就恢复到出厂设置，与此同时任务的退化效应也会恢复到最初，本章假定对机器进行维护所需要的时间取决于机器什么时候开始维护的，并将所有待加工的任务分成若干个任务集合，且所有任务集合的个数已知，每一个任务集合共享一个交货期窗口。本章的目标是得到每个任务集合最优交货期窗口的位置、大小和维护活动的最佳位置、以及所有任务的最佳加工顺序使任务的提前惩罚与延误惩罚、每个交货期窗口开始时间及交货期窗口宽度费用之和最小。证明可以通过将该研究问题转化为指派问题求解。
　　第三章，主要介绍带有多个松弛窗口、公共流、维护和资源分配的单机排序问题，并着重考虑在一定的资源约束下如何寻求最优解。本章假定所有的任务都具有一个松弛窗口，窗口的长度随着任务的不同而不同。在工厂生产过程中，为了提高生产效率，会提供给相应的任务一些资源，但资源并不是无限的，资源过多容易使成本加大，通常我们假定资源有限，并且在合适的时间会对机器进行维护，保证机器的正常加工状态。当机器的维护活动结束后，机器会恢复到出厂状态，与此同时任务的退化效应也会恢复到最初。本章的目标是确定任务的松弛窗口的位置、资源分配情况、任务最佳排序使得提前、延误惩罚、松弛窗口的位置、松弛窗口的宽度、时间表长、所有任务的完工时间总和及资源消耗情况之和最小。证明可以将该问题转化为指派问题求解。
　　最后，对全文的内容进行了总结分析。

目录

声明

第一章 绪论

一、 排序问题研究背景

二、三参数表示法及符号说明

三、排序问题的国内外研究现状

四、本文主要内容及结果

第二章 带有多交货期窗口的单机排序问题

一、引言

二、问题描述

三、准备工作

四、最优解

五、小结

第三章 具有公共流、资源分配的单机窗口排序问题

一、引言

二、问题描述

三、预备知识

四、最优解

五、实例

六、小结

结论

参考文献

致谢

个人简历

在学期间的研究成果和发表的学术论文