Algorithms for Some Maximization Scheduling Problems on a Single Machine

作者：Gafarov E R^*; Lazarev A A; Werner F

来源：Automation and Remote Control, 2010, 71(10): 2070-2084.

DOI：10.1134/S0005117910100061

In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1aEuro-max-I T pound (j) and for the problem of maximizing the number of tardy jobs 1aEuro-maxI U pound (j) . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1aEuro-max-I T pound (j) is polynomially solvable. For several special cases of problem 1aEuro-maxI T pound (j) , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.

• 出版日期2010-10