并行多机提前/拖期调度的启发式算法

Heuristic Algorithms for Parallel Machines Earliness and Tardiness Scheduling

准时制生产模式要求生产任务必须在交货期内完成。实际生产中这一问题受很多约束的影响变得非常复杂。文章针对任务动态到达、任务转换存在的调整时间和交货期、提前 /拖期单位成本各不相同的并行多机上任务排序问题进行了分析 ,设计了一种解决并行多机提前 /拖期调度的启发式近似求解算法。大量实验数据和应用实例充分表明文章所提的启发式算法是有效的。

In just-in-time production, jobs need to be completed as close to their due dates as possible. However, in many real-word situations, the problem is greatly complicated by many constraints. This paper analyses the parallel machines earliness and tardiness scheduling problem with distinct ready times, sequence dependent setup-times, distinct job due date, and distinct earliness and tardiness penalties for each job and develops a heuristic algorithm for an approximate solution. The great number of experiments and application instances show that the algorithm can behave efficiently.