English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we consider the problem of scheduling jobs on parallelidentical machines, where the processing times of jobs are uncertain: onlyinterval bounds of processing times are known. The optimality criterion of aschedule is the total completion time. In order to cope with the uncertainty,we consider the maximum regret objective and we seek a schedule that performswell under all possible instantiations of processing times. Although thedeterministic version of the considered problem is solvable in polynomial time,the minmax regret version is known to be weakly NP-hard even for a singlemachine, and strongly NP-hard for parallel unrelated machines. In this paper,we show that the problem is strongly NP-hard also in the case of parallelidentical machines.

Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion