Abstract: The scheduling of multiple concurrent projects that shares and competes for limited resources with uncertain activity durations is common in mold manufacturing practices,and there is still a lack of effective methods for this type of problem until now.By addressing the mold project scheduling problem with partial activity durations that followed a given discrete probability distribution,the mathematical model was constructed based on a Markov Decision Processes (MDPs),whose objective was to minimize the expected total weighed tardiness costs.To deal with the curse of dimensionality when solve an optimal policy of large-scale instance by traditional dynamic programming,the approximate approaches based on classical priority rules,genetic algorithm (GA) and Approximate Dynamic Programming (ADP) were proposed respectively.The constructed model and methods were validated by a random generated project instances.The experimental results showed that the proposed approximate methods could obtain the acceptable suboptimal or even an optimal result with a small computational cost,which had the ability to solve practical problems.

Key words: mold, project scheduling, discrete durations, Markov decision processes, approximate dynamic programming, priority rules

摘要： 模具制造工程中普遍存在任务工期不确定,以及多并行项目共享和竞争企业有限资源的情形,目前尚缺乏求解这类项目调度问题的方法。鉴于此,考虑了部分任务工期服从已知离散分布下的模具项目调度问题,基于马尔可夫决策过程理论构建了以总加权拖期成本期望最小为优化目标的数学模型。针对传统随机动态规划在求解大规模问题时面临的维数灾,分别提出了基于经典优先规则、遗传算法和近似动态规划的求解方法。通过随机生成的项目算例验证了所构建模型和方法的有效性。结果表明,所提近似方法能够在耗费较少计算资源的情形下获得可接受的次优或最优解,可用于求解工程实际问题。

关键词: 模具, 项目调度, 离散工期, 马尔可夫决策过程, 近似动态规划, 优先规则