Scheduling unrelated machines with two types of jobs

作者：Vakhania Nodari; Alberto Hernandez Jose; Werner Frank^*

来源：International Journal of Production Research, 2014, 52(13): 3793-3801.

DOI：10.1080/00207543.2014.888789

• scheduling
• unrelated machines
• linear programming
• polynomial-time algorithm
• approximation algorithm
• worst-case analysis

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 p and 2p 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 q for the case of two arbitrary processing times p and q, p < q. 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.

• 出版日期2014