Speaker：Yiwei Jiang (Zhejiang Gongshang University)

Time：2020-11-25, 15:00

Location：Conference Room 105 at Experiment Building at Haiyun Campus

Abstract:

本报告主要介绍绿色制造背景下的一个双目标平行机调度问题。不同的机器具有不同的单位加工费用，在给定总预算费用的情况下，如何组织生产使得完工时间最少。对于工件不允许中断的情形，我们给出了一个1.686的近似算法，改进了已有的2近似算法；对于给问题的对偶问题，即给定交货期情形下极小化总加工费用的调度问题，我们给出了一个(2+r)/3的近似算法，这里r表示最大单位加工费用和最小单位加工费用之比；对于机器带有固定费用和单位费用问题，以极小化makespan为目标，分别给出了可中断情形下的一个FPTAS和不可中断情形下的2近似算法。