Multiprocessor Scheduling Problem with Stepwise Model of Job Value Change

Adam Janiak (adam.janiak@pwr.wroc.pl) and Tomasz Krysiak (tomasz.krysiak@pwr.wroc.pl)
Additional contact information
Adam Janiak: Wroclaw University of Technology
Tomasz Krysiak: Wroclaw University of Technology

A chapter in Operations Research Proceedings 2004, 2005, pp 352-359 from Springer

Abstract: Abstract The paper deals with a scheduling problem on the parallel processors, in which the sum of values of all the jobs is maximized. The value of job is characterized by a stepwise non-increasing function. Establishing an order of processing of datagrams which are sent by multiprocessor router is a practical example of application of this problem. It was already proved that its single processor case is NP-hard, thus the problem is also NP-hard. Therefore, two pseudo-polynomial time algorithms for the problem with common moments of job value change and a polynomial time algorithm for the case with identical processing times are constructed. It is also constructed and experimentally tested a number of heuristic algorithms which solve the general version of the problem.

Date: 2005
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-540-27679-1_44

Ordering information: This item can be ordered from
http://www.springer.com/9783540276791

DOI: 10.1007/3-540-27679-3_44

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla (sonal.shukla@springer.com) and Springer Nature Abstracting and Indexing (indexing@springernature.com).