Skip to main content
SpringerLink
Log in

Online over time processing of combinatorial problems

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

In an online environment, jobs arrive over time and there is no information in advance about how many jobs are going to be processed and what their processing times are going to be. In this paper, we study the online scheduling of Boolean Satisfiability (SAT) and Mixed Integer Programming (MIP) instances that are well-known NP-complete problems. Typical online machine scheduling approaches assume that jobs are completed at some point in order to minimize functions related to completion time (e.g., makespan, minimum lateness, total weighted tardiness, etc). In this work, we formalize and present an online over time problem where arriving instances are subject to waiting time constraints. We propose computational approaches that combine the use of machine learning, MIP, and instance interruption heuristics. Unlike other approaches, we attempt to maximize the number of solved instances using single and multiple machine configurations. Our empirical evaluation with well-known SAT and MIP instances, suggest that our interruption heuristics can improve generic ordering policies to solve up to 21.6x and 12.2x more SAT and MIP instances. Additionally, our hybrid approach observed up to 90% of solved instances with respect to a semi clairvoyant policy (SCP).

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Anderson, E.J., & Potts, C.N. (2004). Online scheduling of a single machine to minimize total weighted completion time. Mathematics of Operations Research, 29(3), 686–697.

    Article  MathSciNet  MATH  Google Scholar 

  2. Arpaci-Dusseau, R.H., & Arpaci-Dusseau, A.C. (2014). Operating systems: three easy pieces, chap. Scheduling: Introduction. Arpaci-Dusseau Books.

  3. Bartz-Beielstein, T., & Markon, S. (2004). Tuning search algorithms for real-world applications: a regression tree based approach. In Congress on evolutionary computation, 2004. CEC2004, (Vol. 1 pp. 1111–1118). IEEE.

  4. Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32.

    Article  MATH  Google Scholar 

  5. Chan, W.T., Chin, F.Y., Ye, D., Zhang, G., Zhang, Y. (2008). On-line scheduling of parallel jobs on two machines. Journal of Discrete Algorithms, 6(1), 3–10.

    Article  MathSciNet  MATH  Google Scholar 

  6. Deng, K., Song, J., Ren, K., Iosup, A. (2013). Exploring portfolio scheduling for long-term execution of scientific workloads in iaas clouds. In Proceedings of the international conference on high performance computing, networking, storage and analysis (p. 55). ACM.

  7. Deng, K., Song, J., Ren, K., Iosup, A. (2013). Exploring portfolio scheduling for long-term execution of scientific workloads in iaas clouds. In SC.

  8. Deng, K., Verboon, R., Ren, K., Iosup, A. (2013). A periodic portfolio scheduler for scientific computing in the data center. In Workshop on job scheduling strategies for parallel processing (pp. 156–176). Springer.

  9. Duque, R., Arbelaez, A., Díaz, J.F. (2017). Off-line and on-line scheduling of SAT instances with time processing constraints, (pp. 524–539). Cham: Springer International Publishing.

    Google Scholar 

  10. Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326.

    Article  MathSciNet  MATH  Google Scholar 

  11. Heule, M.J.H., Kullmann, O., Marek, V.W. (2016). Solving and verifying the boolean pythagorean triples problem via cube-and-conquer. In SAT.

  12. Hurink, J.L., & Paulus, J.J. (2008). Online scheduling of parallel jobs on two machines is 2-competitive. Operations Research Letters, 36(1), 51–56.

    Article  MathSciNet  MATH  Google Scholar 

  13. Hutter, F., Xu, L., Hoos, H.H., Leyton-Brown, K. (2014). Algorithm runtime prediction: methods & evaluation. Artificial Intelligence, 206, 79–111.

    Article  MathSciNet  MATH  Google Scholar 

  14. Järvisalo, M., Le Berre, D., Roussel, O., Simon, L. (2012). The international sat solver competitions. AI Magazine, 33(1), 89–92.

    Article  Google Scholar 

  15. Kautz, H.A. (2006). Deconstructing planning as satisfiability. In IAAI (pp. 1524–1526).

  16. Krueger, P., Lai, T., Dixit-Radiya, V. (1994). Job scheduling is more important than processor allocation for hypercube computers. IEEE Transactions on Parallel and Distributed Systems, 5(5), 488–497.

    Article  Google Scholar 

  17. Lawler, E.L., Lenstra, J.K., Kan, A.H.R., Shmoys, D.B. (1993). Sequencing and scheduling: algorithms and complexity. Handbooks in Operations Research and Management Science, 4, 445–522.

    Article  Google Scholar 

  18. Leyton-Brown, K., Nudelman, E., Shoham, Y. (2009). Empirical hardness models: methodology and a case study on combinatorial auctions. Journal of the ACM (JACM), 56(4), 22.

    Article  MathSciNet  MATH  Google Scholar 

  19. Lynce, I., & Marques-Silva, J. (2006). SAT in bioinformatics: making the case with haplotype inference. In SAT.

  20. Pinedo, M.L. (2016). Scheduling: theory, algorithms, and systems, 5th edn. Cham: Springer International Publishing.

    Book  MATH  Google Scholar 

  21. Prasad, M.R., Biere, A., Gupta, A. (2005). A survey of recent advances in sat-based formal verification. STTT, 7(2), 156–173.

    Article  Google Scholar 

  22. Shen, S., Deng, K., Iosup, A., Epema, D. (2013). Scheduling jobs in the cloud using on-demand and reserved instances. In European conference on parallel processing (pp. 242–254). Springer.

  23. Smith-Miles, K., & van Hemert, J.I. (2011). Discovering the suitability of optimisation algorithms by learning from evolved instances. Annals of Mathematics and Artificial Intelligence, 61(2), 87.

    Article  MathSciNet  MATH  Google Scholar 

  24. Srinivasan, S., Kettimuthu, R., Subramani, V., Sadayappan, P. (2002). Characterization of backfilling strategies for parallel job scheduling. In ICPP workshops (pp. 514–522).

  25. Sukhija, N., Malone, B., Srivastava, S., Banicescu, I., Ciorba, F.M. (2014). Portfolio-based selection of robust dynamic loop scheduling algorithms using machine learning. In IPDPS workshops.

  26. Terekhov, D., Tran, T.T., Down, D.G., Beck, J.C. (2014). Integrating queueing theory and scheduling for dynamic scheduling problems. Journal of Artificial Intelligence Research, 50, 535–572.

    MathSciNet  MATH  Google Scholar 

  27. Thain, D., Tannenbaum, T., Livny, M. (2005). Distributed computing in practice: the condor experience. Concurrency - Practice and Experience, 17(2-4), 323–356.

    Article  Google Scholar 

  28. Tian, J., Fu, R., Yuan, J. (2014). Online over time scheduling on parallel-batch machines: a survey. Journal of the Operations Research Society of China, 2(4), 445–454.

    Article  MathSciNet  MATH  Google Scholar 

  29. Vielma, J.P. (2015). Mixed integer linear programming formulation techniques. SIAM Review, 57(1), 3–57.

  30. Witten, I.H., Frank, E., Hall, M.A. (2011). Data mining: practical machine learning tools and techniques, 3rd edn. San Mateo: Morgan Kaufmann.

    Google Scholar 

