Optimal Semi-online Algorithms for Scheduling with Machine Activation Cost

摘要

We investigate the following two semi-on-line scheduling problems with machine activation cost. We are given two potential identical machines to non-preemptively process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and activation cost of machines. For the first semi-on-line problem with known the sum size of all jobs P in advance , we present an semi-on-line algorithm which is optimal for every P ＞ 0. For the second problem with known the largest size of all jobs L in advance, we present an optimal semi-on-line algorithm for every L ＞ 0.