{"entities":{"Q1104235":{"pageid":1114984,"ns":120,"title":"Item:Q1104235","lastrevid":66141780,"modified":"2026-04-12T07:49:51Z","type":"item","id":"Q1104235","labels":{"en":{"language":"en","value":"On a scheduling problem where a job can be executed only by a limited number of processors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055358"}},"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":"Q1104235$42F741AE-3CDB-4791-99AE-44CECC176262","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"573430a8b3bf5b2d89c80c2e2c734cdff4bcfb36","datavalue":{"value":{"text":"On a scheduling problem where a job can be executed only by a limited number of processors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104235$19B0F4BE-4E77-46D1-85E0-3BEAAEB0A2C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f85049cfb21ec960ef608a05718460a56e7b243f","datavalue":{"value":"0646.90045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104235$269AD7C8-B75F-4EBB-9AA3-89BBCA5D731F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f0a563f1d3f4f75fb392a06624fe659ad10eeafb","datavalue":{"value":"10.1016/0305-0548(88)90063-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104235$EBD894DF-8A25-4BC5-81E6-9AA6051813A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e630590c5ca6e787c3c7b5e291898405495fea2b","datavalue":{"value":{"entity-type":"item","numeric-id":162215,"id":"Q162215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$3900DD2B-A4F0-4164-B763-C5461A921F48","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":"Q1104235$BE811152-9439-4EB3-B7D4-322423AD0277","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c3563641b589fdedb458de6ecb5d3ec3d486188b","datavalue":{"value":"We consider a job scheduling problem where each job can be executed only by a subset of available processors. This problem arises when we are scheduling a set of cannons to be fired on a set of targets. Each cannon can destroy only a subset of targets and we want targets to be destroyed in the shortest possible time. We define what is meant by a balanced solution. We then consider three problems: How can we detect that there is a balanced solution? If this solution exists, find such a solution. If no such solution exists, find an optimal assignment which minimizes the makespan. We show that there are polynomial time algorithms to solve these problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104235$0744B537-46F0-4A20-9317-487FD3A4283E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104235$AB0D328A-983B-4BA3-BB73-1B4D335F0F28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104235$8A4A4369-C9DA-475B-AA27-3761B89E378A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d31bc4899753bdc83dd2c771f4274e9ec1b2dc84","datavalue":{"value":"4055358","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104235$6FE1F7D0-2205-4FEB-A8CC-AD19644BB216","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27460fb340b49c6e8bd324d65446214141faf465","datavalue":{"value":"job scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104235$DE0E6F88-E989-4DD8-9F21-F4985F0B1342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e79fd5eb335563b1127bb89cf3f19aece62b5dcc","datavalue":{"value":"balanced solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104235$559CC860-AAC0-4AF3-BD96-C499608041AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1dd92ba390d06aef54843c00b923d5fab9a61c4f","datavalue":{"value":"optimal assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104235$CB4CA7C7-2296-4E9D-8BC5-6D96711B5CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104235$6AF26CFF-1D86-4E21-BBC0-7246AD28F80C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d85c121e6e6200a1d4667137fca957de2656737","datavalue":{"value":"polynomial time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104235$830D1A15-F7A1-49D2-A429-7953E3ACB674","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a441f6fa21648e6226ebea36faad5dfd6fced31","datavalue":{"value":{"entity-type":"item","numeric-id":290258,"id":"Q290258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$9E2F3F55-76AE-4322-B9C9-4512BC2A2152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"47287d42254c668443f35e7681b0c02cf3b2e14b","datavalue":{"value":{"entity-type":"item","numeric-id":702771,"id":"Q702771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$AA7CBEF0-20FA-492F-B320-CD1860026FAE","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":"Q1104235$86688E5C-0503-4C20-A0F3-09488A48FEF5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2bf81d98340066f7d0ff055dcf8749e321100dc6","datavalue":{"value":"https://doi.org/10.1016/0305-0548(88)90063-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104235$ADE1DA43-CA86-42E9-B3E3-163A22B29AF3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7573d7b3957020fa00c7c2408a576fc725924d67","datavalue":{"value":"W1966447954","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104235$032EC88F-437B-443C-87FB-239128FA3D97","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f69a74e308f73d0ad3e29bde22f0c7cd163d4f","datavalue":{"value":{"entity-type":"item","numeric-id":4658190,"id":"Q4658190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$CEF8DB26-2CEC-42F7-BB72-E6D55460DA85","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":"Q1104235$FAFAC640-42A3-48E1-9BDA-C041449F7963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaee65c9f89eb2322b1ea792982596d2bb5379e2","datavalue":{"value":{"entity-type":"item","numeric-id":4133147,"id":"Q4133147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$47930CEA-7A03-471C-80B7-6823B6045F29","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":"Q1104235$06BBC8F9-FF71-418E-8BE4-5056010685E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4ae368f5009736f85a97fcebaf4630774830353","datavalue":{"value":{"entity-type":"item","numeric-id":4124328,"id":"Q4124328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$18ECB310-0F5B-4A86-95D6-D290C39560AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$FCBF04BD-DD42-4520-928F-025525802A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c52b21e2b050930655d553363cf317d38372f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3885184,"id":"Q3885184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$A13DF285-3990-4983-89BA-FBE10FF8AD0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$9FBA641E-CBF2-49F1-9A6D-E6BFBDDC015B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1fae2c8f5cf61b31423ad640fb4fa499d668660","datavalue":{"value":{"entity-type":"item","numeric-id":917431,"id":"Q917431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$6E1FA79F-7B63-49E3-94F9-53F4AEA136DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104235$8102DC15-EE38-4149-9A58-FFFA5999BF3F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"450182155ac89730fd318e173cfdd554a531c18f","datavalue":{"value":{"entity-type":"item","numeric-id":1399581,"id":"Q1399581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53372d0d887ceecc24c8c4f9fa55c51004cef8a9","datavalue":{"value":{"amount":"+0.8708026","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":"Q1104235$00E1B752-F697-4F88-9211-C2E2CCCC1E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f391a9837cb52a623951c8df30a6c054ec06b71","datavalue":{"value":{"entity-type":"item","numeric-id":4706224,"id":"Q4706224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44dc3ee527a0a67b8f3795adaa6fa949778a5a59","datavalue":{"value":{"amount":"+0.87032056","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":"Q1104235$CAA28BE4-E5DA-4E18-8D02-1AA26662519D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5fd986904a77db5a171c78199c081a7723143af","datavalue":{"value":{"entity-type":"item","numeric-id":3804433,"id":"Q3804433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ffefd94bbdec6baf80f502f39191f9cd1520c88","datavalue":{"value":{"amount":"+0.8678467","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":"Q1104235$57E8763F-C97B-4194-9604-20B070C4C71E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dad285fa18892bb76f48b46252f2ad2f754b58a3","datavalue":{"value":{"entity-type":"item","numeric-id":1351619,"id":"Q1351619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac4436e2c20365c5158156d7ab6e6ed65238a7ce","datavalue":{"value":{"amount":"+0.86491156","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":"Q1104235$EACD30D0-EBDF-4772-96FF-D8DB4840AD7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9fb3895961941a80ba90eba9b449560cc80206a","datavalue":{"value":{"entity-type":"item","numeric-id":4690459,"id":"Q4690459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f925170ff5c31ed083d6a22bf4fc5b2711fc6946","datavalue":{"value":{"amount":"+0.8618131","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":"Q1104235$E29A340F-CF86-4BBB-898A-4B1EBFEFCC79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb8ab49f63f73e96234aaf03ce95c05e27ce6b80","datavalue":{"value":{"entity-type":"item","numeric-id":2897985,"id":"Q2897985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69f8e2d4ccd749ffad0123f7b81f3ffe3f95c0b2","datavalue":{"value":{"amount":"+0.8605823","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":"Q1104235$93C12558-4CA2-46FC-9570-4B05F5CC005F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ab798256e42357c878cbf79ef983212eb1700a5","datavalue":{"value":{"entity-type":"item","numeric-id":2015808,"id":"Q2015808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69f8e2d4ccd749ffad0123f7b81f3ffe3f95c0b2","datavalue":{"value":{"amount":"+0.8605823","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":"Q1104235$33343CB7-38B6-485D-A396-E913B452CBF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e19082ae257590107ac2688d56d8c864f499e52","datavalue":{"value":{"entity-type":"item","numeric-id":1575603,"id":"Q1575603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0694c040a28ca8d4f88f3c1215c69fe1940ad415","datavalue":{"value":{"amount":"+0.85874826","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":"Q1104235$04DFB02F-72A6-4A88-A418-66FC48969A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab2cc517398628898896c78de96cc28637424573","datavalue":{"value":{"entity-type":"item","numeric-id":4427861,"id":"Q4427861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fd73d31379de5ca33a3c4d45ec376ddc00aeb3a","datavalue":{"value":{"amount":"+0.8586792","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":"Q1104235$81749976-6F69-4D4A-A97E-4C3704E5C7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6b50ba932f2129af9f039947915416a6c02f1af","datavalue":{"value":{"entity-type":"item","numeric-id":2304117,"id":"Q2304117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcdb669f8dfe1f4824d16af64b63aea3a67e3ff5","datavalue":{"value":{"amount":"+0.8569791","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":"Q1104235$AD6470A7-F370-4E64-9E18-3E01C3E9C1D9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On a scheduling problem where a job can be executed only by a limited number of processors","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_a_scheduling_problem_where_a_job_can_be_executed_only_by_a_limited_number_of_processors"}}}}}