Topic: Approximate Algorithms for Parallel Machine Scheduling in Green Manufacturing

Speaker: Yiwei Jiang

Location: Room 211, Glorious Sun Building, Yan'an Road Campus 

Time: 2020-12-11 16:00:00 

Brief introduction of the speaker: Yiwei Jiang is a Distinguished Professor of “West Lake Scholar”, Zhejiang Gongshang University, a visiting scholar in the Department of Computer Science at the University of Texas at Dallas (UTD), the Department of Computer Science at the University of Hong Kong, and the Department of Logistics and Shipping at the Hong Kong Polytechnic University, a special commentator of Mathematical Reviews, USA and the director of the Professional Committee of Scheduling of the Operations Research Society of China. He has been selected as a member of the “151” Talent Project of Zhejiang Province and Outstanding Young Teachers Funding Program for Universities in Zhejiang Province. His main research areas are: scheduling theory, logistics and supply chain management, discrete optimization, algorithm design and analysis, etc. He has hosted two projects of the National Natural Science Foundation of China and two projects of the Natural Science Foundation of Zhejiang Province. He was awarded one second prize of scientific research achievements of universities in Zhejiang Province  (ranked first). He has published more than 60 academic papers in the fields of operations research, management, theoretical computer science and so on in domestic and international mainstream journals such as EJOR, FGCS, INS, JORS, CAIE, TCS, JOCO, etc.

Report Overview: This talk mainly considers parallel machine scheduling in green manufacturing. We are given a set of machines where each machine has associated with a fixed cost and a processing cost per unit time. Our goal is to schedule a set of jobs onto some machines such that the makespan is minimized, subject to the constraint that the total cost is not more than a given threshold value. We provide an FPTAS for the preemptive variant and an approximation algorithm with a worst-case ratio of 2 for the non-preemptive variant. For a special case where the fixed cost is zero, we provide an improved non-preemptive algorithm with a worst-case ratio of 1.686.