Repozytorium publikacji - Politechnika Gdańska

We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem of optimal scheduling of sparse tree-like instances can be solved in polynomial time. However, if we admit dense instances then the problem becomes NP-hard, even if there are only two machines.

Autorzy

• prof. dr hab. inż. Krzysztof Giaro link otwiera się w nowej karcie ,
• prof. dr hab. inż. Marek Kubale link otwiera się w nowej karcie ,
• dr Paweł Obszarski link otwiera się w nowej karcie