Abstract
We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time before it can be processed. First we show that a natural adaptation of the seminal approximation algorithm for unrelated machine scheduling [11] yields a 3-approximation algorithm, equal to the integrality gap of the corresponding LP relaxation. Through a stronger LP relaxation, obtained by applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + φ, where φ ≈ 1.618 is the golden ratio. This ratio decreases to 2 in the restricted assignment setting, matching the result for the classic version. Interestingly, we show that our problem cannot be approximated within a factor better than \(\frac{e}{e-1}\approx 1.582\) (unless \(\mathcal{P}=\mathcal{NP}\)). This provides some evidence that it is harder than the classic version, which is only known to be inapproximable within a factor 1.5 − ε. Since our 1 + φ bound remains tight when considering the seemingly stronger machine configuration LP, we propose a new job based configuration LP that has an infinite number of variables, one for each possible way a job may be split and processed on the machines. Using convex duality we show that this infinite LP has a finite representation and can be solved in polynomial time to any accuracy, rendering it a promising relaxation for obtaining better algorithms.
This work was partially supported by Nucleo Milenio Información y Coordinación en Redes ICM/FIC P10-024F, by EU-IRSES grant EUSACOU, by the DFG Priority Programme ”Algorithm Engineering” (SPP 1307), by the Berlin Mathematical School, by ERC Starting Grant 335288-OptApprox, and by FONDECYT project 3130407.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Setup Time
- Golden Ratio
- Unrelated Parallel Machine
- Unrelated Machine
- Schedule Unrelated Parallel Machine
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allahverdi, A., Ng, C., Cheng, T., Kovalyov, M.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187, 985–1032 (2008)
Asadpour, A., Feige, U., Saberi, A.: Santa claus meets hypergraph matchings. ACM Trans. Algorithms 24, 24:1–24:9 (2012)
Bansal, N., Sviridenko, M.: The Santa Claus problem. In: STOC, pp. 31–40 (2006)
Chen, B., Ye, Y., Zhang, J.: Lot-sizing scheduling with batch setup times. J. Sched. 9, 299–310 (2006)
Correa, J.R., Verdugo, V., Verschae, J.: Approximation algorithms for scheduling splitting jobs with setup times. In: Talk in MAPSP (2013)
Ebenlendr, T., Krčál, M., Sgall, J.: Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica (2012), doi:10.1007/s00453-012-9668-9
Feige, U.: On allocations that maximize fairness. In: SODA, pp. 287–293 (2008)
Graham, R., Lawler, E., Lenstra, J., Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)
Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the Lovász Local Lemma. J. ACM 58, 28:1–28 (2011)
Kim, D.-W., Na, D.-G., Frank Chen, F.: Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. Robot. Com. -Int. Manuf. 19, 173–181 (2003)
Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259–271 (1990)
Liu, Z., Cheng, T.C.E.: Minimizing total completion time subject to job release dates and preemption penalties. J. Sched. 7, 313–327 (2004)
Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optimiz. 1, 166–190 (1991)
Polacek, L., Svensson, O.: Quasi-polynomial local search for restricted max-min fair allocation. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 726–737. Springer, Heidelberg (2012)
Potts, C.N., Wassenhove, L.N.V.: Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. J. Oper. Res. Soc. 43, 395–406 (1992)
Schalekamp, F., Sitters, R., van der Ster, S., Stougie, L., Verdugo, V., van Zuylen, A.: Split scheduling with uniform setup times. Arxiv (2012)
Schuurman, P., Woeginger, G.J.: Preemptive scheduling with job-dependent setup times. In: SODA, pp. 759–767 (1999)
Serafini, P.: Scheduling jobs on several machines with the job splitting property. Oper. Res. 44, 617–628 (1996)
Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput. 41, 1318–1341 (2012)
Sviridenko, M., Wiese, A.: Approximating the configuration-lp for minimizing weighted sum of completion times on unrelated machines. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 387–398. Springer, Heidelberg (2013)
van der Ster, S.: The allocation of scarce resources in disaster relief. MSc-Thesis in Operations Research at VU University Amsterdam (2010)
Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 530–542. Springer, Heidelberg (2011)
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press (2011)
Xing, W., Zhang, J.: Parallel machine scheduling with splitting jobs. Discrete Appl. Math. 103, 259–269 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Correa, J.R. et al. (2014). Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines. In: Lee, J., Vygen, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2014. Lecture Notes in Computer Science, vol 8494. Springer, Cham. https://doi.org/10.1007/978-3-319-07557-0_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-07557-0_21
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07556-3
Online ISBN: 978-3-319-07557-0
eBook Packages: Computer ScienceComputer Science (R0)