报告人：陈如冰 研究员 郑州大学

报告题目I：A note on the multi-agent competing scheduling on a single machine

报告时间：2026年7月1日 19:00-19:50

报告地点：性爱网站 301室

摘要： In this talk, we consider single-machine competing multi-agent scheduling problems  involving k agents. When k is arbitrary, the exact complexities of the single-machine feasibility problems with equal-length jobs were unaddressed in the literature, where each agent aims to minimize the total weighted completion time, the total tardiness, the total weighted number of tardy jobs or the total weighted late work. In addition, the exact complexities of the single-machine feasibility problems was posed an open problem in the literature, where the objective of each agent is to minimize the total number of tardy jobs. This motivates the current studies on competing multi-agent scheduling problems. For theses feasibility problems, we prove unary NP-completeness.

报告题目II：Bicriterion Pareto-scheduling of equal-length jobs on a single machine related to the total weighted late work

报告时间：2026年7月1日 20:00-20:50

报告地点：性爱网站 301室

摘要：In this talk, we study bicriterion Pareto-scheduling on a single machine of equal-length jobs, where one of the criteria is the total weighted late work. Motivated by two Pareto-scheduling open problems where one criterion is the total (weighted) late work and the other criterion is the weighted number of tardy jobs, we show that twelve constrained scheduling problems unaddressed in the literature are binary NP-hard, implying that the Pareto-scheduling versions of these problems are also binary NP-hard. Moreover, we introduce the concept of dummy due dates (DDD) for equal-length jobs to be scheduled in equal-length intervals. Intriguingly, we find that a DDD-based technique outperforms the existing solution methods and improves the known time complexities of the related problems. In addition, we extend our research to the two-agent scheduling model under the assumption of equal-length or partially equal-length jobs by including the total weighted late work as the criterion of one agent. For these problems, our results also improve the known time complexity results.

报告人简介：陈如冰，郑州大学数学与统计学院研究员。研究方向为排序问题的计算复杂性分析和算法设计。研究成果发表在《European Journal of Operational Research》、《Naval Research Logistics》、《Journal of Scheduling》、《International Journal of Production Research》、《Computers & Industrial Engineering》等期刊。现主持国家自然科学基金面上项目一项，主持完成国家自然科学基金青年项目一项和中国博士后面上项目一项。