{"entities":{"Q1109673":{"pageid":1120422,"ns":120,"title":"Item:Q1109673","lastrevid":66450999,"modified":"2026-04-12T10:09:53Z","type":"item","id":"Q1109673","labels":{"en":{"language":"en","value":"Multiprocessor scheduling: Combining LPT and MULTIFIT"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070615"}},"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":"Q1109673$B6D57711-FF3F-4842-9C44-1B9409D16920","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e1b8fe7861bdbbb211fa15b6440ec17ec2528c18","datavalue":{"value":{"text":"Multiprocessor scheduling: Combining LPT and MULTIFIT","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109673$7F268274-BEDF-4C10-BF3D-F2C6C0362035","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e13d9e3c52bb9bd9c89ca0ef22bda2d195ef3543","datavalue":{"value":"0655.90036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109673$B8E69C48-4143-45B8-8611-98D05A5D2A13","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2445bad4ed5ee0a808c89afcc5ca25bf0341d501","datavalue":{"value":"10.1016/0166-218X(88)90079-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109673$167F0F13-976D-4E3F-AD1B-A43D6292AA88","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e454750c2fb4fbd7c325226ed92c521be961a5c","datavalue":{"value":{"entity-type":"item","numeric-id":177697,"id":"Q177697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$0C119031-626D-41B8-B4A7-1D5B070C2865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05d5b5cf1b51ac00b21cef72f2e5fbf95426000a","datavalue":{"value":{"entity-type":"item","numeric-id":1109672,"id":"Q1109672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$E29CD876-D939-456C-80F6-8C555B79B745","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$2480DA43-71FE-4E4B-9932-B37207E921DF","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":"Q1109673$5464B072-679A-4A69-80CA-02BF73EF0E1C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0cd4c5bb1a6bea879cd82ec60218a1394a08b416","datavalue":{"value":"The paper considers the problem of scheduling a set of n independent jobs on m identical machines with the objective of minimizing the total finishing time. Two well-known heuristic algorithms, namely LPT and MULTIFIT, are reviewed with respect to their advantages and drawbacks. A new algorithm called COMBINE is proposed which uses the result of LPT as the incumbent and then applies MULTIFIT with fewer iterations. The performance of the proposed new algorithm is better than that of LPT becauses it uses LPT as an incumbent.    Furthermore, it is shown that the error bound of the new algorithm is never worse than that of MULTIFIT. Although it is not known for the general multiprocessor problem how much improvement is obtained in the error bound for COMBINE over MULTIFIT, it is shown that the improvement is significant for the two-processor system. Empirical comparison results are finally provided.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$5DC7A0B6-5A08-4797-843B-31268AC6E89E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109673$4A12AFEB-47CB-4AD1-B93D-5DBFAC21DDC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109673$C1328DA3-0CD7-4999-9100-E61974BC6FD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109673$0EE59FB5-3C2B-4942-BBD2-D74C880C38B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b489d2e415e2a30e753e9eaeea887b7b0ca88aa6","datavalue":{"value":"4070615","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109673$AB137D5E-650C-4D58-BE25-03945625D636","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2484ef43bc9c784b4200ae297f0d99c551e12110","datavalue":{"value":"multiprocessor scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$9064E965-0944-4E67-8CE1-50119748BBD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c0b807ce95ffa69c2e1059e1ad6d9ddf7f7d221","datavalue":{"value":"comparison of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$1460C18D-0E63-4873-9D22-3B62EA87A421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb3d5d67ecc295abfe474c8e632a944f8b951c80","datavalue":{"value":"independent jobs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$1900D32D-327C-490F-9FBC-6BC6D666B9F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9c50e166b3bdd3d4624c14c188b82f1a7aeb2da","datavalue":{"value":"identical machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$BFB6CE04-4252-4EF8-B196-D21C5881E7D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77eca5aef1e8a5a7ab2d7cf5a79fa4a223d09669","datavalue":{"value":"total finishing time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$6D504C08-E7DC-44BB-A3DF-79AADD0DD78F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6fb9ac68bddbfa8d11616ed9b4850fa8757e1bd","datavalue":{"value":"heuristic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$8CE001AF-030C-4C0F-B02D-3D6EFD50734C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de83081b3e60fe50622d0467cc80748ac613a0c9","datavalue":{"value":"error bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$5A08B3A4-0CDD-4044-85D8-2170A029C941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46138cf39157d660347e79b2a39274514f62b0a3","datavalue":{"value":"improvement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109673$9AE2652E-BBCA-4297-A873-D9AB9C2F4247","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c51a7d1011ed2bb448c220bea1a3bdb3e0f81198","datavalue":{"value":{"entity-type":"item","numeric-id":1000780,"id":"Q1000780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$9E67D523-8C99-4FE2-96AD-647019129D19","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":"Q1109673$2089A777-5F93-40BC-A4F3-403322B76E7E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a62af7ec2eae31085b45e2485228d8678c8c12b0","datavalue":{"value":{"entity-type":"item","numeric-id":4151721,"id":"Q4151721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$D158CA56-E5EF-49B0-87AD-B8A48F6A24A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc17ad9868778f70eb43382620252bdd715f6c36","datavalue":{"value":{"entity-type":"item","numeric-id":3326834,"id":"Q3326834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$26316FE4-A077-4DBF-A759-604A80CBA7DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7988a07b6af9ebf84294ebb7cbd22eed7ca9deb","datavalue":{"value":{"entity-type":"item","numeric-id":3725543,"id":"Q3725543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$5A4E3152-1910-432B-BE1D-53B329C6C7F9","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":"Q1109673$C2D211C2-01B0-4BE3-AA0C-CEC5E20EAB80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df399851d600f5fc66b83855263f74637e3a379d","datavalue":{"value":{"entity-type":"item","numeric-id":5555416,"id":"Q5555416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$AEB9B3FE-B0C2-4825-8DA2-4B0DE7910CE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7470519bc10f2a005ff140469be5d8d581b53250","datavalue":{"value":{"entity-type":"item","numeric-id":5582060,"id":"Q5582060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109673$8DFBB26F-8305-4D8E-A9E6-22F523D5B2A7","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7e8418fe2c297813b741e8f4776cd3b005f528c5","datavalue":{"value":"Q127352600","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109673$A2251427-66D6-4557-9DA5-E0B50640AF86","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fa3187126f7537e3f8bc46b56709768895ab3b1","datavalue":{"value":{"entity-type":"item","numeric-id":1175792,"id":"Q1175792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1800dd992d40e6386f8fe19917eccef246e88f20","datavalue":{"value":{"amount":"+0.851311206817627","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":"Q1109673$A59BD652-1938-4EA5-997E-EDA9A8755009","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34085e53b1790f2383f1b4b7d259cf98f96fa6d2","datavalue":{"value":{"entity-type":"item","numeric-id":3677169,"id":"Q3677169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84a075653390c1dfd5b7e02ec81b037df7ffdabe","datavalue":{"value":{"amount":"+0.8435245752334595","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":"Q1109673$4967C75E-7DC6-42E9-9F0A-AEF87DD4327E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"545b20b18bc3b2332ce7eb6034f6e4f0aa8e89ad","datavalue":{"value":{"entity-type":"item","numeric-id":3326834,"id":"Q3326834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"066e9fe921672f2d9c85dabc4b153380380695a9","datavalue":{"value":{"amount":"+0.8410117626190186","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":"Q1109673$8D39EE75-0027-4CFE-9713-8FE57748C53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6b1e924721791ed3b3e445bd495fb3550b653f8","datavalue":{"value":{"entity-type":"item","numeric-id":1097028,"id":"Q1097028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e38db7559bb6f36bfece14781e3efec4c189508a","datavalue":{"value":{"amount":"+0.8377391695976257","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":"Q1109673$2FB029A8-1DD1-460C-86D4-89C894ED3466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6ad4e00065c0682ad3f3e2ea7d622ea35cda23d","datavalue":{"value":{"entity-type":"item","numeric-id":3725543,"id":"Q3725543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"170eaac5c3250e07667c4afd2e58634fd40e4120","datavalue":{"value":{"amount":"+0.8362588882446289","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":"Q1109673$63592087-572F-4F4F-93F2-E4ED921A9B18","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Multiprocessor scheduling: Combining LPT and MULTIFIT","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Multiprocessor_scheduling:_Combining_LPT_and_MULTIFIT"}}}}}