報告題目：以總誤工時間為主指標的主次指標排序問題

報 告 人：趙秋蘭

報告時間：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日