Speaker：Yiwei Jiang (Zhejiang Gongshang University)

Time：2023-7-7, 9:00

Location：Conference Room 686 at the 6th floor of Shuli Building at Haiyun Campus

Abstract:

We consider non-preemptive online parallel-machine scheduling with a common due date to maximize the total early work of all the jobs, i.e., the total processing time of the jobs (or parts) completed before the common due date. For the general case of m machines, we provide a lower bound on m, which is the positive real root of an m-degree equation. For the online algorithm, we first show that the tight competitive ratio of the classical list scheduling (LS) algorithm is 4/3. We then re-prove that the competitive ratio of the previous algorithm EFFm is at most 1.2956 and present a formula to compute the competitive ratio of the algorithm for any given m. For the case of three machines, we improve the lower bound to 1.1878 and propose an improved online algorithm with a competitive ratio of 1.2483.