Pub. online:1 Jan 2014Type:Research ArticleOpen Access
Volume 25, Issue 1 (2014), pp. 37–53
The paper deals with a parallel processor scheduling problem with changeable job values. Contrary to other papers in this area, we assume that job values are characterized by a non-monotonic stepwise functions of job completion times (previously only non-increasing functions have been considered). We give examples of real-life systems that can be modelled in such a way, in order to show that the problem is interesting from practical point of view. The problem is shown to be NP-hard and a pseudo-polynomial time algorithm for its special case is constructed. Moreover, a number of heuristic algorithms is provided and experimentally tested.
Pub. online:1 Jan 2006Type:Research ArticleOpen Access
Volume 17, Issue 1 (2006), pp. 13–24
We study single machine scheduling problems, where processing times of the jobs are exponential functions of their start times. For increasing functions, we prove strong NP-hardness of the makespan minimization problem with arbitrary job release times. For decreasing functions, maximum lateness minimization problem is proved to be strongly NP-hard and total weighted completion time minimization problem is proved to be ordinary NP-hard. Heuristic algorithms are presented and computationally tested for these problems.
Pub. online:1 Jan 2001Type:Research ArticleOpen Access
Volume 12, Issue 1 (2001), pp. 61–88
Multicriteria sequencing problems with criteria ordered according to their importance are considered. Additional precedence and group technology constraints are imposed. We introduce a notion of a priority-generating vector function and suggest general techniques that form a base for the construction of polynomial time algorithms for numerous sequencing problems including all known polynomially solvable problems. A comprehensive survey of results for sequencing problems with ordered criteria is given as well.