Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On-line preemptive machine scheduling with \(\ell _p\) norm on two uniform machines

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

One of the basic and fundamental scheduling problems is to minimize the machine completion time vector in the \(\ell _p\) norm, a direct extension of the well-studied objective makespan (\(l_{\infty }\) norm), on parallel machines. We concentrate on the on-line and preemptive version of this problem where jobs arrive one by one over a list to be allocated to two uniform machines with job preemption permitted. We present a best possible deterministic on-line scheduling algorithm for this problem along with a matching lower bound, generalizing existing results for the identical machines scheduling problem in the literature. One notable feature of this work is the highly involved technicality compared to similar analysis in the existing literature, mainly due to the intrinsic unavailability of a closed-form formula for the competitive ratio.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Alon, N., Azar, Y., Woeginger, G. J., & Yadid, T. (1997). Approximation schemes for scheduling. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 493–500). ACM/SIAM.

  • Avidor, A., Azar, Y., & Sgall, J. (2001). Ancient and new algorithms for load balancing in the \(\ell _p\) norm. Algorithmica, 29, 422–441.

    Article  Google Scholar 

  • Azar, Y., & Epstein, A. (2005). Convex programming for scheduling unrelated parallel machines. In H. N. Gabow, & R. Fagin (Eds.), Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC) (pp. 331–337).

  • Azar, Y., & Taub, S. (2004). All-norm approximation for scheduling on identical machines. In T. Hagerup, & J. Katajainen (Eds.), Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science (Vol. 3111, pp. 298–310). Berlin: Springer.

  • Azar, Y., Epstein, A., & Epstein, L. (2006). Load balancing of temporary tasks in the \(\ell _p\) norm. Theoretical Computer Science, 361(2–3), 314–328.

    Article  Google Scholar 

  • Azar, Y., Epstein, L., Richter, Y., & Woeginger, G.J. (2002). All-norm approximation algorithms. In M. Penttonen, & M. E. Schmidt (Eds.), Scandinavian Workshop on Algorithm Theory(SWAT). Lecture Notes in Computer Science (Vol. 2368, pp. 288–297). Berlin: Springer.

  • Bannister, J. A., & Trivedi, K. S. (1983). Task allocation in fault-tolerant distributed systems. Acta Informatica, 20(3), 261–281.

    Article  Google Scholar 

  • Bansal, N., & Pruhs, K. R. (2010). Server scheduling to balance priorities, fairness and average quality of service. SIAM Journal of Computing, 39(7), 3311–3335.

    Article  Google Scholar 

  • Caragiannis, I. (2008). Better bounds for online load balancing on unrelated machines. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 08) (pp. 972–981).

  • Chandra, A. K., & Wong, C. K. (1975). Worst-case analysis of a placement algorithm related to storage allocation. SIAM Journal on Computing, 1, 249–263.

    Article  Google Scholar 

  • Chen, B., Du, D., Han, J., & Wen, J. (2001). On-line scheduling of small open shops. Discrete Applied Mathematics, 110, 133–150.

    Article  Google Scholar 

  • Cody, R. A., & Coffman, E. G. (1976). Record allocation for minimizing expected retrieval costs on drum-like storage devices. Journal of the ACM, 23(1), 103–115.

    Article  Google Scholar 

  • Du, D. (2004). Optimal preemptive semi-online scheduling on two uniform processors. Information Processing Letters, 92, 219–223.

    Article  Google Scholar 

  • Du, D., Jiang, X., & Zhang, G. (2005). Optimal preemptive online scheduling to minimize \(l_p\) norm on two processors. Journal of Manufacturing and Management Optimization, 1(3), 345–351.

    Google Scholar 

  • Epstein, L., & Tassa, T. (2006). Optimal Preemptive Scheduling for General Target Functions. Journal of Computer and System Sciences, 72(1), 132–162.

    Article  Google Scholar 

  • Epstein, L., Noga, J., Seiden, S., Sgall, J., & Woeginger, G. J. (2001). Randomized online scheduling on two uniform machines. Journal of Scheduling, 4(2), 71–92.

    Article  Google Scholar 

  • Feigenbaum, I., & Sethuraman, J., Ye, C. (2013). Approximately optimal nechanisms for strategyproof facility location: Minimizing \(L_p\) norm of costs. arXiv:1305.2446 [cs.GT].

  • Feldman, M., & Wilf, Y. (2011). Randomized strategyproof mechanisms for facility location and the mini-sum-of-squares objective. CoRR, abs/1108.1762, 2011.

  • Golovin, D., Gupta, A., Kumar, A., Tangwongsan, K., (2007) All-norms and all-Lp-norms approximation algorithms. Computer Science Department, Carnegie Mellon University. Paper 828. http://repository.cmu.edu/compsci/828.

  • Kleinberg, J., Rabani, Y., & Tardos, E. (2001). Fairness in routing and load balancing. Journal of Computer and System Sciences, 63(1), 2–20.

    Article  Google Scholar 

  • Kumar, V. S. A., Marathe, M. V., Parthasarathy, S., & Srinivasan, A. (2005). Approximation algorithms for scheduling on multiple machines. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (pp. 254–263).

  • Lin, L. (2007). Semi-online scheduling algorithm under the \(\ell _p\) norm on two identical machines. Journal of Zhejiang University (Science Edition), 34(2), 148–151. (In Chinese).

    Google Scholar 

  • Lin, L., Tan, Z. Y., & He, Y. (2005). Deterministic and randomized scheduling problems under the \(\ell _p\) norm on two identical machines. Journal of Zhejiang University Science, 6(1), 20–26.

    Article  Google Scholar 

  • Munagala, K., Babu, S., Motwani, R., Widom, J. (2005). The pipelined set cover problem. Database Theory—ICDT 2005, 10th International Conference (pp. 83–98).

  • Tan, Z., He, Y., & Epstein, L. (2005). Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data. Information and Computation, 196(1), 57–70.

  • Wen, J., & Du, D. (1998). Preemptive on-line scheduling for two uniform processors. Operations Research Letters, 23, 113–116.

    Article  Google Scholar 

