{"entities":{"Q1111373":{"pageid":1122122,"ns":120,"title":"Item:Q1111373","lastrevid":66688572,"modified":"2026-04-12T11:59:37Z","type":"item","id":"Q1111373","labels":{"en":{"language":"en","value":"Preemptive scheduling of independent jobs on a hypercube"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076609"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111373$011B3B2F-44D5-4C57-BE9E-0DC03068FFED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a3d0e6e9417a955dc46813fc03715e2d05751c53","datavalue":{"value":{"text":"Preemptive scheduling of independent jobs on a hypercube","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111373$C8987242-C488-4A37-ABCC-299E05F5B241","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2e16ab5d295bfbcddfcadcaa850e2695138a3b45","datavalue":{"value":"0658.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111373$FCB498D1-E0A9-4A42-9C4D-598EE04BC7E3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"14b74961791aab08dda4412b4be47a7515c3a593","datavalue":{"value":"10.1016/0020-0190(88)90209-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111373$A4F2DABF-FD34-48DD-84DB-8C61351A2D1A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c3c51ad29d30392c0e38ec522f0737acab086fdf","datavalue":{"value":{"entity-type":"item","numeric-id":1111372,"id":"Q1111372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111373$A69ED9C7-D2FB-4D80-A956-39C173CC810D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"92231d63cabc3dcee3b00a19ed1ca19de20015c7","datavalue":{"value":{"entity-type":"item","numeric-id":678865,"id":"Q678865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111373$96334592-E669-4235-9A08-BB22FE98097D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111373$6938F8FF-F415-45AC-A181-C745E3AF9DD5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1111373$D373E2B6-5E75-478A-A291-DCE08C7478A2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09ead8a95b10b78e5df308f65393b6dec77ecc2b","datavalue":{"value":"We consider the problem of scheduling n independent jobs on an m- dimensional hypercube system to minimize the finishing time, where each job \\(J_ i\\) is associated with a dimension \\(d_ i\\) and a processing time \\(t_ i\\), meaning that \\(J_ i\\) requires a \\(d_ i\\)-dimensional subcube for \\(t_ i\\) units of time. An \\(O(n^ 2)\\) algorithm is presented that decides if all n jobs can be finished by a given deadline T. Using this algorithm, one may obtain a minimum-finishing-time schedule in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111373$D18B16B0-24B9-41AE-8FF5-A6449829C2BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111373$47B3FBFF-D103-4AC1-8C8D-030E600508B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111373$EE2D552B-B91F-421E-B717-97773BC83279","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea97e33785f9a6ad23e3b61e99db457debb6cbfb","datavalue":{"value":"4076609","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111373$29BE7B71-D221-40FE-B85C-771BFCFA4ED6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15eff2489d1abe6198af3b015ee555ef09dd6324","datavalue":{"value":"preemptive scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111373$259F2D7A-1194-44DA-8801-3E3D3459287E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111373$3C1B75DA-ECDA-47D0-96BF-0C567CFD9246","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111373$0087CEEF-B479-439C-B786-6E2A04CF8217","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4f51a5c6cab6837e6487ab61d2e7fadc5bd323fc","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90209-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111373$2AC5184E-080D-42E4-8147-552FDFD72C26","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a42f26e71caf41632f969a989b2ff346e0929f81","datavalue":{"value":"W1996376059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111373$9088905C-2A1A-4408-AE99-C56CC971E2D9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"55f7aa0aaa5de3f3884fd6bfb1b483140e8f4664","datavalue":{"value":{"entity-type":"item","numeric-id":3787470,"id":"Q3787470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111373$01A115F0-F6BA-41B6-A4D9-1B54E8552161","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce2043ff879d7369132e42619f1d0f205905cc57","datavalue":{"value":{"entity-type":"item","numeric-id":910210,"id":"Q910210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68ea3b732928cc2607d2cf4e9a17d3e1a5e29059","datavalue":{"value":{"amount":"+0.96703774","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$AA9DB140-55D4-4C96-9088-24CA31FE1BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06b97f4cfe195294b36bbfa187a1e87f53dbe2d3","datavalue":{"value":{"entity-type":"item","numeric-id":3787470,"id":"Q3787470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"daa41ab71e16515a7e70be618261623024bf8120","datavalue":{"value":{"amount":"+0.948775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$19DE3FAA-3718-421D-A7D5-AFBA752BC0C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26dd493d155a614e5b2e40972105206219889dde","datavalue":{"value":{"entity-type":"item","numeric-id":1177086,"id":"Q1177086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd5776525552f0acf6eefbe1b5f4e1877824cfcd","datavalue":{"value":{"amount":"+0.93262666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$FCAB969A-693B-440B-B9EE-B74788B02D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"881b1ae1a8c5045c220875fb1caddd242d3e559a","datavalue":{"value":{"entity-type":"item","numeric-id":917300,"id":"Q917300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d6bde3236c9353155ebf217698691ecfcd4303c","datavalue":{"value":{"amount":"+0.9301253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$13604C64-AD8C-48EC-B21C-ECFB33107C9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3774069bbb46b05581941ae6c6b96dacf3d26bd","datavalue":{"value":{"entity-type":"item","numeric-id":4507343,"id":"Q4507343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"417a06926674220808ad69010e9ebe22f690464b","datavalue":{"value":{"amount":"+0.92125255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$F487A74A-6207-4F24-BFFA-6A04328BFA2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e386b910f1abe2ad4844f35d34710a0e7e65b30","datavalue":{"value":{"entity-type":"item","numeric-id":4875180,"id":"Q4875180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"417a06926674220808ad69010e9ebe22f690464b","datavalue":{"value":{"amount":"+0.92125255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$A09B7AB1-6591-47BB-958E-456E0A5A99F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"535641eb9fb2428efbd7dd2052243b93d6145f3e","datavalue":{"value":{"entity-type":"item","numeric-id":5718920,"id":"Q5718920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8709deee0a4911be865e5f7dcefe28d679d460a4","datavalue":{"value":{"amount":"+0.9201652","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$E0EF0908-FDB6-4CA1-9CBC-DBAC1CB18CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18abf9c002fd585e91069ccb734b5d7cf7e5d0ae","datavalue":{"value":{"entity-type":"item","numeric-id":4717121,"id":"Q4717121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8aacffcef028d16e050cd5f4596f0a4cd853ce38","datavalue":{"value":{"amount":"+0.9136586","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$18C4AE2E-5E0F-42EA-8DEF-231E3470FA1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb9126520384a07468d4210558ea718698173b45","datavalue":{"value":{"entity-type":"item","numeric-id":1607020,"id":"Q1607020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5626dc5efac3236106e3d561116843e91fc15b18","datavalue":{"value":{"amount":"+0.9041124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111373$BBA5AF91-FCE6-44B0-B287-5801D16E5163","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Preemptive scheduling of independent jobs on a hypercube","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Preemptive_scheduling_of_independent_jobs_on_a_hypercube"}}}}}