Abstract: In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to 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 the machine activation cost. We design optimal online algorithms with competitive ratio of (2s+1)/(s+1) for every s≥1.

Key words: Online algorithm, Competitive analysis, Uniform machine scheduling, Machine activation cost

Please provide your name, email address and a comment

Your Name: Affili: E-Mail Address:

Comment (Please comment in English):


Verification Code(click to change a pic):