×

Minimizing total completion time on parallel machines with deadline constraints. (English) Zbl 1052.90034

Summary: Consider \(n\) independent jobs and \(m\) identical machines in parallel. Job \(j\) has a processing time \(p_{j}\) and a deadline \(\overline{d}_j\). It must complete its processing before or at its deadline. All jobs are available for processing at time \(t=0\) and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines; such a schedule is called a feasible schedule. Given a feasible set of jobs, our goal is to find a schedule that minimizes the total completion time \(\sum C_j\). In the classical \(\alpha | \beta | \gamma\) scheduling notation this problem is referred to as \(P | \operatorname{prm}t, \overline{d}_j | \sum C_j\).
E. L. Lawler [in: Mathematical Programming: The State of the Art, A. Bachem, et al. (eds.), Bonn 1982, Springer, Berlin, 202–234 (1982; Zbl 0547.90042)] raised the question of whether or not the problem is NP-hard. In this paper we present a polynomial-time algorithm for every \(m \geq 2\), and we show that the more general problem with \(m\) unrelated machines, i.e., \(R | \operatorname{prm}t, \overline{d}_j | \sum C_j\), is strongly NP-hard.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C60 Abstract computational complexity for mathematical programming problems

Citations:

Zbl 0547.90042
PDFBibTeX XMLCite
Full Text: DOI