{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:44:57Z","timestamp":1774417497454,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,2,1]],"date-time":"2007-02-01T00:00:00Z","timestamp":1170288000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2007,2,14]]},"DOI":"10.1007\/s10951-006-0003-7","type":"journal-article","created":{"date-parts":[[2007,2,3]],"date-time":"2007-02-03T03:12:28Z","timestamp":1170472348000},"page":"111-127","source":"Crossref","is-referenced-by-count":27,"title":["Time slot scheduling of compatible jobs"],"prefix":"10.1007","volume":"10","author":[{"given":"M.","family":"Demange","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. de","family":"Werra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,2,1]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1023\/A:1008764212265","volume":"16","author":"L. Alfandari","year":"2000","unstructured":"Alfandari, L. and V. T. Paschos, \u201cMaster\u2013slave strategy and polynomial approximation,\u201d Computational Optimization and Applications, 16, 231\u2013245 (2000).","journal-title":"Computational Optimization and Applications"},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A. Bar-Noy","year":"1988","unstructured":"Bar-Noy, A., M. Bellare, M. M. Halld\u00f3rsson, H. Shachnai, and T. Tamir, \u201cOn chromatic sums and distributed resource allocation,\u201d Information and Computation, 140, 183\u2013202 (1988).","journal-title":"Information and Computation"},{"key":"3_CR3","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"Berge, C., Graphs and Hypergraphs. North Holland, Amsterdam, 1973."},{"key":"3_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03217-6","volume-title":"Scheduling Computer and Manufacturing Processes","author":"J. Blazewicz","year":"1996","unstructured":"Blazewicz, J., K. H. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Scheduling Computer and Manufacturing Processes. Springer Verlag, Berlin (1996)."},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0166-218X(94)90009-4","volume":"55","author":"H. L. Bodlaender","year":"1994","unstructured":"Bodlaender, H. L., K. Jansen, and G. J. Woeginger, \u201cScheduling with incompatible jobs,\u201d Discrete Applied Mathematics, 55, 219\u2013232 (1994).","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"3_CR6","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"B. B. Boppana","year":"1992","unstructured":"Boppana, B. B. and M. M. Halld\u00f3rsson, \u201cApproximating maximum independent sets by excluding subgraphs,\u201d BIT, 32(2), 180\u2013196 (1992).","journal-title":"BIT"},{"key":"3_CR7","unstructured":"Boudhar, M. and G. Finke, \u201cScheduling on a batch machine with job compatibilities,\u201d Special issue ORBEL-14: Emerging challenges in operations research (Mons, 2000). Belgian Journal of Operational Research Statistical Computer Science, 40(1\u20132), 69\u201380 (2000)."},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., V. B. Le, and J. P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999).","DOI":"10.1137\/1.9780898719796"},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02260498","volume":"35","author":"R. E. Burkard","year":"1985","unstructured":"Burkard, R. E., \u201cTime-slot assignment for TDMA-systems,\u201d Computing, 35, 99\u2013112 (1985).","journal-title":"Computing"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Chv\u00e0tal, V., \u201cPerfectly ordered graphs,\u201d in C. Berge and V. Chv\u00e0tal (Eds.), Topics on Perfect Graphs, volume 21 of Annals of Discrete Math. (1984) pp. 253\u2013277.","DOI":"10.1016\/S0304-0208(08)72923-2"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Cook, W. J., W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, Combinatorial Optimization. J. Wiley, 1998.","DOI":"10.1002\/9781118033142"},{"key":"3_CR12","first-page":"165","volume":"8","author":"D. de Werra","year":"1970","unstructured":"de Werra, D., \u201cOn some combinatorial problems arising in scheduling,\u201d Canad. Operational Research Society Journal, 8, 165\u2013175 (1970).","journal-title":"Canad. Operational Research Society Journal"},{"key":"3_CR13","first-page":"191","volume":"7","author":"D. de Werra","year":"1990","unstructured":"de Werra, D., \u201cHeuristics for graph coloring,\u201d Computing, 7, 191\u2013208 (1990).","journal-title":"Computing"},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF01858447","volume":"12","author":"D. de Werra","year":"1996","unstructured":"de Werra, D. and J. Erschler, \u201cOpen shop scheduling with some additional constraints,\u201d Graphs and Combinatorics, 12, 81\u201393 (1996).","journal-title":"Graphs and Combinatorics"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0166-218X(94)90207-0","volume":"49","author":"D. de Werra","year":"1994","unstructured":"de Werra, D. and Y. Gay, \u201cChromatic scheduling and frequency assignment,\u201d Discrete Applied Mathematics, 49, 165\u2013174 (1994).","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR16","unstructured":"Fiala, J. The NP-completeness of the edge precoloring extension problem on bipartite graphs. Unpublished result."},{"key":"3_CR17","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"M. R. Garey","year":"1975","unstructured":"Garey, M. R. and D. S. Johnson, \u201cComplexity results for multiprocessor scheduling under resource constraints,\u201d SIAM Journal on Computing, 4, 397\u2013411 (1975).","journal-title":"SIAM Journal on Computing"},{"key":"3_CR18","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0012-365X(00)00110-2","volume":"224","author":"S. Gerke","year":"2000","unstructured":"Gerke, S., \u201cColouring weighted bipartite graphs with a co-site constraint,\u201d Discrete Mathematics, 224, 125\u2013138 (2000).","journal-title":"Discrete Mathematics"},{"key":"3_CR19","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)."},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I., \u201cThe NP-completeness of edge-colouring,\u201d SIAM Journal on Computing, 10, 718\u2013720 (1981).","journal-title":"SIAM Journal on Computing"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Jansen, K., \u201cApproximation results for the optimum cost chromatic partition problem,\u201d in P. M. Pardalos and D. Du (Eds.), Theoretical Computer Science, Network Design: Connectivity and Facilities Location (1997) pp. 143\u2013168.","DOI":"10.1007\/3-540-63165-8_226"},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0166-218X(96)00085-6","volume":"75","author":"K. Jansen","year":"1997","unstructured":"Jansen, K. and P. Scheffler, \u201cGeneralized coloring for tree-like graphs,\u201d Discrete Applied Mathematics, 75, 135\u2013155 (1997).","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR23","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"Johnson, D. S., \u201cApproximation algorithms for combinatorial problems,\u201d Journal of Computer and System Sciences, 9, 256\u2013278 (1974).","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR24","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"Karp, R. M., \u201cReducibility among combinatorial problems,\u201d in R. E. Miller and J. W. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, New York (1972) pp. 85\u2013103."},{"key":"3_CR25","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D. K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D., \u201c\u00dcber graphen und iher anwendung auf determinantentheorie und mengenlehre,\u201d Annals of Mathematics, 77, 453\u2013465 (1916).","journal-title":"Annals of Mathematics"},{"key":"3_CR26","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/PL00009252","volume":"23","author":"S. Nicoloso","year":"1999","unstructured":"Nicoloso, S., M. Sarrafzadeh, and X. Song, \u201cOn the sum coloring problem on interval graphs,\u201d Algorithmica, 23, 109\u2013126 (1999).","journal-title":"Algorithmica"},{"key":"3_CR27","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/S0377-2217(99)00153-8","volume":"120","author":"C. N. Potts","year":"2000","unstructured":"Potts, C. N. and M. Y. Kovalyov, \u201cScheduling with batching: a review,\u201d European Journal of Operational Research, 120, 228\u2013249 (2000).","journal-title":"European Journal of Operational Research"},{"key":"3_CR28","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/1099-1425(200101\/02)4:1<25::AID-JOS58>3.0.CO;2-7","volume":"4","author":"C. N. Potts","year":"2001","unstructured":"Potts, C. N., V. A. Strusevich, and T. Tautenhahn, \u201cScheduling batches with simultaneous job processing for two-machine shop problems,\u201d Journal of Scheduling, 4, 25\u201351 (2001).","journal-title":"Journal of Scheduling"},{"key":"3_CR29","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0167-6377(85)90042-2","volume":"4","author":"F. Rendl","year":"1985","unstructured":"Rendl, F., \u201cOn the complexity of decomposing matrices arising in satellite communication,\u201d Operations Research Letters, 4, 5\u20138 (1985).","journal-title":"Operations Research Letters"},{"issue":"2","key":"3_CR30","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"H. U. Simon","year":"1990","unstructured":"Simon, H. U., \u201cOn approximate solutions for combinatorial optimization problems,\u201d SIAM Journal on Discrete Mathematics, 3(2), 294\u2013310 (1990).","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"3_CR31","doi-asserted-by":"crossref","first-page":"161","DOI":"10.7151\/dmgt.1049","volume":"17","author":"Z. Tuza","year":"1997","unstructured":"Tuza, Z., \u201cGraph colorings with local constraints-a survey,\u201d Discussiones Mathematicae Graph Theory, 17, 161\u2013228 (1997).","journal-title":"Discussiones Mathematicae Graph Theory"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-006-0003-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-006-0003-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-006-0003-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T09:39:37Z","timestamp":1559468377000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-006-0003-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,1]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,2,14]]}},"alternative-id":["3"],"URL":"https:\/\/doi.org\/10.1007\/s10951-006-0003-7","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2,1]]}}}