報(bào)告題目：以總誤工時(shí)間為主指標(biāo)的主次指標(biāo)排序問(wèn)題

報(bào) 告 人：趙秋蘭

報(bào)告時(shí)間：2025年9月20號(hào)10:00

報(bào)告地點(diǎn)： 蓮花街校區(qū)惟德樓315會(huì)議室

報(bào)告人簡(jiǎn)介（附照片）：趙秋蘭，現(xiàn)任南京大學(xué)數(shù)學(xué)學(xué)院副教授、碩士生導(dǎo)師，博士畢業(yè)于香港大學(xué)數(shù)學(xué)系。目前擔(dān)任中國(guó)運(yùn)籌學(xué)會(huì)圖論組合分會(huì)理事，主持國(guó)家自然科學(xué)基金青年項(xiàng)目和面上項(xiàng)目，2019年入選江蘇省“雙創(chuàng)博士”，2024年獲得江蘇省運(yùn)籌學(xué)會(huì)第一屆青年科技獎(jiǎng)。主要研究興趣包括多面體組合、圖論和排序論。目前在Mathematics of Operations Research, SIAM Journal on Optimization, Journal of Combinatorial Theory, Series B等期刊發(fā)表學(xué)術(shù)論文多篇。

報(bào)告內(nèi)容簡(jiǎn)介：主次指標(biāo)排序問(wèn)題是排序論中的重要課題，其目標(biāo)是尋找可行排序使得在主指標(biāo)達(dá)到最優(yōu)的情況下最小化次指標(biāo)。Lee和Vairaktarakis在1993年給出了主次指標(biāo)排序問(wèn)題較為全面的綜述。對(duì)于各種不同的主次指標(biāo)，他們綜述了相關(guān)的計(jì)算復(fù)雜性結(jié)果。特別地，當(dāng)主指標(biāo)是總誤工時(shí)間，次指標(biāo)是最大延誤時(shí)間，總加權(quán)誤工工件數(shù)或者總加權(quán)誤工時(shí)間時(shí)，他們指出這三個(gè)問(wèn)題雖然是NP-困難的，但它們的精確復(fù)雜性（擬多項(xiàng)式時(shí)間可解或者強(qiáng)NP-困難）仍然是未知的。我們證明了這三個(gè)問(wèn)題都是擬多項(xiàng)式時(shí)間可解的。本報(bào)告介紹這三個(gè)問(wèn)題的精確復(fù)雜性。

歡迎廣大師生參加！

數(shù)學(xué)與統(tǒng)計(jì)學(xué)院
2025年9月15日