{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T10:08:58Z","timestamp":1771236538429,"version":"3.50.1"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031183669","type":"print"},{"value":"9783031183676","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-18367-6_3","type":"book-chapter","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T16:05:36Z","timestamp":1666281936000},"page":"36-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Scheduling with\u00a0Machine Conflicts"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1590-346X","authenticated-orcid":false,"given":"Moritz","family":"Buchem","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3786-916X","authenticated-orcid":false,"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9331-445X","authenticated-orcid":false,"given":"Daniel","family":"Schmidt genannt Waldschmidt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0305-0548(00)00074-5","volume":"29","author":"AH Abdekhodaee","year":"2002","unstructured":"Abdekhodaee, A.H., Wirth, A.: Scheduling parallel machines with a single server: some solvable cases and heuristics. Comput. Oper. Res. 29(3), 295\u2013315 (2002)","journal-title":"Comput. Oper. Res."},{"issue":"11","key":"3_CR2","doi-asserted-by":"publisher","first-page":"1867","DOI":"10.1016\/S0305-0548(03)00144-8","volume":"31","author":"AH Abdekhodaee","year":"2004","unstructured":"Abdekhodaee, A.H., Wirth, A., Gan, H.S.: Equal processing and equal setup time cases of scheduling parallel machines with a single server. Comput. Oper. Res. 31(11), 1867\u20131889 (2004)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"3_CR3","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1016\/j.cor.2004.08.013","volume":"33","author":"AH Abdekhodaee","year":"2006","unstructured":"Abdekhodaee, A.H., Wirth, A., Gan, H.S.: Scheduling two parallel machines with a single server: the general case. Comput. Oper. Res. 33(4), 994\u20131009 (2006)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"3_CR4","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55\u201366 (1998)","journal-title":"J. Sched."},{"issue":"2","key":"3_CR5","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"BS Baker","year":"1996","unstructured":"Baker, B.S., Coffman, E.G., Jr.: Mutual exclusion scheduling. Theoret. Comput. Sci. 162(2), 225\u2013243 (1996)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2005.09.027","volume":"349","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Fomin, F.V.: Equitable colorings of bounded treewidth graphs. Theoret. Comput. Sci. 349(1), 22\u201330 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-57182-5_21","volume-title":"Mathematical Foundations of Computer Science 1993","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., Jansen, K.: On the complexity of scheduling incompatible jobs with unit-times. In: Borzyszkowski, A.M., Soko\u0142owski, S. (eds.) MFCS 1993. LNCS, vol. 711, pp. 291\u2013300. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-57182-5_21"},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Jansen, K.: Restrictions of graph partition problems. Part I. Theor. Comput. Sci. 148(1), 93\u2013109 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"3_CR9","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0166-218X(94)90009-4","volume":"55","author":"HL Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Jansen, K., Woeginger, G.J.: Scheduling with incompatible jobs. Discret. Appl. Math. 55(3), 219\u2013232 (1994)","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"3_CR10","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1002\/jos.120","volume":"5","author":"P Brucker","year":"2002","unstructured":"Brucker, P., Dhaenens-Flipo, C., Knust, S., Kravchenko, S.A., Werner, F.: Complexity results for parallel machine problems with a single server. J. Sched. 5(6), 429\u2013457 (2002)","journal-title":"J. Sched."},{"key":"3_CR11","unstructured":"Buchem, M., Kleist, L., Schmidt\u00a0genannt Waldschmidt, D.: Scheduling with machine conflicts. CoRR abs\/2102.08231 (2021). https:\/\/arxiv.org\/abs\/2102.08231"},{"key":"3_CR12","unstructured":"Chen, J.J., Hahn, T., Hoeksma, R., Megow, N., von der Br\u00fcggen, G.: Scheduling self-suspending tasks: new and old results. In: Proceedings of the 31st Euromicro Conference on Real-Time Systems (2019)"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Chen, L., Jansen, K., Zhang, G.: On the optimality of approximation schemes for the classical scheduling problem. In: Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, pp. 657\u2013668 (2013)","DOI":"10.1137\/1.9781611973402.50"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1007\/3-540-48224-5_70","volume-title":"Automata, Languages and Programming","author":"M Chrobak","year":"2001","unstructured":"Chrobak, M., Csirik, J., Imreh, C., Noga, J., Sgall, J., Woeginger, G.J.: The buffer minimization problem for multiprocessor scheduling with conflicts. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 862\u2013874. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-48224-5_70"},{"key":"3_CR15","unstructured":"Das, S., Wiese, A.: On minimizing the makespan when some jobs cannot be assigned on the same machine. In: Proceedings of the 25th Annual European Symposium on Algorithms (2017)"},{"issue":"9","key":"3_CR16","doi-asserted-by":"publisher","first-page":"2242","DOI":"10.1016\/j.cor.2011.11.007","volume":"39","author":"HS Gan","year":"2012","unstructured":"Gan, H.S., Wirth, A., Abdekhodaee, A.H.: A branch-and-price algorithm for the general case of scheduling parallel machines with a single server. Comput. Oper. Res. 39(9), 2242\u20132247 (2012)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"3_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.dam.2008.04.016","volume":"157","author":"F Gardi","year":"2009","unstructured":"Gardi, F.: Mutual exclusion scheduling with interval graphs or related classes. Part I. Discret. Appl. Math. 157(1), 19\u201335 (2009)","journal-title":"Discret. Appl. Math."},{"key":"3_CR18","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness (1979)"},{"issue":"9","key":"3_CR19","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"issue":"2","key":"3_CR20","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discret. Math."},{"issue":"3","key":"3_CR22","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0166-218X(99)00206-1","volume":"102","author":"NG Hall","year":"2000","unstructured":"Hall, N.G., Potts, C.N., Sriskandarajah, C.: Parallel machine scheduling with a common server. Discret. Appl. Math. 102(3), 223\u2013243 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20133","key":"3_CR23","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(93)90165-P","volume":"111","author":"P Hansen","year":"1993","unstructured":"Hansen, P., Hertz, A., Kuplinsky, J.: Bounded vertex colorings of graphs. Discret. Math. 111(1\u20133), 305\u2013312 (1993)","journal-title":"Discret. Math."},{"issue":"1","key":"3_CR24","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within 1- $$\\varepsilon $$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"3_CR25","unstructured":"Hochbaum, D.S.: Various notions of approximations: good, better, best and more. Approx. Algorithms NP-Hard Probl., 346\u2013398 (1997)"},{"issue":"1","key":"3_CR26","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2021.05.013","volume":"876","author":"F H\u00f6hne","year":"2021","unstructured":"H\u00f6hne, F., van Stee, R.: Buffer minimization with conflicts on a line. Theoret. Comput. Sci. 876, 25\u201333 (2021)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"3_CR28","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen, K.: An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. SIAM J. Discret. Math. 24(2), 457\u2013485 (2010)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"3_CR29","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1287\/moor.2019.1036","volume":"45","author":"K Jansen","year":"2020","unstructured":"Jansen, K., Klein, K.M., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. Math. Oper. Res. 45(4), 1371\u20131392 (2020)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"3_CR30","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10878-014-9727-z","volume":"30","author":"Y Jiang","year":"2014","unstructured":"Jiang, Y., Zhang, Q., Hu, J., Dong, J., Ji, M.: Single-server parallel-machine scheduling with loading and unloading times. J. Comb. Optim. 30(2), 201\u2013213 (2014). https:\/\/doi.org\/10.1007\/s10878-014-9727-z","journal-title":"J. Comb. Optim."},{"key":"3_CR31","unstructured":"Kern, W., Nawijn, W.N.: Scheduling multi-operation jobs with time lags on a single machine. In: Proceedings of the 2nd Twente Workshop on Graphs and Combinatorial Optimization (1991)"},{"key":"3_CR32","first-page":"116","volume":"38","author":"D K\u0151nig","year":"1931","unstructured":"K\u0151nig, D.: Gr\u00e1fok \u00e9s m\u00e1trixok. Mat. Fizikai Lapok 38, 116\u2013119 (1931)","journal-title":"Mat. Fizikai Lapok"},{"issue":"11","key":"3_CR33","doi-asserted-by":"publisher","first-page":"2457","DOI":"10.1016\/j.cor.2011.12.011","volume":"39","author":"MY Kim","year":"2012","unstructured":"Kim, M.Y., Lee, Y.H.: MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server. Comput. Oper. Res. 39(11), 2457\u20132468 (2012)","journal-title":"Comput. Oper. Res."},{"key":"3_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-56039-6","volume-title":"Combinatorial Optimization","author":"BH Korte","year":"2018","unstructured":"Korte, B.H., Vygen, J.: Combinatorial Optimization, vol. 6. Springer, Heidelberg (2018)"},{"issue":"12","key":"3_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0895-7177(97)00236-7","volume":"26","author":"SA Kravchenko","year":"1997","unstructured":"Kravchenko, S.A., Werner, F.: Parallel machine scheduling problems with a single server. Math. Comput. Model. 26(12), 1\u201311 (1997)","journal-title":"Math. Comput. Model."},{"key":"3_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/3-540-56939-1_60","volume-title":"Automata, Languages and Programming","author":"C Lund","year":"1993","unstructured":"Lund, C., Yannakakis, M.: The approximation of maximum subgraph problems. In: Lingas, A., Karlsson, R., Carlsson, S. (eds.) ICALP 1993. LNCS, vol. 700, pp. 40\u201351. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-56939-1_60"},{"key":"3_CR37","doi-asserted-by":"crossref","unstructured":"Rajkumar, R., Sha, L., Lehoczky, J.P.: Real-time synchronization protocols for multiprocessors. In: Proceedings of the 9th IEEE Real-Time Systems Symposium, vol. 88, pp. 259\u2013269 (1988)","DOI":"10.1109\/REAL.1988.51121"},{"issue":"1","key":"3_CR38","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"SK Sahni","year":"1976","unstructured":"Sahni, S.K.: Algorithms for scheduling independent tasks. J. ACM 23(1), 116\u2013127 (1976)","journal-title":"J. ACM"},{"issue":"10","key":"3_CR39","doi-asserted-by":"publisher","first-page":"1195","DOI":"10.1109\/12.543712","volume":"45","author":"SK Sahni","year":"1996","unstructured":"Sahni, S.K.: Scheduling master-slave multiprocessor systems. IEEE Trans. Comput. 45(10), 1195\u20131199 (1996)","journal-title":"IEEE Trans. Comput."},{"key":"3_CR40","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0012-365X(96)00208-7","volume":"165","author":"D de Werra","year":"1997","unstructured":"de Werra, D.: Restricted coloring models for timetabling. Discret. Math. 165, 161\u2013170 (1997)","journal-title":"Discret. Math."},{"key":"3_CR41","doi-asserted-by":"crossref","unstructured":"Xie, X., Li, Y., Zhou, H., Zheng, Y.: Scheduling parallel machines with a single server. In: Proceedings of 2012 International Conference on Measurement, Information and Control, vol. 1, pp. 453\u2013456. IEEE (2012)","DOI":"10.1109\/MIC.2012.6273340"},{"key":"3_CR42","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-18367-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T07:28:56Z","timestamp":1728199736000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-18367-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031183669","9783031183676"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-18367-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"21 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Potsdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2022.eu\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"57% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}