Kubale, Marek; Ocetkiewicz, Krzysztof M. A new optimal algorithm for a time-dependent scheduling problem. (English) Zbl 1301.93064 Control Cybern. 38, No. 3, 713-721 (2009). Summary: A single machine time-dependent scheduling problem with total completion time criterion is considered. There are \(n\) given jobs, \(j_1, \dots,j_n\), and the processing time \(p_i\) of the \(i\)-th job is given by \(p_i=1+b_is_i\), where \(s_i\) is the starting time of the \(i\)-th job, \(i=1, \dots,n\). If all jobs have different and non-zero deterioration rates and \(b_i>b_j\Rightarrow b_i\geq\frac{b_{\min}+1}{b_{\min}}b_j+\frac{1} {b_{\min}}\), where \(b_{\min}=\min\{b_i\}\), then an optimal schedule can be found in \(O(n\log n)\) time. The conducted computational experiments show that the presented algorithm performs very well even on data not satisfying the assumed constraints. Cited in 3 Documents MSC: 93B40 Computational methods in systems theory (MSC2010) 93C55 Discrete-time control/observation systems 90B35 Deterministic scheduling theory in operations research 49N90 Applications of optimal control and differential games Keywords:scheduling; single machine; deteriorating jobs; total completion time; algorithms PDFBibTeX XMLCite \textit{M. Kubale} and \textit{K. M. Ocetkiewicz}, Control Cybern. 38, No. 3, 713--721 (2009; Zbl 1301.93064)