Download references

Acknowledgments

Research of the first author is supported in part by the National Natural Science Foundation of China (NSFC) Grant 11001030; the Fundamental Research Funds for the Central Universities (BUPT2012RC0709). This work was done while the first author visits Faculty of Business Administration, University of New Brunswick. Research of the second author is supported by the National Science and Engineering Council of Canada (NSERC) Grant 283106.

Author information

Authors and Affiliations

  1. School of Sciences, Beijing University of Posts and Telecommunications, Beijing, 100876, China

    Tianping Shuai

  2. Faculty of Business Administration, University of New Brunswick, 7 Macaulay Lane, Fredericton, NB, E3B 5A3, Canada

    Donglei Du

  3. College of Engineering, Louisiana State University, Baton Rouge, LA, USA

    Xiaoyue Jiang

Authors
  1. Tianping Shuai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Donglei Du
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaoyue Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Donglei Du.

Appendices

Appendix 1: A proof of the lower on the optimal objective value (3)

We prove a stronger result that the equality holds in (3).

Consider the optimal (off-line) schedule opt before \(x\). Let \(L\) be the total process time before \(x\) and \(z\) be any job before \(x\) in opt. Denote \(C_{\textsc {opt}}\) to be the optimal off-line objective prior to \(x\). Note that \(\frac{z}{s}\ge \hat{s}\hat{t}L\) if and only if \(L-z\le \hat{t}L\) due to (1)–(2). Therefore, the RHS of (3)

$$\begin{aligned} \text {RHS:}&= \root p \of {\left( \max \left\{ \frac{z}{s}, \hat{s}\hat{t}L \right\} \right) ^p + \left( \min \left\{ L-z,\hat{t}L\right\} \right) ^p}\\&= \left\{ \begin{array}{ll} \root p \of {(L-z)^p+\left( \frac{z}{s}\right) ^p},&{}\text { if } \frac{z}{s}\ge \hat{s}\hat{t}L;\\ \root p \of {\left( \hat{s}\hat{t}L\right) ^p+\left( \hat{t}L\right) ^p},&{}\text { otherwise.} \end{array}\right. \end{aligned}$$

Now we show the desired result in two cases.

  1. Case 1.

    \(\frac{z}{s}\ge \hat{s}\hat{t}L\), which is equivalent to \(L-z\le \hat{t}L\). From the case conditions and \(\hat{s}\ge 1\), we have that \(\frac{z}{s}\ge \hat{s}\hat{t}L\ge \hat{t}L\ge L-z\). Under these conditions, the optimal schedule is to put \(z\) entirely on machine 2 and the rest on machine 1, leading to the desired optimal value:

    $$\begin{aligned}&\quad C_{\textsc {opt}}=\root p \of {(L-z)^p+\left( \frac{z}{s}\right) ^p}. \end{aligned}$$
  2. Case 2.

    \(\frac{z}{s}< \hat{s}\hat{t}L\), which is equivalent to \(L-z>\hat{t}L\). In this case, let \(y\) be the load assigned to machine 1 in opt. Then the objective value is \(c(y)=\root p \of {y^p+(\frac{L-y}{s})^p}\). By taking derivative, we have the stationary point \(y^*=\frac{L}{1+\hat{s}^p}=\hat{t}L\). Checking the second derivative convinces us that \(c(y)\) achieves its minimum value at \(y^*\), which, due to (1)–(2), equals to

    $$\begin{aligned}&\quad \root p \of {\left( \hat{t}L\right) ^p+\left( \frac{L-\hat{t}L}{s}\right) ^p}=\root p \of {\left( \hat{s}\hat{t}L\right) ^p+\left( \hat{t}L\right) ^p}. \end{aligned}$$
    (13)

    Note that the case condition \(L-z>\hat{t}L\) implies that we can indeed assign (by preemption) the load \(y^*=\hat{t}L\) on machine 1 and the rest on machine 2 to achieve the bound in (13), implying that

    $$\begin{aligned}&\quad C_{\textsc {opt}}=\root p \of {\left( \hat{s}\hat{t}L\right) ^p+\left( \hat{t}L\right) ^p}. \end{aligned}$$

Appendix 2: Competitive ratios for selected \(p\) and \(s\)

See Table 1.

Table 1 Competitive ratios for selected \(s\) and \(p\)
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shuai, T., Du, D. & Jiang, X. On-line preemptive machine scheduling with \(\ell _p\) norm on two uniform machines. J Sched 18, 185–194 (2015). https://doi.org/10.1007/s10951-014-0387-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-014-0387-8

Keywords

Search

Navigation