{"entities":{"Q1084012":{"pageid":1094764,"ns":120,"title":"Item:Q1084012","lastrevid":66102561,"modified":"2026-04-12T07:33:56Z","type":"item","id":"Q1084012","labels":{"en":{"language":"en","value":"Scheduling tasks on two processors with deadlines and additional resources"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3978806"}},"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":"Q1084012$0D9573BE-CFFD-46A0-8410-4CEC601F2A79","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2ed2f07cf06485b4fbc00f489381b1bde228a552","datavalue":{"value":{"text":"Scheduling tasks on two processors with deadlines and additional resources","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084012$1581FF35-9AB5-41F3-8EE0-54EABD6F05AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8996a0edd772f901d9cb26f0d7fe25a96f05981f","datavalue":{"value":"0605.90073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084012$9B511EBC-9D11-4483-B073-486CBC5AA7E2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"15d5400eda984a511295d0f9623b4714f2cebe42","datavalue":{"value":"10.1016/0377-2217(86)90138-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084012$EC2E0B58-26CF-474E-B180-D9D553504FC9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$4122E9F2-6DB8-4E3A-A4BA-98A41C201945","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$DBF090B6-D1EA-4CB8-A239-8BB119108BA6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1084012$5247E225-D3E6-41F6-838E-D8B0CCB14671","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9bc2469f03f7c75e76aae8dff583f7a4735a18c9","datavalue":{"value":"The deterministic scheduling model in this paper involves a finite set of identical processors, a finite set of additional resources and a finite set of tasks to be executed, each requiring one processor and specified amounts of additional resources during a known amount of time. Each task is to be completed before its deadline. We establish the complexity status of the two major open nonpreemptive scheduling problems of this type. That is, we prove NP-hardness of two scheduling problems with two processors and unit processing times of all the tasks; the first one has one resource type available in a specified amount, the second one has an arbitrary number of resources, each available in amount of one unit. These results are complementary to a previous paper by the first author [Inform. Processing Letters 8, 60-63 (1979; Zbl 0401.90048)], where a polynomial-time algorithm was presented for an arbitrary number of processors, one resource type and zero-one resource requirements of the tasks. In addition, in the present paper new restricted versions of ONE- IN-THREE 3 SAT are also proved to be NP-hard. These heavily restricted versions promise to be useful in other NP-hardness proofs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084012$65EA68EC-456B-4042-A9F1-ED646224EB31","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084012$212529B5-349E-41C6-AB82-740F402ACC52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084012$BF0E0DE7-229A-4AD3-B1CD-02122ABFEF0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084012$4E6FBBD9-ACB7-4992-BA69-C768D1D94B5A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e8d851437d4c96713419093f5ae89a666a99e59","datavalue":{"value":"3978806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084012$580E33AE-F1F2-4E5D-B2E5-4EEC83545838","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c019636d603acdd3d851350cb14feafea63adc8a","datavalue":{"value":"deadlines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084012$65B01982-7C73-47BB-9A60-98EB9FFBC1BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d753e5e990ebfdf83a949c3aaffa7801d2f62688","datavalue":{"value":"resource constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084012$F2E1F8DB-E0D4-4AF0-A565-24FF43125381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc770d3e2bfa57b3b75921e2539bd37b46d1dbf0","datavalue":{"value":"finite set of identical processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084012$47383FDF-E864-47F7-9357-50DCECEE02C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da331c001028b3be01f10e9737864bc7bfa6a77a","datavalue":{"value":"additional resources","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084012$40C08889-3077-4DA9-BBCA-3CC21E254C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c8923e0cb490d6f02e4e0f77b8069ffb59359ac","datavalue":{"value":"two major open nonpreemptive scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084012$63BC3913-6168-4E02-943E-C5ECB728D2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aecb4baa5821ea76a005bdb100ff5bae0cdee090","datavalue":{"value":"NP- hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084012$2F9B6A93-5719-47CD-B368-5FDF796DA13D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"54a1a60f7878342d195fe8fcac0e176777632c9f","datavalue":{"value":"Q57387928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084012$0A94571B-31A8-43CA-8BD8-63B670F084F8","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":"Q1084012$367A104D-E009-4ADF-893E-85DD4A98CDBA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"86bae5e408bf4dfe51ed70a5cf93ee9e3dba0b50","datavalue":{"value":"https://doi.org/10.1016/0377-2217(86)90138-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1084012$DEB09B03-9B14-49A3-B250-58605E1878D6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5b97281ded1c66e099e08e1631c42fb6eeb618a","datavalue":{"value":"W2018082550","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084012$361F4B81-5A50-4F26-B468-DDC4E896B817","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee045d4c1365a06485d035e5bba80ff8c8ee70ff","datavalue":{"value":{"entity-type":"item","numeric-id":1255432,"id":"Q1255432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$98ECD367-A0BA-4812-9637-9F49FB8AA0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"647887f10b1dbe2de36403203573c37a1f26acf9","datavalue":{"value":{"entity-type":"item","numeric-id":4182233,"id":"Q4182233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$70621AB3-0F33-45E7-8AD7-EC13C4C9676E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43fbbe54300be7fffaceec1c73c5d1f3e4364d17","datavalue":{"value":{"entity-type":"item","numeric-id":1837623,"id":"Q1837623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$E308E197-BB0D-4122-B881-10306BC7B422","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63d7deaf3e7bac9de0ff67356dbe46db811c5ca2","datavalue":{"value":{"entity-type":"item","numeric-id":1052820,"id":"Q1052820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$E1FBABAC-2D4B-4727-A8A2-3333B5B2A96F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9661dc321e9197c44616cc21a898b0798188a31","datavalue":{"value":{"entity-type":"item","numeric-id":4131987,"id":"Q4131987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$08383E97-8C09-452C-BB9D-D69F0940E41A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c28afcd7f535eb5d060786592b3e3f2c4f02d206","datavalue":{"value":{"entity-type":"item","numeric-id":4166568,"id":"Q4166568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$1FE51034-CC13-4BE7-BF6F-C2461A2B6A01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be8a53fe134b0b70830e68dfe27608ac9174a22f","datavalue":{"value":{"entity-type":"item","numeric-id":4140712,"id":"Q4140712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$D28EDDA6-8448-43AB-804D-67B1AC20F8FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$C0A1AF2B-7F29-43CB-BCE1-35D4F4AD519F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"206aac1fed08722358479159401448a8a87bf332","datavalue":{"value":{"entity-type":"item","numeric-id":4198327,"id":"Q4198327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$61983BB7-8AC6-46EF-B3AF-3C527C0A4EFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"befdb7fe1eaca43bc37060727dd405b397d1b5cc","datavalue":{"value":{"entity-type":"item","numeric-id":3940839,"id":"Q3940839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$DBE3B6AE-E8D8-428C-8ADF-4333A03B1C78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc91e14183c7f776e81c49bc16c9345bba17ad00","datavalue":{"value":{"entity-type":"item","numeric-id":3221735,"id":"Q3221735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$F4194C40-EC07-450A-91C8-97FD6D61321F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c43b340141108fe3cf098903820b3120fecb533","datavalue":{"value":{"entity-type":"item","numeric-id":3312010,"id":"Q3312010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$AA72D310-A40B-45BB-BC36-C251AFA91841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$2C35F479-6ED7-4625-BC9A-8C1234C4749A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b22ccff316e5f62cb128a177eb788cb71729906","datavalue":{"value":{"entity-type":"item","numeric-id":3911382,"id":"Q3911382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$E0647650-43FF-41E9-ACFD-6812DB3E35B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50041fd827b9a880db5475227f379529c471731","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$E2D69291-10B8-4092-927B-3C5E37392914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a87de1c38db6556a83241e897586e60278b4d349","datavalue":{"value":{"entity-type":"item","numeric-id":4152015,"id":"Q4152015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$1AF1C5DB-87F5-4BAF-BDC4-24718638DC3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1d100291218ee3055d0233659bfb3e960399a04","datavalue":{"value":{"entity-type":"item","numeric-id":3315254,"id":"Q3315254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084012$47ABE07C-6E6E-4B1A-93D2-E099AAA1DAEC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d9c1a613ce36b5740d05659b20f732308d39ae7","datavalue":{"value":{"entity-type":"item","numeric-id":1084859,"id":"Q1084859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebd76711bd7de4035346907df73330b1199f1f8d","datavalue":{"value":{"amount":"+0.8124777674674988","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084012$EB4E3ECD-D339-4DEB-A87B-FC283673E96A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fe4494896a64fe5dcabd452e98a70da251ec0bf","datavalue":{"value":{"entity-type":"item","numeric-id":3821925,"id":"Q3821925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"691ae6650f43b7bdc28ff605c788ac8a220ae07a","datavalue":{"value":{"amount":"+0.8111573457717896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084012$995AE031-B100-4669-9DC9-326B645BFF1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"816117851aad04687f26c02d0f19ac0e22e30292","datavalue":{"value":{"entity-type":"item","numeric-id":3741047,"id":"Q3741047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"829e0a16cd796a9cd6236dca5dca9e5d043601cf","datavalue":{"value":{"amount":"+0.8105703592300415","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084012$CC49AB8D-5600-4DF2-908A-463971FEF026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b73084b8b72855d1511f4305e2400989c254bb8","datavalue":{"value":{"entity-type":"item","numeric-id":3470246,"id":"Q3470246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9037fd1cfe369929c3a06ede2fb51d84a7757f1f","datavalue":{"value":{"amount":"+0.8033787608146667","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084012$94FEAE55-95CD-4935-A3F9-048865C9610A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c2c9c45d9bd555dab5743f876bbe26877383d4d","datavalue":{"value":{"entity-type":"item","numeric-id":3319772,"id":"Q3319772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0897e514c0d148ec4ec01f84ca6bb268d94b392","datavalue":{"value":{"amount":"+0.8033123016357422","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1084012$4E7661F8-58F0-4A69-AD16-715CBA3F1C77","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling tasks on two processors with deadlines and additional resources","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scheduling_tasks_on_two_processors_with_deadlines_and_additional_resources"}}}}}