Abstract: In this paper, we assume the using cost of machines cost is fixedand study the uniform parallel machine scheduling problem considering the using cost of machines. The goal is to minimize the maximum lateness whose total cost does not exceed a given budget. A mixed integer programming model is established for this problem. To minimize the maximum lateness, we design the rule to select suitable machines in all the machines. Then we propose an improvement of the traditional LPT(Longest Processing Time First)algorithm, ECT(Earliest Completion Time First) algorithm,and EDD(Earliest Due Date First) algorithm. A heuristic algorithm named H is designed. The worst error bounds of the algorithm under parallel machine and uniform parallel machine are also analyzed theoretically. By giving two examples, we illustrate the implementation of the algorithm. Finally, a variety of total cost budgets are considered and the effectiveness of the algorithm is verified by a large number of random data experiments.

Key words: uniform parallel machine, cost of machines, maximal lateness

摘要： 假定生产时机器成本是固定的,研究了一类考虑成本的同类机调度问题,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。为该类问题构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法H,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。

关键词: 同类机, 机器成本, 最大延迟时间