Position Assignment on an Enterprise Level Using Combinatorial Optimization

Leonard Kinnaird-Heether, Chris DormanAAAI 2015 · DOI

TL;DR

This paper introduces a combinatorial optimization tool developed at Ford Motor Company to address the complex challenge of assigning new graduate employees to various positions within their rotational programs. By leveraging the Hungarian algorithm, the tool ensures fair and efficient assignments based on employee preferences and program guidelines, improving upon manual methods and previous software solutions.

What Problem Does This Paper Address?

Large corporations often employ rotational programs, like Ford's Ford College Graduate (FCG) program, to provide new hires with diverse experiences and networking opportunities. A significant challenge in administering these programs is equitably assigning participants to available positions, especially when more employees are interested in certain roles than there are openings. Manual assignment becomes infeasible as program size grows, and previous software solutions had limitations. The authors tackle the problem of creating a fair and efficient system for assigning participants to positions that balances employee preferences with organizational needs and program constraints.

Methods

The core of the solution is a combinatorial optimization approach, specifically utilizing the Hungarian algorithm (also known as the Kuhn-Munkres algorithm). This algorithm is well-suited for solving the assignment problem, which aims to find a one-to-one matching between two sets (in this case, participants and positions) to optimize a given objective function.

The process involves:

  1. Data Collection: Supervisors submit available positions with descriptions, and participants rank their preferred positions.
  2. Preference Weighting: A "weight function" is applied to the raw preference data. This function assigns a numerical score based on the participant's ranking of a position and their seniority level within the program. Higher rankings and greater seniority contribute to higher weights.
  3. Weight Matrix Creation: The weighted preferences are organized into a matrix where rows represent participants and columns represent positions.
  4. Optimization: The Hungarian algorithm is applied to this weight matrix to find the assignment that maximizes the sum of the weights (representing overall participant satisfaction).
  5. Bias Mitigation: To prevent bias in the algorithm's selection when multiple optimal solutions exist, the order of participants is randomized before running the algorithm.
  6. Flexibility: The system is designed modularly, allowing for different optimization algorithms to be used in the future if needed. For positions with multiple openings, additional columns are created in the weight matrix to represent each available slot.

Datasets

The paper does not introduce new datasets. Instead, it uses historical data from Ford Motor Company's IT FCG program and other internal programs (IT Summer Intern program, Ford Finance College Foundational Program - CFP) for evaluation. The data consists of:

  • Participant population numbers.
  • Number of available positions.
  • Participant preference rankings for positions.
  • Supervisor-submitted position details.
  • Satisfaction ratings derived from the assignment outcomes.

Key Insights and Ideas

  • Combinatorial Optimization as a Solution: The paper demonstrates that a well-established mathematical technique like combinatorial optimization can effectively solve complex, real-world enterprise problems like employee assignment, moving beyond ad-hoc or manual methods.
  • Balancing Preferences and Constraints: The system successfully balances individual employee preferences with program-specific guidelines (e.g., encouraging exploration of different roles based on seniority) and organizational needs.
  • The "Fairness" Challenge: The core problem is framed as achieving an "egalitarian" or fair assignment, which the weighted preference system and optimization algorithm aim to deliver.
  • Limitations of Simple Ratios: The authors found that a simple position-to-participant ratio isn't a strong predictor of satisfaction. Instead, the "effective positions count" (positions with actual interest) and the "effective position-participant ratio" provide better insights.
  • The "Gaming" Problem: The paper acknowledges that participants might try to "game" the system through social engineering (e.g., ranking all choices in a popular group) or by strategically taking less desirable roles early on to gain an advantage later.

Key Results

  • The developed position assignment tool has been in active use since 2012 for the IT FCG program and has successfully completed assignments annually.
  • The tool has maintained a high level of participant satisfaction, with satisfaction ratings generally above 77% for the FCG program and varying for other programs.
  • The system has been adapted for other programs like the IT Summer Intern program and the Ford Finance College Foundational Program (CFP), demonstrating its versatility.
  • The tool's performance metrics (satisfaction ratings, first/second choice percentages) are tracked and presented to a development committee for review.

Limitations and Future Work

  • Satisfaction Decline: The paper notes a decline in satisfaction ratings for the IT FCG and Summer Intern programs, which is attributed to increased program membership and decreased position availability, leading to more competition for desirable roles, rather than a failure of the assignment tool itself.
  • Scalability Concerns: The current implementation of the Hungarian algorithm is single-threaded, and the authors express concern about its ability to handle potential future increases in program size and position numbers without performance degradation.
  • Potential for "Gaming": The paper acknowledges that participants might attempt to influence assignment outcomes through strategic choices or social engineering, and this is an area for future research.
  • Collusion: The possibility of collusion between individuals to influence assignments is also identified as an area for future investigation.
  • Exploring Alternative Algorithms: The authors suggest exploring other optimization techniques, such as genetic algorithms or cultural algorithms, which might offer different advantages or handle larger-scale problems more efficiently.
  • User Equilibrium: Investigating concepts from user equilibrium in traffic management could potentially offer insights into how to better manage resource sharing and participant contentment.

Summary updated

BibTeX
@inproceedings{kinnairdheether2015position,
  author = {Leonard Kinnaird-Heether and Chris Dorman},
  title = {{Position Assignment on an Enterprise Level Using Combinatorial Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i2.19046},
}
Figure