{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T22:47:13Z","timestamp":1780440433007,"version":"3.54.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"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":[[2008,8]]},"DOI":"10.1007\/s10951-008-0066-8","type":"journal-article","created":{"date-parts":[[2008,4,30]],"date-time":"2008-04-30T20:12:38Z","timestamp":1209586358000},"page":"263-277","source":"Crossref","is-referenced-by-count":147,"title":["Graph colouring approaches for a satellite range scheduling problem"],"prefix":"10.1007","volume":"11","author":[{"given":"Nicolas","family":"Zufferey","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrick","family":"Amstutz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philippe","family":"Giaccari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,8,1]]},"reference":[{"issue":"2","key":"66_CR1","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A. Bar-Noy","year":"2002","unstructured":"Bar-Noy, A., Guha, S., Naor, J. S., & Schieber, B. (2002). Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing, 31(2), 331\u2013352.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"66_CR2","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1023\/B:JOSH.0000013053.32600.3c","volume":"7","author":"L. Barbulescu","year":"2004","unstructured":"Barbulescu, L., Watson, J.-P., Whitley, L. D., & Howe, A. E. (2004a). Scheduling space-ground communications for the air force satellite control network. Journal of Scheduling, 7(1), 7\u201334.","journal-title":"Journal of Scheduling"},{"key":"66_CR3","unstructured":"Barbulescu, L., Howe, A. E., Whitley, L. D., & Roberts, M. (2004b). Trading places: how to schedule more in a multi-resource oversubscribed scheduling problem. In International conference on automated planning and scheduling."},{"issue":"9\u201310","key":"66_CR4","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1016\/j.mcm.2005.12.004","volume":"43","author":"L. Barbulescu","year":"2006","unstructured":"Barbulescu, L., Howe, A. E., & Whitley, L. D. (2006). AFSCN scheduling: how the problem and solution have evolved. Mathematical and Computer Modelling, 43(9\u201310), 1023\u20131037","journal-title":"Mathematical and Computer Modelling"},{"key":"66_CR5","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1023\/A:1026488509554","volume":"4","author":"E. Bensana","year":"1999","unstructured":"Bensana, E., Lemaitre, M., & Verfaillie, G. (1999). Earth observation satellite management. Constraints, 4, 293\u2013299.","journal-title":"Constraints"},{"key":"66_CR6","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1016\/j.ejor.2005.12.026","volume":"177","author":"N. Bianchessi","year":"2007","unstructured":"Bianchessi, N., Cordeau, J.-F., Desrosiers, J., Laporte, G., & Raymond, V. (2007). A heuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites. European Journal of Operational Research, 177, 750\u2013762.","journal-title":"European Journal of Operational Research"},{"key":"66_CR7","unstructured":"Bloechliger, I. (2005). Suboptimal colorings and solution of large chromatic scheduling problems. PhD thesis, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Switzerland."},{"key":"66_CR8","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1016\/j.cor.2006.05.014","volume":"35","author":"I. Bloechliger","year":"2008","unstructured":"Bloechliger, I., & Zufferey, N. (2008). A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 35, 960\u2013975.","journal-title":"Computers & Operations Research"},{"key":"66_CR9","doi-asserted-by":"publisher","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 vertices of a graph. Communications of the Association for Computing Machinery, 22, 251\u2013256.","journal-title":"Communications of the Association for Computing Machinery"},{"key":"66_CR10","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1057\/palgrave.jors.2601926","volume":"56","author":"J.-F. Cordeau","year":"2005","unstructured":"Cordeau, J.-F., & Laporte, G. (2005). Maximizing the value of an earth observation satellite orbit. Journal of the Operational Research Society, 56, 962\u2013968.","journal-title":"Journal of the Operational Research Society"},{"key":"66_CR11","unstructured":"Culberson, J. (1992). Iterated greedy graph coloring and the difficulty landscape (Tech. rept. TR 92-07). Department of Computer Science, University of Alberta, Edmonton."},{"key":"66_CR12","unstructured":"Culberson, J. C., & Luo, F. (1995). Exploring the k-colorable landscape with iterated greedy. DIMACS Series in Discrete Mathematics and Theoretical Computer Science."},{"key":"66_CR13","first-page":"131","volume":"81","author":"S. Dauz\u00e8re-P\u00e9r\u00e8s","year":"1995","unstructured":"Dauz\u00e8re-P\u00e9r\u00e8s, S. (1995). Minimizing late jobs in the general one machine scheduling problem. European Journal of Operational Research, 81, 131\u2013142.","journal-title":"European Journal of Operational Research"},{"key":"66_CR14","volume-title":"Handbook of genetic algorithms","author":"L. Davis","year":"1991","unstructured":"Davis, L. (1991). Handbook of genetic algorithms. New York: Van Nostrand Reinhold."},{"key":"66_CR15","unstructured":"Frank, J., Jonsson, A., Morris, R., & Smith, D. (2001). Planning and scheduling for fleets of earth observing satellites. In Proceedings of the sixth international symposium on artificial intelligence, robotics, automation and space."},{"key":"66_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3752-3_7","volume-title":"Mathematical programming for Earth observation satellite mission planning","author":"V. Gabrel","year":"2003","unstructured":"Gabrel, V., & Murat, C. (2003). Operations research in space and air. In Mathematical programming for Earth observation satellite mission planning. Boston: Kluwer Academic (Chap.\u00a07)."},{"issue":"4","key":"66_CR17","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"P. Galinier","year":"1999","unstructured":"Galinier, P., & Hao, J. K. (1999). Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3(4), 379\u2013397.","journal-title":"Journal of Combinatorial Optimization"},{"key":"66_CR18","doi-asserted-by":"publisher","first-page":"2547","DOI":"10.1016\/j.cor.2005.07.028","volume":"33","author":"P. Galinier","year":"2006","unstructured":"Galinier, P., & Hertz, A. (2006). A survey of local search methods for graph coloring. Computers & Operations Research, 33, 2547\u20132562.","journal-title":"Computers & Operations Research"},{"key":"66_CR19","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/j.dam.2006.07.017","volume":"156","author":"P. Galinier","year":"2008","unstructured":"Galinier, P., Hertz, A., & Zufferey, N. (2008). An adaptive memory algorithm for the graph coloring problem. Discrete Applied Mathematics, 156, 267\u2013279","journal-title":"Discrete Applied Mathematics"},{"key":"66_CR20","volume-title":"Computer and intractability: a guide to the theory of np-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., & Johnson, D. S. (1979). Computer and intractability: a guide to the theory of np-completeness. San Francisco: Freeman."},{"key":"66_CR21","unstructured":"Globus, A., Crawford, J., Lohn, J., & Pryor, A. (2003). Scheduling earth observing satellites with evolutionary algorithms. In International conference on space mission challenges for information technology, Pasadena, CA."},{"key":"66_CR22","unstructured":"Globus, A., Crawford, J., Lohn, J., & Pryor, A. (2004). A comparison of techniques for scheduling earth observing satellites. In Proceedings of the sixteenth innovative applications of artificial intelligence conference (IAAI-04)."},{"key":"66_CR23","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"F. Glover","year":"1986","unstructured":"Glover, F. (1986). Future paths for integer programming and linkage to artificial intelligence. Computers & Operations Research, 13, 533\u2013549.","journal-title":"Computers & Operations Research"},{"key":"66_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-6089-0","volume-title":"Tabu search","author":"F. Glover","year":"1997","unstructured":"Glover, F., & Laguna, M. (1997). Tabu search. Boston: Kluwer Academic."},{"key":"66_CR25","unstructured":"Gooley, T. D. (1993). Automating the satellite range scheduling process. M.Phil. thesis, Air Force Institute of Technology, USA."},{"key":"66_CR26","doi-asserted-by":"crossref","unstructured":"Habet, D., & Vasquez, M. (2004). Solving the selecting and scheduling satellite photographs problem with a consistent neighborhood heuristic. In Sixteenth IEEE international conference on tools with artificial intelligence.","DOI":"10.1109\/ICTAI.2004.110"},{"key":"66_CR27","unstructured":"Hansen, P. (1986). The steepest ascent mildest descent heuristic for combinatorial programming. In Congress on numerical methods in combinatorial optimization, Capri, Italy."},{"key":"66_CR28","unstructured":"Harrison, S. A., Philpott, M. S., & Price, M. E. (1999). Task scheduling for satellite based imagery. In Proceedings of the 18th workshop of the UK planning and scheduling special interest group (pp. 64\u201378), University of Salfort, UK."},{"issue":"3","key":"66_CR29","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1057\/palgrave.jors.2600357","volume":"48","author":"A. Hertz","year":"1997","unstructured":"Hertz, A., & Costa, D. (1997). Ants can color graphs. The Journal of the Operational Research Society, 48(3), 295\u2013305.","journal-title":"The Journal of the Operational Research Society"},{"key":"66_CR30","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A. Hertz","year":"1987","unstructured":"Hertz, A., & de Werra, D. (1987). Using Tabu search techniques for graph coloring. Computing, 39, 345\u2013351.","journal-title":"Computing"},{"key":"66_CR31","doi-asserted-by":"crossref","unstructured":"Hertz, A., Plumettaz, M., & Zufferey, N. (2007, accepted). Variable space search for graph coloring. Discrete Applied Mathematics.","DOI":"10.1016\/j.dam.2008.03.022"},{"key":"66_CR32","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/S1270-9638(02)01173-2","volume":"6","author":"M. Lemaitre","year":"2002","unstructured":"Lemaitre, M., Verfaillie, G., Jouhaud, F., Lachiver, J.-M., & Bataille, N. (2002). Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 6, 367\u2013381.","journal-title":"Aerospace Science and Technology"},{"key":"66_CR33","unstructured":"Marinelli, F., Nocella, S., Rossi, F., & Smriglio, S. (2006). A Lagrangian heuristic for satellite range scheduling with resource constraints (Tech. rept. TRCS 004\/2005). Dip. di Informatica, Universit\u00e0 L\u2019Aquila, Italy."},{"key":"66_CR34","unstructured":"Meuwly, F.-X., Ries, B., & Zufferey, N. (2007). Heuristiques pour la coloration de graphes mixtes. Master thesis. Swiss Federal Institute of Technology, EPFL, Lausanne, Switzerland."},{"key":"66_CR35","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N. Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24, 1097\u20131100.","journal-title":"Computers & Operations Research"},{"key":"66_CR36","doi-asserted-by":"publisher","first-page":"2419","DOI":"10.1016\/j.cor.2004.03.010","volume":"32","author":"N. Mladenovi\u0107","year":"2005","unstructured":"Mladenovi\u0107, N., Plastria, F., & Uro\u0161evi\u0107, D. (2005). Reformulation descent applied to circle packing problems. Computers & Operations Research, 32, 2419\u20132434.","journal-title":"Computers & Operations Research"},{"key":"66_CR37","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1090\/dimacs\/026\/16","volume":"26","author":"C. Morgenstern","year":"1996","unstructured":"Morgenstern, C. (1996). Distributed coloration neighborhood search. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, 335\u2013357.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"66_CR38","unstructured":"Parish, D. A. (1994). A genetic algorithm approach to automating satellite range scheduling. M.Phil. thesis, Air Force Institute of Technology, USA."},{"key":"66_CR39","unstructured":"Pemberton, J. C. (2000). Toward scheduling over-constrained remote-sensing satellites. In Proceedings of the second NASA international workshop on planning and scheduling for space."},{"key":"66_CR40","volume-title":"Scheduling: theory, algorithms, and systems","author":"M. Pinedo","year":"2002","unstructured":"Pinedo, M. (2002). Scheduling: theory, algorithms, and systems. New York: Prentice Hall."},{"key":"66_CR41","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF02430370","volume":"1","author":"Y. Rochat","year":"1995","unstructured":"Rochat, Y., & Taillard, E. (1995). Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1, 147\u2013167.","journal-title":"Journal of Heuristics"},{"key":"66_CR42","unstructured":"Schlack, S. M. (1993). Automating satellite range scheduling. M.Phil. thesis, Air Force Institute of Technology, USA."},{"key":"66_CR43","first-page":"502","volume-title":"Proceedings of the 4th international conference on genetic algorithms","author":"G. Syswerda","year":"1991","unstructured":"Syswerda, G., & Palmucci, J. (1991). The application of genetic algorithms to resource scheduling. In Proceedings of the 4th international conference on genetic algorithms (pp. 502\u2013508). San Mateo: Morgan Kaufmann."},{"key":"66_CR44","first-page":"87","volume":"7","author":"M. Vasquez","year":"2003","unstructured":"Vasquez, M., & Hao, J.-K. (2003). A \u201clogic-constrained\u201d knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite. Computational Optimization and Applications, 7, 87\u2013103.","journal-title":"Computational Optimization and Applications"},{"key":"66_CR45","unstructured":"Verfaillie, G., & Lemaitre, M. (2001). Selecting and scheduling observations for agile satellites: some lessons from the contraint programming community point of view. In T. Walsh (Ed.), Principles and practice of constraint programming (pp. 670\u2013684)."},{"key":"66_CR46","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1287\/mnsc.46.1.148.15134","volume":"46","author":"W. J. Wolfe","year":"2000","unstructured":"Wolfe, W. J., & Sorensen, S. E. (2000). Three scheduling algorithms applied to the earth observing systems domain. Management Science, 46, 148\u2013168.","journal-title":"Management Science"},{"key":"66_CR47","unstructured":"Zufferey, N. (2002). Heuristiques pour les probl\u00e8mes de la coloration des sommets d\u2019un graphe et d\u2019affectation de fr\u00e9quences avec polarit\u00e9s. Ph.D. thesis, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-008-0066-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-008-0066-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-008-0066-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-008-0066-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T09:39:41Z","timestamp":1559468381000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-008-0066-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["66"],"URL":"https:\/\/doi.org\/10.1007\/s10951-008-0066-8","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}