{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T10:08:56Z","timestamp":1771236536085,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,4,22]],"date-time":"2016-04-22T00:00:00Z","timestamp":1461283200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s10951-016-0482-0","type":"journal-article","created":{"date-parts":[[2016,4,22]],"date-time":"2016-04-22T05:00:48Z","timestamp":1461301248000},"page":"355-372","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["An exact algorithm for parallel machine scheduling with conflicts"],"prefix":"10.1007","volume":"20","author":[{"given":"Daniel","family":"Kowalczyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roel","family":"Leus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"482_CR1","doi-asserted-by":"crossref","unstructured":"Alvim, A.C.F., Ribeiro, C.C. (2004). A hybrid bin-packing heuristic to multiprocessor scheduling. In Experimental and efficient algorithms. Proceedings of the third international workshop WEA 2004, Angra dos Reis, Brazil, May 25\u201328.","DOI":"10.1007\/978-3-540-24838-5_1"},{"key":"482_CR2","first-page":"801","volume":"56","author":"BV Balachandran","year":"1981","unstructured":"Balachandran, B. V., & Zoltners, A. A. (1981). An interactive audit-staff scheduling decision support system. The Accounting Review, 56, 801\u2013812.","journal-title":"The Accounting Review"},{"issue":"1","key":"482_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10479-011-0971-7","volume":"213","author":"L Berghman","year":"2014","unstructured":"Berghman, L., Leus, R., & Spieksma, F. C. R. (2014). Optimal solutions for a dock assignment problem with trailer transportation. Annals of Operations Research, 213(1), 3\u201325.","journal-title":"Annals of Operations Research"},{"key":"482_CR4","unstructured":"Bettinelli, A., Cacchiani, V., Malaguti, E. (2014). Bounds and algorithms for the knapsack problem with conflict graph. Technical Report OR-14-16, DEIS, University of Bologna. URL \n                        http:\/\/www.optimization-online.org\/DB_FILE\/2014\/06\/4401.pdf\n                        \n                    ."},{"issue":"3","key":"482_CR5","doi-asserted-by":"crossref","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. (1994). Scheduling with incompatible jobs. Discrete Applied Mathematics, 55(3), 219\u2013232.","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"482_CR6","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1147\/sj.403.0666","volume":"40","author":"RA Botha","year":"2001","unstructured":"Botha, R. A., & Eloff, J. H. P. (2001). Separation of duties for access control enforcement in workflow environments. IBM Systems Journal, 40(3), 666\u2013682.","journal-title":"IBM Systems Journal"},{"issue":"4","key":"482_CR7","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251\u2013256.","journal-title":"Communications of the ACM"},{"issue":"6","key":"482_CR8","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R Carraghan","year":"1990","unstructured":"Carraghan, R., & Pardalos, P. M. (1990). An exact algorithm for the maximum clique problem. Operations Research Letters, 9(6), 375\u2013382.","journal-title":"Operations Research Letters"},{"issue":"2","key":"482_CR9","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1287\/ijoc.7.2.191","volume":"7","author":"M Dell\u2019Amico","year":"1995","unstructured":"Dell\u2019Amico, M., & Martello, S. (1995). Optimal scheduling of tasks on identical parallel processors. ORSA Journal on Computing, 7(2), 191\u2013200.","journal-title":"ORSA Journal on Computing"},{"issue":"3","key":"482_CR10","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1287\/ijoc.1070.0246","volume":"20","author":"M Dell\u2019Amico","year":"2008","unstructured":"Dell\u2019Amico, M., Iori, M., Martello, S., & Monaci, M. (2008). Heuristic and exact algorithms for the identical parallel machine scheduling problem. INFORMS Journal on Computing, 20(3), 333\u2013344.","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"482_CR11","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1287\/ijoc.1100.0406","volume":"23","author":"S Elhedhli","year":"2011","unstructured":"Elhedhli, S., Li, L., Gzara, M., & Naoum-Sawaya, J. (2011). A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS Journal on Computing, 23(3), 404\u2013415.","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"482_CR12","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G Even","year":"2009","unstructured":"Even, G., Halld\u00f3rsson, M. M., Kaplan, L., & Ron, D. (2009). Scheduling with conflicts: online and offline algorithms. Journal of Scheduling, 12(2), 199\u2013224.","journal-title":"Journal of Scheduling"},{"issue":"2","key":"482_CR13","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0305-0548(94)90053-1","volume":"21","author":"PM Fran\u00e7a","year":"1994","unstructured":"Fran\u00e7a, P. M., Gendreau, M., Laporte, G., & M\u00fcller, F. M. (1994). A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective. Computers & Operations Research, 21(2), 205\u2013210.","journal-title":"Computers & Operations Research"},{"issue":"2","key":"482_CR14","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1023\/B:JOCO.0000031420.05971.29","volume":"8","author":"A Frangioni","year":"2004","unstructured":"Frangioni, A., Necciari, E., & Scutella, M. G. (2004). A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems. Journal of Combinatorial Optimization, 8(2), 195\u2013220.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"482_CR15","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.dam.2008.04.016","volume":"157","author":"F Gardi","year":"2009","unstructured":"Gardi, F. (2009). Mutual exclusion scheduling with interval graphs or related classes, part I. Discrete Applied Mathematics, 157(1), 19\u201335.","journal-title":"Discrete Applied Mathematics"},{"key":"482_CR16","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: WH Freeman and Company."},{"issue":"5","key":"482_CR17","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1287\/opre.1080.0635","volume":"57","author":"DR Gaur","year":"2009","unstructured":"Gaur, D. R., Krishnamurti, R., & Kohli, R. (2009). Conflict resolution in the scheduling of television commercials. Operations Research, 57(5), 1098\u20131105.","journal-title":"Operations Research"},{"issue":"1","key":"482_CR18","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.ejor.2015.06.073","volume":"248","author":"M Gendreau","year":"2016","unstructured":"Gendreau, M., Manerba, D., & Mansini, R. (2016). The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: A branch-and-price approach. European Journal of Operational Research, 248(1), 59\u201371.","journal-title":"European Journal of Operational Research"},{"key":"482_CR19","unstructured":"Giblin, C., Hada, S.(2008). Towards seperation of duties for services. In The 6th international workshop on SOA & web services best practices committee, Nashville, October 19, OOPSLA."},{"issue":"6","key":"482_CR20","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"PC Gilmore","year":"1961","unstructured":"Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849\u2013859.","journal-title":"Operations Research"},{"issue":"9","key":"482_CR21","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9), 1563\u20131581.","journal-title":"Bell System Technical Journal"},{"issue":"2","key":"482_CR22","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2), 416\u2013429.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"482_CR23","unstructured":"Harvey, W.D., Ginsberg M.L. (1995). Limited discrepancy search. In Proceedings of the fourteenth international joint conference on artificial intelligence, pp. 607\u2013615, Morgan Kaufmann."},{"key":"482_CR24","unstructured":"Hastad, J. (1996). Clique is hard to approximate within \n                        $$n^{1 - \\epsilon }$$\n                        \n                            \n                                            \n                                \n                                    n\n                                    \n                                        1\n                                        -\n                                        \u03f5\n                                    \n                                \n                            \n                        \n                    . In Proceedings of the 37th annual symposium on foundations of computer science, pp. 627\u2013636. IEEE."},{"issue":"4","key":"482_CR25","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s12532-012-0042-3","volume":"4","author":"S Held","year":"2012","unstructured":"Held, S., Cook, W., & Sewell, E. C. (2012). Maximum-weight stable sets and safe lower bounds for graph coloring. Mathematical Programming Computation, 4(4), 363\u2013381.","journal-title":"Mathematical Programming Computation"},{"issue":"1","key":"482_CR26","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1504\/IJOR.2012.044026","volume":"13","author":"M Hifi","year":"2012","unstructured":"Hifi, M., & Otmani, N. (2012). An algorithm for the disjunctively constrained knapsack problem. International Journal of Operational Research, 13(1), 22\u201343.","journal-title":"International Journal of Operational Research"},{"issue":"3","key":"482_CR27","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1023\/A:1022908509269","volume":"6","author":"S Irani","year":"2003","unstructured":"Irani, S., & Leung, V. (2003). Scheduling with conflicts on bipartite and interval graphs. Journal of Scheduling, 6(3), 287\u2013307.","journal-title":"Journal of Scheduling"},{"key":"482_CR28","doi-asserted-by":"crossref","unstructured":"Johnson, D.S. (1973). Approximation algorithms for combinatorial problems. In Proceedings of the fifth annual ACM symposium on theory of computing, pages 38\u201349, ACM.","DOI":"10.1145\/800125.804034"},{"key":"482_CR29","doi-asserted-by":"crossref","unstructured":"Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Schevon, C. (1991). Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning. Operations Research, 39(3), 378\u2013406.","DOI":"10.1287\/opre.39.3.378"},{"key":"482_CR30","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1016\/j.endm.2010.05.088","volume":"36","author":"C Joncour","year":"2010","unstructured":"Joncour, C., Michel, S., Sadykov, R., Sverdlov, D., & Vanderbeck, F. (2010). Column generation based primal heuristics. Electronic Notes in Discrete Mathematics, 36, 695\u2013702.","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"482_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin: Springer."},{"key":"482_CR32","doi-asserted-by":"crossref","unstructured":"Kowalczyk, D., Leus, R. (2015). An exact algorithm for parallel machine scheduling with conflicts. Technical Report \n                        $${\\rm KBI}\\_1505$$\n                        \n                            \n                                            \n                                \n                                    KBI\n                                    _\n                                    1505\n                                \n                            \n                        \n                    , Department of Decision Sciences and Information Management, FEB, KU Leuven.","DOI":"10.2139\/ssrn.2572867"},{"key":"482_CR33","series-title":"NATO advanced study Institutes series","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-94-009-7801-0_3","volume-title":"Deterministic and stochastic scheduling","author":"EL Lawler","year":"1982","unstructured":"Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1982). Recent developments in deterministic sequencing and scheduling: A survey. In M. A. H. Dempster, J. K. Lenstra, & A. H. G. Rinnooy\u00a0Kan (Eds.), Deterministic and stochastic scheduling (pp. 35\u201373)., NATO advanced study Institutes series New York: Springer."},{"issue":"2","key":"482_CR34","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1287\/ijoc.1070.0245","volume":"20","author":"E Malaguti","year":"2008","unstructured":"Malaguti, E., Monaci, M., & Toth, P. (2008). A metaheuristic approach for the vertex coloring problem. INFORMS Journal on Computing, 20(2), 302\u2013316.","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"482_CR35","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/net.21588","volume":"65","author":"D Manerba","year":"2015","unstructured":"Manerba, D., & Mansini, R. (2015). A branch-and-cut algorithm for the multi-vehicle traveling purchaser problem with pairwise incompatibility constraints. Networks, 65(2), 139\u2013154.","journal-title":"Networks"},{"issue":"3","key":"482_CR36","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0377-2217(77)90024-8","volume":"1","author":"S Martello","year":"1977","unstructured":"Martello, S., & Toth, P. (1977). An upper bound for the zero-one knapsack problem and a branch and bound algorithm. European Journal of Operational Research, 1(3), 169\u2013175.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"482_CR37","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","volume":"45","author":"S Martello","year":"1999","unstructured":"Martello, S., Pisinger, D., & Toth, P. (1999). Dynamic programming and strong bounds for the 0\u20131 knapsack problem. Management Science, 45(3), 414\u2013424.","journal-title":"Management Science"},{"key":"482_CR38","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-4975-8","volume-title":"Large scale linear and integer optimization: A unified approach","author":"RK Martin","year":"1999","unstructured":"Martin, R. K. (1999). Large scale linear and integer optimization: A unified approach. New York: Springer."},{"issue":"4","key":"482_CR39","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"A Mehrotra","year":"1996","unstructured":"Mehrotra, A., & Trick, M. (1996). A column generation approach for graph coloring. INFORMS Journal on Computing, 8(4), 344\u2013354.","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"482_CR40","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1287\/ijoc.1090.0355","volume":"22","author":"AEF Muritiba","year":"2010","unstructured":"Muritiba, A. E. F., Iori, M., Malaguti, E., & Toth, P. (2010). Algorithms for the bin packing problem with conflicts. INFORMS Journal on Computing, 22(3), 401\u2013415.","journal-title":"INFORMS Journal on Computing"},{"issue":"4","key":"482_CR41","first-page":"424","volume":"8","author":"PRJ \u00d6sterg\u00e5rd","year":"2001","unstructured":"\u00d6sterg\u00e5rd, P. R. J. (2001). A new algorithm for the maximum-weight clique problem. Nordic Journal of Computing, 8(4), 424\u2013436.","journal-title":"Nordic Journal of Computing"},{"issue":"2","key":"482_CR42","doi-asserted-by":"crossref","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy, U., & Schauer, J. (2009). The knapsack problem with conflict graphs. Journal of Graph Algorithms and Applications, 13(2), 233\u2013249.","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"482_CR43","unstructured":"ROADEF. (2011). Google ROADEF\/EURO challenge 2012: Machine reassignment. \n                        http:\/\/challenge.roadef.org\/2012\/files\/problem_definition_v1.pdf\n                        \n                    ."},{"issue":"2","key":"482_CR44","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/ijoc.1120.0499","volume":"25","author":"R Sadykov","year":"2013","unstructured":"Sadykov, R., & Vanderbeck, F. (2013). Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS Journal on Computing, 25(2), 244\u2013255.","journal-title":"INFORMS Journal on Computing"},{"key":"482_CR45","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/978-3-642-16934-2_20","volume":"6426","author":"HY Sun","year":"2010","unstructured":"Sun, H. Y., Zhao, W. L., & Yang, J. (2010). Managing conflict of interest in service composition. Lecture notes in computer science, 6426, 273\u2013290.","journal-title":"Lecture notes in computer science"},{"issue":"1","key":"482_CR46","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1287\/opre.48.1.111.12453","volume":"48","author":"F Vanderbeck","year":"2000","unstructured":"Vanderbeck, F. (2000). On Dantzig\u2013Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 48(1), 111\u2013128.","journal-title":"Operations Research"},{"issue":"2","key":"482_CR47","first-page":"163","volume":"66","author":"AA Zykov","year":"1949","unstructured":"Zykov, A. A. (1949). On some properties of linear complexes. Matematicheskii Sbornik, 66(2), 163\u2013188.","journal-title":"Matematicheskii Sbornik"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-016-0482-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0482-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0482-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0482-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T05:39:52Z","timestamp":1559453992000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-016-0482-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,22]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["482"],"URL":"https:\/\/doi.org\/10.1007\/s10951-016-0482-0","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,22]]}}}