nach oben

Journal of Scheduling

Erschienen in:

01.02.2016

A graph coloring approach to the deployment scheduling and unit assignment problem

verfasst von: Mark Zais, Manuel Laguna

Erschienen in: Journal of Scheduling | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We address one of the external factors of personnel inventory behavior, deployments. The configuration of persistent unit deployments has the ability to affect everything from individual perceptions of service palatability to operational effectiveness. There is little evidence to suggest any analytical underpinnings to the U.S. Army deployment scheduling and unit assignment patterns. This paper shows that the deployment scheduling and unit assignment problem can be formulated as an interval graph such that modifications to traditional graph coloring algorithms provide an efficient mechanism for dealing with multiple objectives.

Vorheriger Artikel A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job

Nächster Artikel A mixed integer programming approach to multi-skilled workforce scheduling

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Unit deployments in persistent conflict range from 9 to 15 months in recent history. It is reasonable to assume a 9-month lower bound since shorter deployments continue to worsen BOG:Dwell ratios and can cause logistics and operations issues that make solutions infeasible in other domains.

Intervals in the graph may have the same endpoints.

Alfares, H. (2004). Survey, categorization, and comparison of recent tour scheduling literature. Annals of Operations Research, 127, 1–4.

Aviles, S. M. (1995). Scheduling Army Deployment to Two Nearly Simultaneous Major Regional Conflicts. Monterey: Naval Postgraduate School.

Baker, K. R. (1976). Workforce allocation in cyclical scheduling problems: a survey. Operational Research Quarterly, 27, 155–167.CrossRef

Blochliger, I. (2004). Scheduling; staff; modeling tutorial, modeling staff scheduling problems. A tutorial. European Journal of Operational Research, 158, 533–542.CrossRef

Bonds, T. M., Baiocchi, D., & McDonald, L. L. (2010). Army Deployments to OIF and OEF. Santa Monica: RAND Corporation.

Cazals, F., & Karande, C. (2008). A note on the problem of reporting maximal cliques. Journal of Theoretical Computer Science, 407, 564–568.CrossRef

Cheng, T. C. E., & Chen, Z.-L. (1994). Parallel-machine scheduling problems with earliness and tardiness penalties. Journal of the Operational Research Society, 645, 685–695.CrossRef

Costa, D., Hertz, A., & Dubuis, C. (1995). Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs. Journal of Heuristics, 1, 105–128.CrossRef

Dabkowski, M., Kwinn, M. J., Miller, K., & Zais, M. (2009). Unit BOG: Dwell...a closed-form approach. Phalanx, 42(4), 11–14.

Department of the Army, AR 525–29: Army Force Generation, March 2011.

Department of the Army, Army Deployment Period Policy, August 2011.

Department of the Army, FM 3-24: Counterinsurgency, December 2006.

Department of the Army, Personnel Policy Guidance for Overseas Contingency Operations, July 2009.

Galinier, P., & Hertz, A. (2006). A survey of local search methods for graph coloring. Computers and Operations Research, 33, 2547–2562.CrossRef

Gamach, M., Hertz, A., & Ouellet, J. O. (2007). A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding. Computers and Operations Research, 34, 2384–2395.CrossRef

Glover, F., & McMillan, C. (1986). The general employee scheduling problem: an integration of MS and AI. Computers and Operations Research, 13, 563–573.CrossRef

Glover, F. (1989). Tabu search - part I. ORSA Journal of Computing, 1, 190–206.CrossRef

Graham, R.L., Lawler, E.L., Lenstra, J.K., & Rinnooy Kan, A.H.G. (1979). Annals of Discrete Mathematics 5: Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey, Hammer, P.L. and Johnson, E.L. and Korte, B.H.. North-Holland Publishing Company.

Hodgson, T. J., Melendez, B., Thoney, K. A., & Trainor, T. (2004). The deployment scheduling anayisis tool (DSAT). Mathematical and Computer Modelling, 39, 905–924.

Hughes, David W., Zais, Mark M., Kucik, Paul, & Huerta, Fernando M. (2011). ARFORGEN BOG: Dwell Simulation. Operations Research Center of Excellence.

Kierstead, H. A. (1988). The linearity of first-fit coloring of interval graphs. Society for Industrial and Applied Mathematics, 1, 526–530.

Kierstead, H. A., & Qin, J. (1995). Coloring interval graphs with first-fit. Discrete Mathematics, 144, 47–57.CrossRef

Kilcullen, D. (2006). Twenty-eight articles: fundamentals of company-level counterinsurgency. Military Review, 86, 50.

Leighton, F. T. (1979). A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards, 84(6), 489–506.CrossRef

Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.CrossRef

Malaguti, E., & Toth, P. (2010). A survey on vertex coloring problems. International Transactions in Operational Research, 17, 1–34.CrossRef

Marler, R. T., & Arora, J. S. (2004). Survey of multi-objective optimization methods for engineering. Structural Multidisciplinary Optimization, 26, 369–395.CrossRef

McKinzie, K., & Barnes, J. W. (2004). A review of strategic mobility models supporting the defense transportation system. Mathematical and Computer Modeling, 39, 839–868.CrossRef

Palubeckis, G. (2008). On the recursive largest first algorithm for graph colouring. International Journal of Computer Mathematics, 85, 191–200.CrossRef

Reed, Heather (2011). Wartime Sourcing: Building Capability and Predictability through Continuity. Military Review, May-June 2011..

Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Boston: Addison Wesley Longman.

Van den Bergh, J., Beliën, J., De Brueker, P., & Demeulemeester, E. (2013). Personnel scheduling: a literature review. European Journal of Operational Research, 226, 367–385.CrossRef

Titel: A graph coloring approach to the deployment scheduling and unit assignment problem
verfasst von: Mark Zais
Manuel Laguna
Publikationsdatum: 01.02.2016
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 1/2016
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0434-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2016

A survey of offline algorithms for energy minimization under deadline constraints

A genetic algorithm for the robust resource leveling problem

A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job

A mixed integer programming approach to multi-skilled workforce scheduling

A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines

MP or not MP: that is the question

Premium Partner