مقاله سال ۲۰۱۶

 مجله امگا – Omega

Ford’s Product Development division is responsible for designing and testing new vehicles and readying them for production. Each vehicle program (e.g., 2015 Ford Fusion, 2016 Ford Escape) progresses through several consecutive stages: concept, design, development and testing, etc., before a new vehicle is manufactured on the assembly line. After the concept and design phases are completed, prototype vehicles are built and subjected to tests to ensure the new vehicle model meets all the design criteria. Each required test needs to be completed by its deadline to ensure adherence to the overall program timing. Test planners and engineers are tasked with scheduling all the tests, placing orders for parts to build the required prototype vehicles, scheduling the order of the builds (e.g., prototype vehicle with automatic transmission on day 1, one with manual transmission on day 2) and assigning the vehicles to departments in charge of tests for different vehicle components, systems, and aspects (e.g., powertrain, electrical, safety).

Each prototype built during the development and testing phases of a vehicle program can cost in excess of $200 K because many of the parts and the prototypes themselves are hand-made and highly customized. Parts needed often require months of lead time, which constrains when prototype vehicle builds can start. That, combined with inflexible deadlines for completion of tests on those vehicles, introduces significant time pressure, an unavoidable and challenging reality associated with maintaining the overall program timing. One way to alleviate time pressure is to build more vehicles, essentially decreasing competition between tests for available vehicle time; however, this would greatly increase the cost of each program. A more efficient way is to develop test plans with tight schedules that combine multiple tests on vehicles to maximally utilize available time. There are many challenges that need to be overcome in implementing this approach. For example, many tests are destructive (e.g., crash tests performed by the safety department), preventing scheduling further tests on the vehicle. Another complicating factor is that different tests may have different vehicle specification requirements; for example, one test may require a hybrid engine whereas another may require a conventional 4-cylinder I4 engine, prohibiting combinations of these tests on the same vehicle.

Prior to our work, test plans were exclusively developed manually using pen and paper and Excel spreadsheets. However, this process is tedious and constructing a test plan may take days, if not weeks. The schedule achieved may not be optimal in terms of the number of vehicles needed; moreover, when changes occur to deadlines and individual tests, manually editing the plan requires significant additional time and effort, and may lead to decreasing vehicle utilization. In this paper, we formally define the problem of obtaining optimized schedules (i.e., ones that minimize the number of vehicles used subject to all pertinent constraints) and introduce computational heuristics that replace the tedious manual scheduling process engineers undertake for each program. Automation saves test planners’ and engineers’ time, increases their ability to quickly react to program changes, and saves resources by providing schedules with high vehicle utilization. In this paper, we describe the development and piloting of our schedule optimization models. We introduce the details of the scheduling problem, then provide an exact mathematical formulation, which turns out to have limited tractability. This leads to our practical heuristic algorithm that provides good feasible schedules. We present results from our first pilot and discuss ongoing efforts and goals of this project.