Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: NP-complete

Sortuj według:

Ogranicz wyniki do:

Complexity of cover - preserving embeddings of bipartite orders into boolean lattices

Herman G.

Reports on Mathematical Logic

2014

Vol. 49

99--117

We study the problem of deciding, whether a given partial order is embeddable into two consecutive layers of a Boolean lattice. Employing an equivalent condition for such em- beddability similar to the one given by J. Mittas and K. Reuter [5], we prove that the decision problem is NP-complete by showing a polynomial-time reduction from the not-all-equal variant of the Satisfiability problem.

Constraint satisfaction problem based modelling and value ordering based heuristic for nurse scheduling

Djeffal L., Goncalves G., Babes M.

Journal of Applied Computer Science

2006

Vol. 14, nr 2

7-28

Nurse Scheduling Problem (NSP) consists of assigning shift-types (morning, afternoon and night) to qualified personnel over a certain planning period. It is a difficult and time-consuming task. In this paper we present a formulation of the hospital Nurse Scheduling Problem just like Constraint Satisfaction Problem "CSP" based constraint programming in order to find a solution, which minimizes the violation of Nurses' preferences. We would suggest a flexibility tool for helping to decide and for making negotiation easier. Our originality lies in the modelling of the problem, by defining the global constraints and in the algorithm of resolution to solve it, by proposing a new value ordering based heuristic for assignment of the decision variables taking into account the set of Nurses preferences. Our heuristic is based on the structure of the CSP and on the properties of constraints. It allows the reduction of the search space for solution and returns a solution within few second.

Interactive knapsacks

Aho I.

Fundamenta Informaticae

2000

Vol. 44, Nr 1,2

1-23

The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete problems, interactive knapsack heuristic decision problem (IKHD), interactive knapsack decision problem (IKD) and multidimensional cloned knapsack decision problem (MDCS), are presented for the interactive knapsack models. IKD and MDCS are shown to be strongly NP-complete. By using interactive knapsacks we can model many planning and scheduling problems in an innovative way. Possible application areas include electricity management, single and multiprocessor scheduling, and packing and tiling problems. As a by-product we show that the longest weight-constrained path problem is NP-complete.