Abstract We propose a related machine scheduling problem in which the processing times of jobs are given and known, but the speeds of machines are variables and must satisfy a system of linear constraints. The objective is to decide the speeds of machines and minimize the makespan of the schedule among all the feasible choices. The problem is motivated by some practical application scenarios. This problem is strongly NP-hard in general, and we discuss various cases of it. In particular, we obtain polynomial time algorithms for two special cases. If the number of constraints is more than one and the number of machines is a fixed constant, then we give a (2+ϵ)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$(2+epsilon )$$end{document}-approximation algorithm. For the case where the number of machines is an input of the problem instance, we propose several approximation algorithms, and obtain a polynomial time approximation scheme when the number of distinct machine speeds is a fixed constant.
展开▼
