Scheduling unrelated machines with two types of jobs
研究在非关联并行机上调度只有两种加工时间的作业，以最小化最大完工时间，提出一个两阶段精确算法和一个近似算法，适用于生产两种产品的场景。
In this paper, we consider the problem of scheduling a set of jobs having only two possible processing times on a set of unrelated parallel machines. This problem is a generalisation of the much more common problem of scheduling equal-length jobs on identical machines. Such a situation may occur in the production of two different types of products. First, we show that an earlier open problem of scheduling jobs with two possible processing times and on unrelated machines with the objective to minimise the makespan can be polynomially solved by an algorithm consisting of two phases. A slight modification of this algorithm yields an absolute worst-case error of for the case of two arbitrary processing times and , . Thus, for practical problems of a large size with two types of products and two possible processing times, the approximation algorithm generates schedules very close to an optimal one.