报告题目：Two-machine Openshop scheduling with Two Agents
摘要：In this paper we consider a two-machine openshop scheduling problem with two agents. There are two agents A and B, each of which has a fixed set of nonpreemptive jobs to be processed on the same two-machine open shop system. The goal is to find a schedule minimizing the makespan of agent A such that the makespan of agent B does not exceed a given number Q. We first show that there is not a polynomial time approximation algorithm with a constant worst-case ratio for the problem. Then we present a pseudo-polynomial-time algorithm to solve it. With violating the constraint a factor ofε, we provide a fully polynomial time approximation scheme.
邀请人：顾满占
报告人：刘培海 副教授 华东理工大学
时间：2019年12月28日（周六） 13:30-14:15
地点：红瓦楼726