×

A new optimal algorithm for a time-dependent scheduling problem. (English) Zbl 1301.93064

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.

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
PDFBibTeX XMLCite