| Autor: |
Nofal Samer |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Open Computer Science, Vol 14, Iss 1, Pp 1-19 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2299-1093 |
| DOI: |
10.1515/comp-2024-0011 |
| Popis: |
Let α\alpha be a set of nn elements and δ\delta be a nonnegative integer. A δ\delta -partition of α\alpha is a set of pairwise disjoint nonempty subsets of α\alpha such that the union of the subsets is equal to α\alpha and every subset has a size greater than δ\delta . We formulate an algorithm for computing all δ\delta -partitions of a given nn-element set and show that the algorithm runs in O(n){\mathcal{O}}\left(n) space and O(n){\mathcal{O}}\left(n) delay time between any two successive outputs of δ\delta -partitions of the given set. An application of the notion of δ\delta -partitions is illustrated in the following scheduling problem. Suppose a factory has nn machines and m≤nm\le n jobs to complete daily. Every job can be accomplished by operating at least δ+1\delta +1 machines. A machine cannot work on multiple jobs simultaneously. According to a utilization policy of the factory’s management, no machine is allowed to be idle, so all machines should be running on some job. Find a daily schedule of the factory’s machines satisfying all the mentioned constraints. Let α\alpha be the set of the factory’s machines. Then, an α\alpha ’s δ\delta -partition with mm subsets is a legal schedule if every subset (in the δ\delta -partition) includes exclusively δ+1\delta +1 or more machines that run on the same job. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
