订单可拒绝的批量排序问题

作     者：程晓璇 

作者单位：曲阜师范大学 

学位级别：硕士

导师姓名：邹娟

授予年度：2024年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：批量排序 订单可拒绝 伪多项式时间 近似算法 

摘      要：随着现代科技的迅速发展,制造业需要更加合理有效的生产模式,由此研究者们提出了许多新兴排序模型.本文所考虑的批排序模型称为批量排序(Lot scheduling),在批量排序模型中每个批次都有相同的加工时间与固定的容量.每个批次可能包含一个或多个不同尺寸的订单,且允许订单在两个连续的批次中被分割.在实际生产过程中,为了提高生产效率,制造商可能会决定只接受一部分订单,因此由于订单被拒绝或者外包,制造商会支付一定的拒绝费用.本文对于订单可拒绝的批量排序问题进行了相关研究.以下为本文5个章节的内容简介: 第1章主要介绍了批量排序问题的研究背景与研究成果,阐述了相关概念及本文的主要结论. 第2章研究了订单可拒绝的单机批量排序问题.主要解决了三个问题:(1)最小化接受订单的总完工时间与拒绝订单的总拒绝费用之和;(2)在拒绝订单的总拒绝费用不超过一个给定的上界的限制下,最小化接受订单的总完工时间;(3)最小化接受订单的最大完工时间与拒绝订单的总拒绝费用之和.首先证明了第一个问题是一般意义下NP-难的,并为前两个问题都提出了一个伪多项式时间算法.其次在最后一个问题中,我们考虑了三种情况:(1)订单有相同的到达时间;(2)订单有常数个不同的到达时间;(3)每个订单有不同的到达时间.对于前两种情况下的问题,提出了相应的伪多项式时间算法.对于最后一种情况下的问题给出了一个2-近似算法. 第3章研究了订单可拒绝的平行机批量排序问题.研究的排序目标是最小化接受订单的最大完工时间与拒绝订单的总拒绝费用之和.将两台平行机环境下提出的伪多项式时间算法推广到了 m台平行机的环境,并且在m台平行机环境下为该排序问题设计了一个3-近似算法. 第4章研究了双代理单机批量排序问题.考虑了竞争代理(Competing agents)排序模型,首先研究的排序目标为两个代理各自的最大成本函数,给出了一个多项式时间算法和一个最优且Pareto最优算法.其次当两个代理都以订单的总完工时间为目标函数时,提出了一个伪多项式时间算法.最后当订单允许被拒绝时,研究的两个代理的排序目标函数为最大完工时间与总完工时间,并提出了相应的伪多项式时间算法. 第5章简明地总结了本文的主要结果并提出了未来研究的潜在方向.