Top

Journal of Scheduling

Published in:

01-02-2016

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

Authors: Mark Zais, Manuel Laguna

Published in: Journal of Scheduling | Issue 1/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

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

next article A mixed integer programming approach to multi-skilled workforce scheduling

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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

Title: A graph coloring approach to the deployment scheduling and unit assignment problem
Authors: Mark Zais
Manuel Laguna
Publication date: 01-02-2016
Publisher: Springer US
Published in: Journal of Scheduling / Issue 1/2016
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0434-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2016

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

Journal of Scheduling (2016)

A genetic algorithm for the robust resource leveling problem

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

MP or not MP: that is the question

A mixed integer programming approach to multi-skilled workforce scheduling

Premium Partner