亚游登录,亚游集团官网

Two-machine Openshop scheduling with Two Agents

报告题目:Two-machine Openshop scheduling with Two Agents


邀请人:顾满占


报告人:刘培海 副教授 华东理工大学

时间:2019年12月28(周六)  13:30-14:15

地点:红瓦楼726

摘要: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.
XML 地图 | Sitemap 地图