约束规划求解原型样车测试排程问题

Scheduling of tests on vehicle prototypes using constraint programming

针对新车型研发阶段原型样车测试排程问题,考虑原型样车可用性、测试优先顺序和资源能力等方面的约束,首先建立一个简化的混合整数线性规划(MILP)模型,确定所需原型样车数目的一个估计值;然后再以该估计值作为输入参数,以实现最大完工时间最小化为目标,建立约束规划(CP)模型,并以甘特图的形式给出排程方案。借助于CPLEX Optimization Studio软件进行实例求解,结果表明:MILP模型在合理的时间范围内可以找出所需原型样车数目的一个有效估计值;同时证实了CP模型在原型样车测试具体排程问题中的可行性和有效性。

In view of all kinds of constraints, such as the availability of vehicle prototypes, capacity of constraint resource, preced- ence constraints, applies Mixed Integer Linear Programming（MILP） and Constraint Programming （CP） to adderess a problem in the automobile industry where lots of tests must be performed on prototypes of a vehicle before starting its mass production. The objective of MILP model is to estimate the number of required prototypes and CP model aims to minimize the makespan. This study shows the scheme by the Gantt chart. The paper used CPLEX Optimization Studio to formulate and solve two models. The result fully proves that MILP easily find the estimate value and constraint programming technology has the superiority and effec- tiveness as scheduling problem.