Similar articles

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.

[1] Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O., 1997. On-line load balancing with applications to machine scheduling and virtual circuit routing. Journal of the ACM, 44(3):486-504.

[2] Berman, P., Charikar, M., Karpinski, M., 1997. On-line Load Balancing for Related Machines. Proceedings of the 5th Workshop on Algorithms and Data Structures. Springer-Verlag, Berlin, 1272:116-125.

[3] Cao, D., Chen, M., Wan, G., 2005. Parallel machine selection and job scheduling to minimize machine cost and job tardiness. Computer & Operations Research, 32(8):1995-2012.

[4] Cho, Y., Sahni, S., 1980. Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9(1):91-103.

[5] Dessouky, M.M., Dessouky, M.I., Verma, S., 1998. Flowshop scheduling with identical jobs and uniform parallel machines. European Journal of Operational Research, 109(3):620-631.

[6] Dósa, G., He, Y., 2004. Better online algorithms for scheduling with machine cost. SIAM Journal on Computing, 33(5):1035-1051.

[7] Epstein, L., Noga, J., Seiden, S., Sgall, J., Woeginger, G.J., 2001. Randomized on-line scheduling on two uniform machines. Journal of Scheduling, 4(2):71-92.

[8] Epstein, L., Sgall, J., 2000. A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters, 26(1):17-22.

[9] He, Y., Han, S.G., Jiang, Y.W., 2006. Online algorithms for scheduling with machine activation cost. Asia-Pacific Journal of Operations research, in press.

[10] Imreh, C., Noga, J., 1999. Scheduling with Machine Cost. Proc. RANDOM APPROX’99. Lecture Notes in Computer Science, 1671:168-176.

[11] Jiang, Y.W., He, Y., 2005. Preemptive online algorithms for scheduling with machine cost. Acta Informatica, 41(6):315-340.

[12] Jiang, Y.W., He, Y., 2006. Semi-online algorithms for scheduling with machine cost. Journal of Computer Science & Technology, 21(6):984-988.

[13] Noga, J., Seiden, S.S., 2001. An optimal online algorithm for scheduling two machines with release times. Theoretical Computer Science, 268(1):133-143.

[14] Panwalkar, S., Liman, S.D., 2002. Single operation earliness-tardiness scheduling with machine activation cost. IIE Transactions, 34(5):509-513.

[15] Sgall, J., 1998. On-line Scheduling. In: Fiat, A., Woeginger, G.J. (Eds.), Online Algorithms: The State of the Art. Springer-Verlag, Berlin, 1442:196-231.

[16] Tan, Z., He, Y., 2002. Optimal online algorithm for scheduling on two identical machines with machine availability constraints. Information Processing Letters, 83(6):323-329.