×

zbMATH — the first resource for mathematics

Online over time processing of combinatorial problems. (English) Zbl 1402.90145
Summary: 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).
MSC:
90C27 Combinatorial optimization
90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anderson, EJ; Potts, CN, Online scheduling of a single machine to minimize total weighted completion time, Mathematics of Operations Research, 29, 686-697, (2004) · Zbl 1082.90033
[2] Arpaci-Dusseau, R.H., & Arpaci-Dusseau, A.C. (2014). Operating systems: three easy pieces, chap. Scheduling: Introduction. Arpaci-Dusseau Books. · Zbl 1024.68669
[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, Random forests, Machine Learning, 45, 5-32, (2001) · Zbl 1007.68152
[5] Chan, WT; Chin, FY; Ye, D; Zhang, G; Zhang, Y, On-line scheduling of parallel jobs on two machines, Journal of Discrete Algorithms, 6, 3-10, (2008) · Zbl 1279.90062
[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.
[10] Graham, RL; Lawler, EL; Lenstra, JK; Kan, AR, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[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. · Zbl 1403.68226
[12] Hurink, JL; Paulus, JJ, Online scheduling of parallel jobs on two machines is 2-competitive, Operations Research Letters, 36, 51-56, (2008) · Zbl 1138.90007
[13] Hutter, F; Xu, L; Hoos, HH; Leyton-Brown, K, Algorithm runtime prediction: methods & evaluation, Artificial Intelligence, 206, 79-111, (2014) · Zbl 1334.68185
[14] Järvisalo, M; Le Berre, D; Roussel, O; Simon, L, The international sat solver competitions, AI Magazine, 33, 89-92, (2012)
[15] Kautz, H.A. (2006). Deconstructing planning as satisfiability. In IAAI (pp. 1524-1526).
[16] Krueger, P; Lai, T; Dixit-Radiya, V, Job scheduling is more important than processor allocation for hypercube computers, IEEE Transactions on Parallel and Distributed Systems, 5, 488-497, (1994)
[17] Lawler, EL; Lenstra, JK; Kan, AHR; Shmoys, DB, Sequencing and scheduling: algorithms and complexity, Handbooks in Operations Research and Management Science, 4, 445-522, (1993)
[18] Leyton-Brown, K; Nudelman, E; Shoham, Y, Empirical hardness models: methodology and a case study on combinatorial auctions, Journal of the ACM (JACM), 56, 22, (2009) · Zbl 1325.68110
[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. · Zbl 1332.90002
[21] Prasad, MR; Biere, A; Gupta, A, A survey of recent advances in sat-based formal verification, STTT, 7, 156-173, (2005)
[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; Hemert, JI, Discovering the suitability of optimisation algorithms by learning from evolved instances, Annals of Mathematics and Artificial Intelligence, 61, 87, (2011) · Zbl 1236.49008
[24] Srinivasan, S., Kettimuthu, R., Subramani, V., Sadayappan, P. (2002). Characterization of backfilling strategies for parallel job scheduling. In ICPP workshops (pp. 514-522). · Zbl 1024.68858
[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, TT; Down, DG; Beck, JC, Integrating queueing theory and scheduling for dynamic scheduling problems, Journal of Artificial Intelligence Research, 50, 535-572, (2014) · Zbl 1364.90131
[27] Thain, D; Tannenbaum, T; Livny, M, Distributed computing in practice: the condor experience, Concurrency - Practice and Experience, 17, 323-356, (2005)
[28] Tian, J; Fu, R; Yuan, J, Online over time scheduling on parallel-batch machines: a survey, Journal of the Operations Research Society of China, 2, 445-454, (2014) · Zbl 1306.90060
[29] Vielma, J.P. (2015). Mixed integer linear programming formulation techniques. SIAM Review, 57(1), 3-57. · Zbl 1338.90277
[30] Witten, I.H., Frank, E., Hall, M.A. (2011). Data mining: practical machine learning tools and techniques, 3rd edn. San Mateo: Morgan Kaufmann.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.