Download references

Acknowledgments

The authors would like to thank the anonymous reviewers for their comments and suggestions which helped to improve the paper. Robinson Duque is supported by the Universidad del Valle and also by Colciencias, the Colombian Administrative Department of Science, Technology and Innovation under the PhD scholarship program.

Author information

Authors and Affiliations

  1. Universidad del Valle, Cali, Colombia

    Robinson Duque & Juan F. Díaz

  2. Cork Institute of Technology, Cork, Ireland

    Alejandro Arbelaez

Authors
  1. Robinson Duque
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alejandro Arbelaez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Juan F. Díaz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Robinson Duque.

Additional information

This article belongs to the Topical Collection: Topical Collection on Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Guest Editor: Willem-Jan van Hoeve

Appendix A: Experiment results across all datasets

Appendix A: Experiment results across all datasets

In this appendix we present further results of our online scheduling approach tested with SAT and MIP instances with waiting time constraints. The results of our approach include six different datasets and we managed to extend some of our experiments using 40–60% and 50–50% partitions:

Table 5 Experiments reporting the average number of solved instances per dataset, machine, and policy combinations using the H2 interruption heuristic
Full size table
Table 6 Experiments comparing the average number of solved instances of policies that use regression and classification models (RC) trained with Trivial and Cheap features
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Duque, R., Arbelaez, A. & Díaz, J.F. Online over time processing of combinatorial problems. Constraints 23, 310–334 (2018). https://doi.org/10.1007/s10601-018-9287-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10601-018-9287-4

Keywords

Search

Navigation