IFAC Symposium on Information Control Problems in Manufacturing (2009)
In this paper we consider the minimizing total weightedcompletion time in preemptive equal job length schedulingproblem on a single machine. We propose a polynomialtime algorithm that solves the problem. Before this paper the problem were known to be open.
For single and multi-machine scheduling problems with the criterion of minimization maximum lateness the metrics \rho has been used for the first time. A theorem of estimating the absolute error has been proved. The idea of the offered approach consists in construction by an initial instance of a problem of other instance for which it is possible to find the optimum or approximated solution, with the minimal distance up to an initial instance in entered metric.
We consider some special cases of the NP-hard resource-constrained projects cheduling problem (RCPSP) to minimize the makespan. We show that a well-known lowerbounds for the problem may yield bad approximation ratios or its calculation is an NP-hardproblem too. We conjecture that the ratio of the optimal makespan of RCPSP to that of the preemptive version of the problem is less than 2. We also provide some new estimates of the optimal makespan of RCPSP.