分批排序问题的在线算法研究

分批排序问题是经典排序的自然推广，主要研究批量生产中作业调度问题。张玉忠同志已结题的国家自然科学基金项目研究了工件离线的问题，得到了若干重要结果。本项目深入研究更加实际的在线分批排序问题，即，诸多信息都不预先知道或者不全知道，它有重要的理论意义和广泛的应用前景。主要对以下几个重要在线分批问题进行深入研究，侧重于设计出相应的实用算法：1、最大完工时间的极小化问题。先从单机的情况入手，再推广到多机情形。2、极小化工件的平均完工时间问题。对于一台机器的情形，我们曾对批容量充分大的情况给出了竞争比为1.618近似算法，我们猜想对于一般的情况竞争比也是1.618。有些人试图证明此猜想但没有成功，本项目力争较彻底地解决此问题。3、其它重要的分批排序问题。如有交货期的，极小化延误和延误个数等问题进行深入研究。问题的特色是在线和分批，使用连续与离散优化技术相结合的方法。此项目将促进排序研究的深入发展。