Improvements of constraint programming and hybrid methods for scheduling of tests on vehicle prototypes
Tóm tắt
In the automotive industry, a manufacturer must perform several hundreds of tests on prototypes of a vehicle before starting its mass production. Tests must be allocated to suitable prototypes and ordered to satisfy temporal constraints and various kinds of test dependencies. The manufacturer aims to minimize the number of prototypes required. We present improvements of constraint programming (CP) and hybrid approaches to effectively solve random instances from an existing benchmark. CP mostly achieves better solutions than the previous heuristic technique and genetic algorithm. We also provide customized search schemes to enhance the performance of general search algorithms. The hybrid approach applies mixed integer linear programming (MILP) to solve the planning part and CP to find the complete schedule. We consider several logical principles such that the MILP model can accurately estimate the prototype demand, while its size particularly for large instances does not exceed memory capacity. Moreover, the robustness is alleviated when we allow CP to partially change the allocation obtained from the MILP model. The hybrid method can contribute to optimal solutions in some instances.
Tài liệu tham khảo
Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based scheduling: Applying constraint programming to scheduling problems. Norwell, MA: Kluwer.
Bartels, J.-H. (2008). Anwendung von Methoden der Ressourcenbeschränkten Projektplanung mit multiplen Ausfü hrungsmodi in der betriebswirtschaftlichen Praxis. PhD thesis, Clausthal University of Technology.
Bartels, J.-H., & Zimmermann, J. (2009). Scheduling tests in automotive R&D projects. European Journal of Operational Research, 193(3), 805–819.
Benini, L., Bertozzi, D., Guerri, A., & Milano, M. (2005). Allocation and scheduling for MPSoCs via decomposition and no-good generation. In Principles and Practice of constraint programming—CP 2005. Lecture notes in computer science (Vol. 3709/2005, pp. 107–121). New York: Springer.
Demeulemeester, E. (1995). Minimizing resource availability costs in time-limited project networks. Management Science, 41(10), 1590–1599.
Hooker, J. (2006). An integrated method for planning and scheduling to minimize tardiness. Constraints, 11(2), 139–157.
Hsu, C. C., & Kim, D. S. (2005). A new heuristic for the multi-mode resource investment problem. Journal of the Operational Research Society, 56(4), 406–413.
ILOG (2006). ILOG CPLEX 10.0 user’s manual. ILOG S.A.
ILOG (2006). ILOG scheduler 6.2 user’s manual. ILOG S.A.
Jain, V., & Grossmann, I. E. (2001). Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS Journal on Computing, 13(4), 258–276.
Junker, U. (2001). Quickxplain: Conflict detection for arbitrary constraint propagation algorithms. In Proceedings of IJCAI’01 Workshop on Modelling and Solving Problems with Constraints.
Le Pape, C., Couronné, P., Vergamini, D., & Gosselin, V. (1994). Time-versus-capacity compromises in project scheduling. In Proceedings of the thirteenth workshop of the UK planning special interest group.
Li, H., & Womer, K. (2009). Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm. Journal of Scheduling, 12(3), 281–298.
Limtanyakul, K. (2009). Scheduling of tests on vehicle prototypes. PhD thesis, Dortmund University of Technology.
Limtanyakul, K., & Schwiegelshohn, U. (2007). Scheduling tests on vehicle prototypes using constraint programming. In Proceedings of the 3rd multidisciplinary international scheduling conference: Theory and applications (pp. 336–343).
Lockledge, J., Mihailidis, D., Sidelko, J., & Chelst, K. (2002). Prototype fleet optimization model. Journal of the Operational Research Society, 53(8), 833–841.
Möhring, R. H. (1984). Minimizing costs of resource requirements in project networks subject to a fixed completion time. Operations Research, 32(1), 89–120.
Neumann, K., & Zimmermann, J. (1999). Resource levelling for projects with schedule-dependent time windows. European Journal of Operational Research, 117(3), 591–605.
Neumann, K., Schwindt, C., & Zimmermann, J. (2003). Project scheduling with time windows and scarce resources: Temporal and resource-constrained project scheduling with regular and nonregular objective functions. New York: Springer.
Nübel, H. (1998). A branch-and-bound procedure for the resource investment problem with generalized precedence constraints. Tech. rep., Institut für Wirtschaftstheorie und Operations Research, University of Karlsruhe.
Pardalos, P. M., & Xue, J. (1994). The maximum clique problem. Journal of Global Optimization, 4(3), 301–328.
Pinedo, M. (2002). Scheduling-theory: Algorithm and systems (2nd ed.). Englewood Cliffs, NJ: Prentice Hall.
Scheffermann, R., Clausen, U., & Preusser, A. (2005). Test-scheduling on vehicle prototypes in the automotive industry. In Proceedings of sixth Asia-Pacific industrial engineering and management systems (APIEMS) (Vol. 11, pp. 1817–1830).
Schwindt, C. (1998). Generation of resource-constrained project scheduling problems subject to temporal constraints. Tech. rep. WIOR-543, Institut für Wirtschaftstheorie und Operations Research, University of Karlsruhe.
van Beck, P. (2006). Backtracking search algorithms. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (pp. 85–134). New York: Elsevier.
Yamashita, D. S., Armentano, V. A., & Laguna, M. (2006). Scatter search for project scheduling with resource availability cost. European Journal of Operational Research, 169(2), 623–637.
Zakarian, A. (2010). A methodology for the performance analysis of product validation and test plans. International Journal of Product Development, 10(4), 369–392.