We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is N P-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is N P-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W pracy zaprezentowany został system dowodowy dla logiki temporalnej czasu rozgałęzionego, nazwany Temporalną Logiką Procesów. Pozwala on na badanie statycznych i dynamicznych własności programów wyrażonych jako formuły temporalne rozważanego języka. Udowodniono mocne twierdzenie o pełności dla przedstawionego systemu formalnego.
EN
This paper provides one of the versions of prepositional, branching time temporal logic, called Process Temporal Logic. It allows to verify static and dynamic properties of programs, which are expressed as temporal formulas. PTL system is presented with the infinitary axiomatic system and the proof of the completeness theorem. The majority of temporal logics treats a program as a separate object and not as a language element. The system shown in this article is different. Program is a part of expression which describes its quality just as in dynamic and algorithmic logic.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.