报告题目：自动仓储系统中的调度问题
报 告 人：许超
报告时间：2022年10月20日9:00-12:00
报告地点：9-412
报告摘要：在自动化仓储系统中，高效地完成存储和取出的操作有极大的意义。一个存储的操作是从任意一个入口拿到物品，放到对应的储存空间里一个特定的位置。一个取出的操作是从一个储存空间的特定的位置拿到物品，放到任意一个出口。将存储的操作和取出的操作对应起来，一次性完成，可以减少一些时间，而存储的顺序不同也可以改变耗时。如何在最短时间内完成所有的存储操作是一个重要的问题，这个问题等价于某一类型图上的高多重性非对称旅行商问题，而旅行商问题是经典的NP-hard的问题。然而，这类型图很特殊：存在一个常数大小的集合，使得任何长度为2的路径都包含这个顶点集中的一个顶点。报告将描述如何利用这些图的结构特性获得一个多项式时间算法。报告也会介绍一个只有存储但是机器可以同时拿起两个物体的版本，和探讨本方向的未解问题。
专家简介：许超本科就读于美国石溪大学，博士就读于美国UIUC大学，师从算法领域著名专家Chandra Chekuri教授和Karthekeyan Chandrasekaran教授。毕业后曾在Yahoo! Research等公司担任研发科学家，2021年底回国入职电子科技大学。许超主要从事的是组合优化和算法的基础研究，在SIAM Journal of Computing、Mathematical Programming、SODA等组合优化和算法的国际顶级期刊和会议上发表多篇有影响力的学术论文。
