12月10日 张国川教授学术报告

报告人：张国川 教授 浙江大学

报告题目I：Revisiting Knapsack Problems

报告时间：2025年12月10日 19:00-19:50

报告地点：5278论坛 301室

摘要：Knapsack is one of the fundamental problems in combinatorial optimization. It aims to select a subset of items, each of which is associated with a weight and a size, such that the total size of the items is upper bounded by a budget, and the total weight is maximized. Knapsack as well as its variants has been extensively studied for decades. There are still quite a few algorithmic issues to be settled for the classical model, while more and more challenging Knapsack-like problems are coming. In this talk, we will briefly introduce our recent work on the old and new Knapsack problems.

报告题目II：Online algorithms for scheduling on parallel batch processing machines

报告时间：2025年12月10日 20:00-20:50

报告地点：5278论坛 301室

摘要：In this talk, we consider the problem of scheduling jobs on-line on parallel batch processing machines with dynamic job arrivals to minimize makespan. We are given m identical batch processing machines, each of which can handle up to B (the capacity of a machine) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is a constant, which is independent of the number and identity of the jobs. Each job becomes available at its arrival time, which is unknown in advance. We deal with the unbounded case where the capacity of the batch processing machines is infinite, and derive an optimal on-line algorithm with competitive ratio, prove that the result is the best possible for all m.

张国川教授：浙江大学教授，中国运筹学会副理事长。1995年毕业于中科院应用数学所，获得运筹学博士学位。曾获德国洪堡基金，在基尔大学和弗莱堡大学合作研究。法国INPG、日本京都大学和加拿大西蒙弗雷泽大学访问教授。研究兴趣包括组合优化近似算法、在线算法和算法机制设计。目前担任Annals of Operations Research, International Journal of Foundations of Computer Science, Journal of Scheduling, Journal of Operations Research Society of China等刊物编委，国际会议New Challenges in Scheduling Theory 组织者之一，ISAAC顾问委员会委员和COCOON指导委员会委员。