A new optimal algorithm for a time-dependent scheduling problem

Marek Kubale; Krzysztof Ocetkiewicz

A new optimal algorithm for a time-dependent scheduling problem

Abstract

In this article a single machine time-dependent scheduling problem with total completion time criterion is considered. There are n given jobs j_1, ..., j_n and the processing time pi of the i-th job is given by p_i = 1 + b_is_i, where si is the starting time of the i-th job, i = 1, ..., n. If all jobs have different and non-zero deterioration rates and bi > bj => bi >= (b_min+1)/(b_min) b_j + 1/b_min, where b_min = min{b_i}, then an optimal schedule can be found in O(n log n) time. Moreover, the conducted computational experiments show that the presented algorithm performs very well even on data not meeting the given constraints.

Authors (2)

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: CONTROL AND CYBERNETICS
ISSN: 0324-8569
Language:: English
Publication year:: 2009
Bibliographic description:: Kubale M., Ocetkiewicz K.: A new optimal algorithm for a time-dependent scheduling problem// CONTROL AND CYBERNETICS. -, (2009),
Verified by:: Gdańsk University of Technology