{"entities":{"Q1861922":{"pageid":1872664,"ns":120,"title":"Item:Q1861922","lastrevid":73906635,"modified":"2026-04-14T17:41:29Z","type":"item","id":"Q1861922","labels":{"en":{"language":"en","value":"Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1878979"}},"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":"Q1861922$3C909606-84B6-4F3A-9525-0C0CA95DAE67","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e8a6c6d91f1936c3ef097400168a819f14b4ea64","datavalue":{"value":{"text":"Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1861922$D57B0B36-AD79-4E92-B36A-D0C39665752D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2f35ffb67ec6482c55de9abe4cd60fea993cda81","datavalue":{"value":"1027.90032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861922$BFDE4DF0-BA8D-423A-815A-284705BF4B2A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"645f62472b02214c1b9e4f501a23ae6ea612f27d","datavalue":{"value":"10.1023/A:1021569406280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861922$D7ED3CDA-56D2-419B-83C8-D41D56AC2E8E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8f57d1123ebbbd10d621b3552a672e7729202712","datavalue":{"value":{"entity-type":"item","numeric-id":59875,"id":"Q59875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1861922$333AEAA4-DE48-4662-9988-400905903288","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"20f463f17fc7e9c2632ed067be3b2803defc648e","datavalue":{"value":{"time":"+2003-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1861922$8AA1FEB0-49D5-4213-8434-5D8DAE6FD80B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"901ce97ddee199a94ea5e34c38cb8fa38ce072f9","datavalue":{"value":"In this paper three heuristics for the unrelated parallel machine problem \\(R||C_{\\max}\\) are considered, where the makespan has to be minimized. All these heuristics are based on a mixed integer linear programming (MILP) formulation with binary variables \\(x_{ij}\\) (denoting when job \\(i\\) is assigned to machine \\(j\\)). After solving the linear programming relaxation of the MILP problem, restricted MILP subproblems are constructed from the optimal LP solution by eliminating several variables. Then these subproblems are solved by branch-and-bound techniques providing heuristic solutions for the whole problem. Finally, computational results are presented, comparing the proposed heuristics with results obtained by other heuristics from \\textit{S. Martello, F. Soumis} and \\textit{P. Toth} [Discrete Appl. Math. 75, 169-188 (1997; Zbl 0882.68016)] and \\textit{S. L. van de Velde} [ORSA J. Comput. 5, 192-205 (1993; Zbl 0777.90019)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861922$8252D42C-2D2A-4995-837F-3FCA8DB51652","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e47c7ebb56a1f0496381a9a28be5aa2e34301ed2","datavalue":{"value":{"entity-type":"item","numeric-id":210525,"id":"Q210525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1861922$8AB066FC-A587-4B5D-BA90-010AAF99C0D1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861922$21CE2A1A-1C44-4943-BC1C-23E76E1B30EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf44f3ad3a2f88c9b2a45e4395030d611f0589bf","datavalue":{"value":"90C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861922$36A81F9D-2D97-453D-8FD6-2CE1DE6852D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861922$18195FFC-132E-4E27-B9AF-03A8D062EACC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3fe89bff6f57555405d3cec3bd5673bf40d5780","datavalue":{"value":"1878979","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861922$FA469915-B6F8-4DD6-949D-D6DF6A978147","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861922$1FBDBE97-E022-40AB-8E2A-FEAA41537078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29ff25105b561b670176510ce616a966ffef4c26","datavalue":{"value":"unrelated machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861922$0B3F4665-F956-459C-9A67-8A4183AD5C2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c41e8252f126e1dba239903786002a155712321","datavalue":{"value":"mixed integer program","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861922$1F65010C-B956-4F83-BED6-880DAE98D13B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861922$42D8E04E-3C13-4ABA-826B-46E45C15ECDB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a10b348749aff388704e3811e6ee9c3bfecaa2cb","datavalue":{"value":{"entity-type":"item","numeric-id":542589,"id":"Q542589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1861922$ACB2BE1A-4846-4841-9C9D-6D8CED6CF0A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0ba855452457b807e3efc4a41204ffe6005dc50","datavalue":{"value":{"entity-type":"item","numeric-id":1348706,"id":"Q1348706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1861922$D88E3903-E59E-4560-ACD9-6CBA3DCCE079","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":"Q1861922$7A36C017-9701-4202-B587-78FDB5444416","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4dcc1c945d37bf269ce4f8ea8c7dcb724fed8881","datavalue":{"value":"https://doi.org/10.1023/a:1021569406280","type":"string"},"datatype":"url"},"type":"statement","id":"Q1861922$0069093E-FDE0-4A6D-9633-626800295FFE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"347a739a862fc7b687110431f20c0ce3c72a7c51","datavalue":{"value":"W80243447","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861922$812BAB20-EE20-4E34-BE27-613B761CD5D2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"779f4ceea88ffed0024a2b0a83693b68609077d0","datavalue":{"value":{"entity-type":"item","numeric-id":1061599,"id":"Q1061599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f96fdd3c521c4c5e353844b7704e5ac6a8426e8c","datavalue":{"value":{"amount":"+0.8522253036499023","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":"Q1861922$D22FC990-E6E4-41E0-A630-3BD943551F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81b42f12f954b4bdb7e3c134ce8aa32c46c786ad","datavalue":{"value":{"entity-type":"item","numeric-id":2276868,"id":"Q2276868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff1098d14a86d75ff9ed2a36c255cb7f2b88b9ab","datavalue":{"value":{"amount":"+0.8503561615943909","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":"Q1861922$4BDE4ED3-8801-4106-8F74-6E42518AF144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6f73faa53f3c74d491e34c1f7bd26ccf712c97b","datavalue":{"value":{"entity-type":"item","numeric-id":4300098,"id":"Q4300098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62aed9ecb68102e325eda400c46fc21719533c2b","datavalue":{"value":{"amount":"+0.8208357095718384","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":"Q1861922$D815A710-B2F7-4719-B311-518BAFF78F8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87d10c75fd849626d8cd4e17781581bc2089cd7e","datavalue":{"value":{"entity-type":"item","numeric-id":1363647,"id":"Q1363647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7778cc116f8ad31b77a6271df7cc637a8b02740","datavalue":{"value":{"amount":"+0.8174391984939575","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":"Q1861922$C7A80C44-2CD7-4D22-A2CF-BB35569A0369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdd362353d69d0f94b05493d6fe09fc39d37e16a","datavalue":{"value":{"entity-type":"item","numeric-id":2273695,"id":"Q2273695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e39e648407f7a234a00a1e6a4c36d0b24788305","datavalue":{"value":{"amount":"+0.8157234787940979","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":"Q1861922$BA533D3E-FA14-4393-845A-E0DD4678A5F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Heuristics_based_on_partial_enumeration_for_the_unrelated_parallel_processor_scheduling_problem"}}}}}