The DOI matches its Crossref record; 97 of the 97 references it cites were found in a registry or an index.
Three Scheduling Algorithms Applied to the Earth Observing Systems Domain
Abstract
This paper describes three approaches to assigning tasks to earth observing satellites (EOS). A fast and simple priority dispatch method is described and shown to produce acceptable schedules most of the time. A look ahead algorithm is then introduced that outperforms the dispatcher by about 12% with only a small increase in run time. These algorithms set the stage for the introduction of a genetic algorithm that uses job permutations as the population. The genetic approach presented here is novel in that it uses two additional binary variables, one to allow the dispatcher to occasionally skip a job in the queue and another to allow the dispatcher to occasionally allocate the worst position to the job. These variables are included in the recombination step in a natural way. The resulting schedules improve on the look ahead by as much as 15% at times and 3% on average. We define and use the “window-constrained packing” problem to model the bare bones of the EOS scheduling problem.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Genetic algorithms in search, optimization, and machine learning
(1989) · Choice Reviews Online · doi:10.5860/choice.27-0936 · Cited by 49,010
(1979) · Cited by 43,841
Genetic Algorithms in Search, Optimization and Machine Learning
Goldberg, D. E., & Robson, D. (1988) · Cited by 18,391
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70356-x · Cited by 5,854
Glover, F. (1990) · ORSA Journal on Computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,647
A machine program for theorem-proving
Davis, M., Logemann, G., & Loveland, D. (1962) · Communications of the ACM · doi:10.1145/368273.368557 · Cited by 3,220
Benchmarks for basic scheduling problems
Taillard, É. D. (1993) · European Journal of Operational Research · doi:10.1016/0377-2217(93)90182-m · Cited by 2,489
Local Search in Combinatorial Optimization
(2003) · Princeton University Press eBooks · doi:10.1515/9780691187563 · Cited by 2,057
de Kleer, J., & Williams, B. C. (1987) · Artificial Intelligence · doi:10.1016/0004-3702(87)90063-4 · Cited by 2,039
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,882
The Shifting Bottleneck Procedure for Job Shop Scheduling
Adams, J., Balas, E., & Zawack, D. J. (1988) · Management Science · doi:10.1287/mnsc.34.3.391 · Cited by 1,603
New methods to color the vertices of a graph
Brélaz, D. (1979) · Communications of the ACM · doi:10.1145/359094.359101 · Cited by 1,567
GRASP: a search algorithm for propositional satisfiability
Marques-Silva, J. P., & Sakallah, K. A. (1999) · IEEE Transactions on Computers · doi:10.1109/12.769433 · Cited by 1,374
Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
Shaw, P. (1998) · Lecture Notes in Computer Science · doi:10.1007/3-540-49481-2_30 · Cited by 1,366
Constraint logic programming: a survey
Jaffar, J., & Maher, M. J. (1994) · The Journal of Logic Programming · doi:10.1016/0743-1066(94)90033-7 · Cited by 1,312
A new method for solving hard satisfiability problems
Selman, B., Levesque, H. J., & Mitchell, D. G. M. (1992) · Cited by 1,156
Job Shop Scheduling by Simulated Annealing
van Laarhoven, P. J. M., Aarts, E. H. L., & Lenstra, J. K. (1992) · Operations Research · doi:10.1287/opre.40.1.113 · Cited by 1,123
Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop
Rand, G. K., & French, S. D. (1982) · Journal of the Operational Research Society · doi:10.1057/jors.1982.184 · Cited by 1,047
A Fast Taboo Search Algorithm for the Job Shop Problem
Nowicki, E., & Smutnicki, C. (1996) · Management Science · doi:10.1287/mnsc.42.6.797 · Cited by 976
Diagnostic reasoning based on structure and behavior
Davis, R. (1984) · Artificial Intelligence · doi:10.1016/0004-3702(84)90042-0 · Cited by 966
A Computational Study of the Job-Shop Scheduling Problem
Applegate, D., & Cook, W. (1991) · ORSA Journal on Computing · doi:10.1287/ijoc.3.2.149 · Cited by 908
Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems
Minton, S., Johnston, M. D., Philips, A. B., & Laird, P. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90007-k · Cited by 843
Pushing the envelope: planning, propositional logic, and stochastic search
Kautz, H., & Selman, B. (1996) · Cited by 830
An Algorithm for Solving the Job-Shop Problem
Carlier, J., & Pinson, É. (1989) · Management Science · doi:10.1287/mnsc.35.2.164 · Cited by 824
Noise strategies for improving local search
Selman, B., Kautz, H., & Cohen, B. (1994) · Cited by 757
Symbolic model checking using SAT procedures instead of BDDs
Biere, A., Cimatti, A., Clarke, E. M., Fujita, M., & Zhu, Y. (1999) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/309847.309942 · Cited by 752
Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules
Fisher, H. F. (1963) · Medical Entomology and Zoology · Cited by 729
Stallman, R. M., & Sussman, G. J. (1977) · Artificial Intelligence · doi:10.1016/0004-3702(77)90029-7 · Cited by 712
Zweben, M., & Fox, M. S. (1998) · Cited by 620
Mackworth, A. K., & Freuder, E. C. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90041-4 · Cited by 619
Applying tabu search to the job-shop scheduling problem
Dell’Amico, M., & Trubian, M. (1993) · Annals of Operations Research · doi:10.1007/bf02023076 · Cited by 603
Using CSP look-back techniques to solve real-world SAT instances
Bayardo, R. J., & Schrag, R. C. (1997) · Cited by 592
Valued constraint satisfaction problems : hard and easy problems
Schiex, T., Fargier, H., & Verfaillie, G. (1995) · Cited by 566
Boosting combinatorial search through randomization
Gomes, C. P., Selman, B., & Kautz, H. (1998) · Cited by 557
Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator
Whitley, L. D., Starkweather, T., & Fuquay, D. (1989) · international conference on Genetic algorithms · Cited by 551
The use of design descriptions in automated diagnosis
Genesereth, M. R. (1984) · Artificial Intelligence · doi:10.1016/0004-3702(84)90043-2 · Cited by 533
The one-machine sequencing problem
Carlier, J. (1982) · European Journal of Operational Research · doi:10.1016/s0377-2217(82)80007-6 · Cited by 528
HYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEM
Prosser, P. (1993) · Computational Intelligence · doi:10.1111/j.1467-8640.1993.tb00310.x · Cited by 528
Dave, U. (1995) · Journal of the Operational Research Society · doi:10.1057/jors.1995.75 · Cited by 517
Local search strategies for satisfiability testing
Selman, B., Kautz, H., & Cohen, B. (1996) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/026/25 · Cited by 516
Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition
Dechter, R. (1990) · Artificial Intelligence · doi:10.1016/0004-3702(90)90046-3 · Cited by 497
Ginsberg, M. L. (1993) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1 · Cited by 456
Dean, T., & Wellman, M. P. (1991) · Cited by 451
Short proofs are narrow—resolution made simple
Ben‐Sasson, E., & Wigderson, A. (2001) · Journal of the ACM · doi:10.1145/375827.375835 · Cited by 422
Guided Local Search with Shifting Bottleneck for Job Shop Scheduling
Balas, E., & Vazacopoulos, A. (1998) · Management Science · doi:10.1287/mnsc.44.2.262 · Cited by 407
Contradicting conventional wisdom in constraint satisfaction
Sabin, D., & Freuder, E. C. (1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-58601-6_86 · Cited by 387
Evidence for invariants in local search
McAllester, D., Selman, B., & Kautz, H. (1997) · Cited by 365
Combinational test generation using satisfiability
Stephan, P., Brayton, R. K., & Sangiovanni-Vincentelli, A. L. (1996) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.536723 · Cited by 326
Heuristics based on unit propagation for satisfiability problems
Li, C.-M., & Anbulagan, A. (1997) · Cited by 319
Domain-independent extensions to GSAT: solving large structured satisfiability problems
Selman, B., & Kautz, H. (1993) · Cited by 291
Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method
Minton, S., Johnston, M., Philips, A. B., & Laird, P. D. (1990) · National Conference on Artificial Intelligence · Cited by 278
Improvements to propositional satisfiability search algorithms
Freeman, J. (1995) · Cited by 265
Vasquez, M., & Hao, J.-K. (2001) · Computational Optimization and Applications · doi:10.1023/a:1011203002719 · Cited by 239
Job shop scheduling by local search
Aarts, E. E., Lenstra, J. J. K., Laarhoven, P. P. V., & Ulder, N. N. (1992) · TU/e Research Portal · Cited by 232
Squeaky Wheel OptimizationPreprint
Clements, D. P., & Joslin, D. E. (2011) · arXiv (Cornell University) · doi:10.1613/jair.561 · Cited by 221
An Efficient Propositional Prover
Zhang, H. (1997) · Cited by 196
Local search with constraint propagation and conflict-based heuristics
Jussien, N., & Lhomme, O. (2002) · Artificial Intelligence · doi:10.1016/s0004-3702(02)00221-7 · Cited by 184
Solution Reuse in Dynamic Constraint Satisfaction Problems
Verfaillie, G., & Schiex, T. (1994) · Cited by 175
Pape, C. L. (1994) · Intelligent Systems Engineering · doi:10.1049/ise.1994.0009 · Cited by 172
Automatic SAT-compilation of planning problems
Ernst, M. D., Millstein, T. D., & Weld, D. S. (1997) · Cited by 168
Russian doll search for solving constraint optimization problems
Verfaillie, G., Lemaı̂tre, M., & Schiex, T. (1996) · Cited by 164
Sequencing by enumerative methods
Lenstra, J. K. (1977) · Data Archiving and Networked Services (DANS) · Cited by 164
The Application of Genetic Algorithms to Resource Scheduling
Syswerda, G., & Palmucci, J. (1991) · Medical Entomology and Zoology · Cited by 159
Scheduling problems and traveling salesman: the genetic edge recombination
Whitley, D., Starkweather, T., & Fuquay, D. (1989) · international conference on Genetic algorithms · Cited by 152
Short proofs for tricky formulas
Krishnamurthy, B. (1985) · Acta Informatica · doi:10.1007/bf00265682 · Cited by 148
A block approach for single-machine scheduling with release dates and due dates
Grabowski, J., Nowicki, E., & Zdrzałka, S. (1986) · European Journal of Operational Research · doi:10.1016/0377-2217(86)90191-8 · Cited by 148
Strategic directions in constraint programming
Hentenryck, P. V., & Saraswat, V. (1996) · CSUR · doi:10.1145/242223.242279 · Cited by 145
Maximizing the value of a space mission
Hall, N. G., & Magazine, M. J. (1994) · European Journal of Operational Research · doi:10.1016/0377-2217(94)90385-9 · Cited by 138
On the parallel complexity of discrete relaxation in constraint satisfaction networks
Kasif, S. (1990) · Artificial Intelligence · doi:10.1016/0004-3702(90)90009-o · Cited by 131
Ginsberg, M. L., & McAllester, D. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58601-6_105 · Cited by 122
Applying constraint satisfaction techniques to job shop scheduling
Cheng, C., & Smith, S. F. (1997) · Annals of Operations Research · doi:10.1023/a:1018934507395 · Cited by 97
Gabrel, V., Moulet, A., Murat, C., & Paschos, V. T. (1997) · Annals of Operations Research · doi:10.1023/a:1018920709696 · Cited by 96
Systematic and Nonsystematic Search Strategies
Langley, P. (1992) · Elsevier eBooks · doi:10.1016/b978-0-08-049944-4.50022-7 · Cited by 96
A view of local search in constraint programming
Pesant, G., & Michel Gendreau, A. (1996) · Lecture notes in computer science · doi:10.1007/3-540-61551-2_86 · Cited by 95
Managing genetic search in job shop scheduling
Uckun, S., Bagchi, S., Kawamura, K., & Miyabe, Y. (1993) · IEEE Expert · doi:10.1109/64.236477 · Cited by 94
Wu, Z., & Wah, B. W.-S. (2000) · Cited by 88
Weak-commitment search for solving constraint satisfaction problems
Yokoo, M. (1994) · National Conference on Artificial Intelligence · Cited by 86
Kunz, W., & Stoffel, D. (1997) · Frontiers in electronic testing · doi:10.1007/978-1-4757-2572-8 · Cited by 83
Micro-Opportunistic Scheduling: The Micro-Boss Factory Scheduler
Sadeh, N. (1994) · doi:10.21236/ada282968 · Cited by 79
Local search and the number of solutions
Clark, D. A., Frank, J., Gent, I. P., MacIntyre, E., Tomov, N., & Walsh, T. (1996) · Lecture notes in computer science · doi:10.1007/3-540-61551-2_70 · Cited by 78
Nonsystematic backtracking search
Harvey, W. D. (1995) · Cited by 77
A sharp threshold in proof complexity
Achlioptas, D., Beame, P. W., & Molloy, M. S. O. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380820 · Cited by 77
Profile-based algorithms to solve multiple capacitated metric scheduling problems
Cesta, A., Oddi, A., & Smith, S. F. (1998) · Cited by 74
Near-Optimal Separation of Treelike and General Resolution
Ben‐Sasson, E., Impagliazzo, R., & Wigderson, A. (2000) · Cited by 68
Systematic versus stochastic constraint satisfaction
Freuder, E. C., Dechter, R., Ginsberg, M. L., Selman, B., & Tsang, E. P. K. (1995) · International Joint Conference on Artificial Intelligence · Cited by 68
Solving non-Boolean satisfiability problems with stochastic local search
Frisch, A. M., & Peugniez, T. J. (2001) · Cited by 61
Iterative Flattening: A Scalable Method for Solving Multi-Capacity Scheduling Problems
Cesta, A., Oddi, A., & Smith, S. F. (2000) · Cited by 61
Task Scheduling for Satellite Based Imagery
Harrison, S., & Philpott, M. (1999) · Cited by 58
Stochastic procedures for generating feasible schedules
Oddi, A., & Smith, S. F. (1997) · Cited by 57
A study of proof search algorithms for resolution and polynomial calculus
Bonet, M. L., & Galesi, N. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814614 · Cited by 56
The hazards of fancy backtracking
Baker, A. B. (1994) · Cited by 53
Exploiting a common property resource under a fairness constraint: a case study
Lemaître, M., Verfaillie, G., & Bataille, N. (1999) · Cited by 45
Verfaillie, G., & Lemaı̂tre, M. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45578-7_55 · Cited by 39
Combining local search and backtracking techniques for constraint satisfaction
Zhang, J., & Zhang, H. (1996) · National Conference on Artificial Intelligence · Cited by 36
DEALING WITH UNCERTAINTY WHEN MANAGING AN EARTH OBSERVATION SATELLITE
Bensana, E., Verfaillie, G., Michelon-Edery, C., & Bataille, N. (1999) · Cited by 34
Three mechanisms for managing resource constraints in a library for constraint-based scheduling
Pape, C. L. (1995) · doi:10.1109/etfa.1995.496781 · Cited by 25
Optimizing Observation Scheduling Objectives
Bresina, J. L., Morris, R. A., & Edgington, W. (1997) · NASA Technical Reports Server (NASA) · Cited by 13
Research works printed but not linked: 8
- Asrar G., 1994, EOS science strategy for the earth observing system
- 10.2514/6.1989-3137 · doi:10.2514/6.1989-3137
- Garey M., 1979, Computers and Intractability
- Johnson M. D., 1994, Intelligent Scheduling
- Muscettola N., 1994, Intelligent Scheduling
- Short N., et al. Notes for the workshop for planning and scheduling of earth science data processing (1995) May(NASA Goddard SFC Conference on Space Applications of AI)8–9
- Uckun S., 1993, IEEE Expert
- Zweben M., 1994, Intelligent Scheduling
Cited by
Chaff: engineering an efficient SAT solver
Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S. (2001) · Proceedings of the 38th conference on Design automation - DAC '01 · doi:10.1145/378239.379017 · Cited by 2,940
Selecting and scheduling observations of agile satellites
Lemaı̂tre, M., Verfaillie, G., Jouhaud, F., Lachiver, J.-M., & Bataille, N. (2002) · Aerospace Science and Technology · doi:10.1016/s1270-9638(02)01173-2 · Cited by 472
Bianchessi, N., Cordeau, J.-F., Desrosiers, J., Laporte, G., & Raymond, V. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.12.026 · Cited by 252
Liu, X., Laporte, G., Chen, Y., & He, R. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.04.006 · Cited by 250
Scheduling Space–Ground Communications for the Air Force Satellite Control Network
Barbulescu, L., Watson, J.-P., Whitley, L. D., & Howe, A. E. (2004) · Journal of Scheduling · doi:10.1023/b:josh.0000013053.32600.3c · Cited by 232
Metadata
- Authors
- Wolfe, W. J., & Sorensen, S. E.
- Venue
- Management Science
- Published
- 2000-01
- Volume
- 46
- Issue
- 1
- Pages
- 148-166
- ISSN
- 0025-1909 (ISSN-L)
- 1526-5501
- OpenAlex
- W2148027993
- Cited by
- 313
- References
- 97
- FWCI
- 25.73
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.