报告题目：以总误工时间为主指标的主次指标排序问题
报 告 人：赵秋兰
报告时间：2025年9月20号10:00
报告地点： 莲花街校区惟德楼315会议室
报告人简介（附照片）：赵秋兰，现任南京大学数学学院副教授、硕士生导师，博士毕业于香港大学数学系。目前担任中国运筹学会图论组合分会理事，主持国家自然科学基金青年项目和面上项目，2019年入选江苏省“双创博士”，2024年获得江苏省运筹学会第一届青年科技奖。主要研究兴趣包括多面体组合、图论和排序论。目前在Mathematics of Operations Research, SIAM Journal on Optimization, Journal of Combinatorial Theory, Series B等期刊发表学术论文多篇。
报告内容简介：主次指标排序问题是排序论中的重要课题，其目标是寻找可行排序使得在主指标达到最优的情况下最小化次指标。Lee和Vairaktarakis在1993年给出了主次指标排序问题较为全面的综述。对于各种不同的主次指标，他们综述了相关的计算复杂性结果。特别地，当主指标是总误工时间，次指标是最大延误时间，总加权误工工件数或者总加权误工时间时，他们指出这三个问题虽然是NP-困难的，但它们的精确复杂性（拟多项式时间可解或者强NP-困难）仍然是未知的。我们证明了这三个问题都是拟多项式时间可解的。本报告介绍这三个问题的精确复杂性。
欢迎广大师生参加！
数学与统计学院
2025年9月15日
