题目：有优先约束的单位工件的自由作业与流水作业

　　时间：5月18日（周二）10：00-12：00

　　地点：（线上）腾讯会议（会议号：645 876 523）

　　主办单位：上海第二工业大学文理学部

　　主讲人：张安，男，博士（后），现任中国运筹学会排序分会理事、数学规划分会青年理事。主要研究兴趣为图与网络、排序及相关组合优化问题的数学建模与近似算法。研究成果曾获浙江省高校优秀科研成果二等奖。长期为EJOR、JOS、IJPE、JORS、JOCO、TCS等运筹学主流刊物的评审专家，并参与组合优化丛书《Handbook of Combinatorial Optimization》（2Eds,Springer）的编写工作。近年来发表SCI期刊论文近30篇，主持国家自然科学基金2项，浙江省自然科学基金1项，参与多项省部级以上科研项目。先后访问香港科技大学、东京电机大学、加拿大阿尔伯塔大学等，与国内外学者广泛合作。

　　讲座简介：研究具有优先约束的单位工件的自由作业和流水作业的排序问题，其中如果一个工件在另一个工件之前完成，那么它必须在另一个工件开始加工之前完成，目标是最小化完工时间。对于三台机器的情形，提出了一个简单的5/3近似算法，该近似算法基于使用优先图的自然分层表示将作业集划分为合适的层。然后，对于自由作业的排序问题，提出了一个近似比为4/3的贪婪算法来减少单作业层的数量，从而得到一个改进的划分。对于流水作业的排序问题，还提出了一种改进的性能比为3/2的算法。所有的近似算法也适用于m台机器的情形。