【摘要】本文主要研究了两类加工时间依赖机器的两阶段车间作业排序问题,一类是加工时间依赖机器的两阶段流水作业排序间题,另一类是加工时间依赖机器的两阶段自由作业排序问题.本文分别设计了相应的近似算法,并证明了算法的最坏情况界.全文共分为四章,具体如下：第一章简要介绍与排序问题相关的一些概念及相应的理论基础知识.第二章研究一类源于计算机网络数据传输中的加工时间依赖机器的两阶段流水作业排序问题,用三参数表 […]

【摘要】本文主要研究了两类不可中断的平行机排序问题：一类是带服务等级约束的m台机在线排序问题，目标是极小化总完工时间；另一类是带单服务器装卸载的两台机排序问题。目标是极小化最大完工时间（makespan）。全文共四章。第一章简要介绍了排序的基本理论知识。第二章研究了带服务等级约束的m台机在线排序问题。本章主要考虑了单位工件情况下该问题的下界以及算法设计，其中要求等级较低的工件只能安排在第一台机器上 […]