排序是运筹学组合优化研究领域中最活跃的分支之一。 本项目将深入研究从实际应用背景驱动的两类排序新模型：无线传感器数据采集网络驱动的数据可压缩通讯排序问题和现代制造及医疗服务业驱动的工件加工可拒绝的重新排序问题，核心内容是设计多项式时间近似或启发式求解算法并用理论分析或数值实验来评价算法的性能。对第一类问题，根据传感器具体型号参数及其与基站间的传输距离，确定需要压缩哪些传感器采集的数据及其与基站间的通讯传输次序，使得一个或多个目标函数达到最优；对第二类问题，主要考虑三种不同情形干扰下 (新工件集到达，部分工件到达时间改变和可用于加工的机器数目减少) 所产生的工件加工可拒绝的重新排序模型，研究如何选择哪些工件拒绝，并确定被接受工件的加工次序，使得给定的排序目标函数及拒绝惩罚总费用之和最小。对以上问题进行研究，本项目将获得理论和实际应用的双重创新性成果，并且推动算法设计与分析思想和技巧的新发展。

Scheduling plays an important role in the operations research, particularly in combinatorial optimization. This proposed project will investigate two types of novel scheduling models of significant practical potential. One is the communication scheduling problem with data compressing, which is motivated by the wireless sensor data gathering network; and the other is rescheduling problem with job rejection, which is motivated by the modern production and medical service industries. Our goal is to design practical approximation algorithms or heuristic algorithms running in polynomial time and evaluate their performances by rigid theoretical analyses and/or extensive numerical experiments. For the first problem, based on the parameters from the heterogeneous sensors and the transmission distances between sensors and base stations, the target is to determine 1) from which sensors the collected data needs to be compressed and 2) the communication sequences between sensors and base stations, such that the given objective function(s) achieve(s) optimum. For the second problem, three types of disruptions situations of immense practical interest (i.e. the arrival of new jobs, changes in release dates for some jobs and reducing in the number of machines for processing) will be investigated for the rescheduling models with job rejection. The target is to reject or accept some jobs and determine the processing order of the accepted jobs on the corresponding machines so that the sum of the given objective function and the total rejection penalty is minimum. By conducting a systematic research on the above problems, several novel results of both significant theoretical and practical importance can be expected, and more importantly, multiple pioneering ideas and techniques for algorithm design and analysis can be inspired. All these outputs will lead to various meaningful real-life applications.