{"entities":{"Q1061599":{"pageid":1072351,"ns":120,"title":"Item:Q1061599","lastrevid":69762456,"modified":"2026-04-13T09:13:10Z","type":"item","id":"Q1061599","labels":{"en":{"language":"en","value":"Analysis of a linear programming heuristic for scheduling unrelated parallel machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3912080"}},"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":"Q1061599$67C86AD4-C36F-4652-B3CD-4FFD1CDE9B31","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5412305c9e08156b922c6348c28c0aa55ffbd07","datavalue":{"value":{"text":"Analysis of a linear programming heuristic for scheduling unrelated parallel machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1061599$2CA95FCF-44D8-461B-82A9-97482DABDDDA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0f48209b57f99d2d2cab9afb40c1dffb2916033e","datavalue":{"value":"0571.90035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1061599$FAB1A448-D4CB-499C-9A61-CE8F7739963F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0ba83cc4454f1a1efc272b0df141cdd615437c3b","datavalue":{"value":"10.1016/0166-218X(85)90009-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1061599$76FEFD08-72FF-4FA8-AF33-FB79B456DD85","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":"Q1061599$7078F91A-E491-4E69-8612-06DBB495D452","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1061599$E346AF6D-D3F3-406B-8278-15C31B155884","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d20c49e850e670f87624e1e5bd968f7e283367df","datavalue":{"value":"Each of n jobs is to be processed without interruption on one of m unrelated parallel machines. The objective is to minimize the maximum completion time. A heuristic method is presented, the first stage of which uses linear programming to form a partial schedule leaving at most m-1 jobs unscheduled: the second stage schedules these m-1 jobs using an enumerative method. For \\(m\\geq 3\\), it is shown that the heuristic has a (best possible) worst-case performance ratio of 2 and has a computational requirement which is polynomial in n although it is exponential in m. For \\(m=2\\), it is shown that the heuristic has a (best possible) worst-case performance ratio of \\((1+\\sqrt{5})/2\\) and requires linear time. A modified version of the heuristic is presented for \\(m=2\\) which is shown to have a (best possible) worst-case performance ratio of 3/2 while still requiring linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1061599$39081E23-64CC-4972-9FE1-EEE52B6D5187","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1061599$E33B1654-CCBE-4E73-97A9-C6301D8B42F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1061599$C6852AB3-2831-4679-AA50-937494FA891D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a4814edfaf41998e1dc34acf00c0248a8bd1ed06","datavalue":{"value":"3912080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1061599$C6817B7C-B8A6-404B-8A6F-599B120CC8DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"458da00cd4c6346ae077352ce5bc00ec665a194a","datavalue":{"value":"unrelated parallel machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1061599$65B08E28-662F-4AC1-96FF-50695077A444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edae7761f34acf97f2d43de39f62b25834213f9a","datavalue":{"value":"maximum completion time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1061599$41838C72-ABB4-46A6-B308-B13704923CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d31c2daef2a80161502378446e0198f17f748d4","datavalue":{"value":"heuristic method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1061599$99474FD3-DE3C-4ADC-99A6-875A814CF8AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f484efaec285509ff945e4480ef36479c3fed36a","datavalue":{"value":"worst-case performance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1061599$E5FFAC7D-AF58-4CA7-811D-65F59E4CB385","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b47923e0e711394508c09165250b22f85b3fc9b1","datavalue":{"value":{"entity-type":"item","numeric-id":170009,"id":"Q170009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$799408CF-7DF9-4A47-8302-A1EA53236CA6","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":"Q1061599$E9C044C2-BF10-4319-AB97-02BB8216AA2F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc2e0d2db0a6d299eb21235fc0a97593259b0d3","datavalue":{"value":{"entity-type":"item","numeric-id":1394121,"id":"Q1394121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$8BBC0B39-C718-4C9B-A61F-B03E34657927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa102313bd6282ba09c7a888a595d49e4fe03d7b","datavalue":{"value":{"entity-type":"item","numeric-id":3925878,"id":"Q3925878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$BCCDCA97-6453-4F21-BF16-425030B0A0A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8506cb0dca743fcc107548c7d84f0a553edc56a","datavalue":{"value":{"entity-type":"item","numeric-id":3895229,"id":"Q3895229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$30216E8B-684A-4A93-B90E-C6005DA2176D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b054b5af59890393b2babdfb385b33c0e3d83db6","datavalue":{"value":{"entity-type":"item","numeric-id":4147833,"id":"Q4147833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$D9439053-08CE-4C59-8BFC-CB5E403A9268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2260b996422f953b9b92d577d1bb801544dd765","datavalue":{"value":{"entity-type":"item","numeric-id":3285991,"id":"Q3285991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$5031DDF9-55AA-4A1F-B9F6-E155A0A6E66C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33e8a7ecbe695332ed12405b42bedc2893b98ce3","datavalue":{"value":{"entity-type":"item","numeric-id":4095869,"id":"Q4095869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$7148986E-D187-4818-8650-A6079598A266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b27292a0dcc90836a68b3d2305667c316dd6ac71","datavalue":{"value":{"entity-type":"item","numeric-id":4160662,"id":"Q4160662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$66A16D84-228E-40F2-A6A2-AEFCE3463AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$12D127E7-67AB-487D-B8B3-52151F0B6FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97236fbeb6b6b2bba840114a8ba2f0448b9619f9","datavalue":{"value":{"entity-type":"item","numeric-id":4197641,"id":"Q4197641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$734B2F00-E117-46D0-9634-F7CE940D62B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696d2c12656116930cbe8540683b849a20624320","datavalue":{"value":{"entity-type":"item","numeric-id":3893644,"id":"Q3893644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$5B4130F2-BADC-465A-B867-2DA944997508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"049529675d903d4c6e9cad5925fb5ab48f636e24","datavalue":{"value":{"entity-type":"item","numeric-id":3928233,"id":"Q3928233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$91D12C23-6BDC-439D-B7D1-6E28D0B35771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"257001b5ea4ce59499d55ccb1ebeb946df7a89ba","datavalue":{"value":{"entity-type":"item","numeric-id":1229583,"id":"Q1229583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1061599$3ADC1192-DB22-4694-9E2F-D7514113F3EA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"170a2cadd4dae3511d726d2f51aaa26923f26526","datavalue":{"value":"https://doi.org/10.1016/0166-218x(85)90009-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1061599$74F995B5-1522-4961-80C1-4975D2B5F1F6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"726a07a4eae723824a454fffa9b9b8030c05921a","datavalue":{"value":"W1965349277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1061599$4C7164A6-4C0F-4BB2-AA2F-87072D81254C","rank":"normal"}],"P1643":[{"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":"1021d176c725e3f842c5967af48a735a6e6330c2","datavalue":{"value":{"amount":"+0.9083864092826844","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":"Q1061599$0C4296C9-764C-492B-8DD3-EFA462634325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"401d697b13992b3a47d12e48baf7bdfb231cdfef","datavalue":{"value":{"entity-type":"item","numeric-id":751989,"id":"Q751989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72fe872056ca294d752776da4214d3937ffa5d95","datavalue":{"value":{"amount":"+0.8981266617774963","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":"Q1061599$FEA289BE-D67D-4626-A651-EB9DB9656677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9eb8592e313467a5264a94fee3d33f66499e519d","datavalue":{"value":{"entity-type":"item","numeric-id":1338896,"id":"Q1338896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d991734f3b470f8aa095d557c055da9a4af2f39","datavalue":{"value":{"amount":"+0.8542043566703796","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":"Q1061599$AC544052-C8A4-4AB5-B954-363931E03E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8583ea9a68a7066a28b42cfd098d9b1eefa7e367","datavalue":{"value":{"entity-type":"item","numeric-id":1923596,"id":"Q1923596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"601baa296f68a1255daeded01847ec0410cf5c7b","datavalue":{"value":{"amount":"+0.8533425331115723","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":"Q1061599$4000C488-C017-410C-9F2A-1C5EEF18BF0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd36bfd280109bbaeba6780f94499a1bcb4e19ab","datavalue":{"value":{"entity-type":"item","numeric-id":2819574,"id":"Q2819574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dbbb0d2ddd5b1153bfab6c9b55367e92f4ece28","datavalue":{"value":{"amount":"+0.852710485458374","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":"Q1061599$07B04930-FF17-4B86-B151-982E9AF2ECAC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Analysis of a linear programming heuristic for scheduling unrelated parallel machines","badges":[]}}}}}