带有恶化效应的单机供应链排序问题-数学、运筹学与控制论专业论文.docxVIP

I万方数据 I 万方数据 带有恶化效应的单机供应链排序问题 摘要 排序论是运筹学中最重要的分支之一。供应链排序是供应链管理与排序理论相结合产 生的新领域,它将排序理论应用于供应链管理,集成研究生产调度和分批配送这两个问题。 工件带有恶化效应的排序和工件可拒绝的排序是两种新兴起的现代排序模型,它们更接近 现实生活,因而具有很好的研究价值。本文将上述三类排序问题相结合,讨论了几个相关的 排序问题。论文主要结构安排如下： 第一章绪论部分主要介绍了供应链排序问题、带有恶化效应的排序问题、可拒绝排序, 算法的复杂性以及本文所需要的基础知识,并对本文的主要工作进行了简要描述。 第二章主要研究了带有恶化效应的单机供应链排序问题：一个制造商为一个客户加工 工件,每个工件的加工时间是其开工时间的简单线性增函数,工件加工完之后要安排车辆 配送给客户,完工时间为工件送达客户的时刻。在同一辆车配送的工件为一批,每一批可同 时配送至多 z ??n 个工件,每配送一批要支付一定的配送费用。我们分析了加工时间为其开 工时间的不同函数,目标函数分别为极小化总完工时间与总配送费用之和、极小化最大延 误时间与总配送费用之和的情形,并分别给出了多项式时间的最优算法。 第三章在第二章的基础上研究了工件可拒绝的情形。一个制造商为一个客户加工工件, 每个工件既可以被接受加工,也可以被拒绝加工。若工件被拒绝,则要支付一定的拒绝费 用。若工件被接受,则其加工时间是其开工时间的简单线性增函数,且加工完之后要被安排 在车辆运送给客户,完工时间为工件送达客户的时间。在同一辆车配送的工件为一批,每配 送一批要支付一定的配送费用,每一批可同时配送至多 z ??n 个工件。目标函数为极小化被 接受工件的总完工时间、总配送费用和被拒绝工件的总拒绝费用三者之和,本文对这个问 题给出了运行时间为多项式的动态规划算法。 关键词 单处理机,供应链排序,可拒绝,分批配送,动态规划,线性恶化 II万方数据 II 万方数据 Supply Chain Scheduling on Single Machine with Deterioration Abstract The theory of scheduling is one of the most important branches in operations research. Supply chain scheduling is a new area that integrates scheduling and batch delivery. Scheduling with deterioration and scheduling with rejection are two new scheduling models, which attract more and more attention recently. In this thesis we combine three scheduling theories mentioned above and discuss three related problems. The structure of this article is as follows: The first chapter introduces some notions that we will use in this thesis. Such as what are supply chain scheduling and scheduling with deterioration, the definition of the co mplexity of algorithms, and so on. Then the main work of this paper is briefly summarized in this chapter. In the second chapter, we study some problems of supply chain scheduling with deterioration. Jobs belong to one customer which should be processed by a manufacturer on a single machine. The processing time of each job is a simple linear increasing function of its starting time. After being processed, the jobs should be delivered to