{"entities":{"Q1013970":{"pageid":1015818,"ns":120,"title":"Item:Q1013970","lastrevid":69420720,"modified":"2026-04-13T06:53:13Z","type":"item","id":"Q1013970","labels":{"en":{"language":"en","value":"LP-based online scheduling: From single to parallel machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5547232"}},"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":"Q1013970$077EC6EF-8997-482A-B7AB-715A3D10CC4D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a7f818838227fe152b500f800b23b10cecae0275","datavalue":{"value":{"text":"LP-based online scheduling: From single to parallel machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1013970$0DF4A0E6-7214-41B5-A2DB-E1557B48687B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e17cecb52bd3fc974726c5a16295aa09b536208a","datavalue":{"value":"1162.90009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$54A1D8FC-3709-470C-9243-AF106CABE2B5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e3bed7e8f93d139e20a825548361af68501e91d2","datavalue":{"value":{"entity-type":"item","numeric-id":250714,"id":"Q250714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$99F823F1-1228-40F3-9007-A19EA6554CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"30164d1fc9e4eea30a30105706211ade44172985","datavalue":{"value":{"entity-type":"item","numeric-id":319250,"id":"Q319250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$E6E42330-890F-4EB3-B2DC-244750E81565","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$53D19C43-6591-4BE7-801E-F8934B2708AC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"62d8f72b1020afd83d4654c37051e1faed59ff3b","datavalue":{"value":{"time":"+2009-04-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1013970$4586B762-6E67-415B-A22D-72D7A1C617EE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c876c7ea4fdcd8e6e00c9fc6d4e5eed937ed1810","datavalue":{"value":"http://hdl.handle.net/10533/127845","type":"string"},"datatype":"url"},"type":"statement","id":"Q1013970$31EAFB21-7243-4EAA-8E50-7EC4D3C89B56","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3770b3a928f0fec93f50e09705d1f23138130f43","datavalue":{"value":"This paper considers the problem of scheduling \\(n\\) jobs with given release dates on \\(m\\) identical parallel machines such that the sum of weighted completion times becomes minimal. Both the non-preemptive and the preemptive problems are considered in an online version. The paper uses linear programming techniques and generalizes the ideas given by \\textit{M. X. Goemans} et al. [SIAM J. Discrete Math. 15, No. 2, 165--192 (2002; Zbl 1009.90096)] for the single machine problem to the parallel machine case. In particular, it improves the 3.28-competitive algorithm by \\textit{N. Megow} and \\textit{A. S. Schulz} [Oper. Res. Lett. 32, No. 5, 485--490 (2004; Zbl 1054.90037)] for the non-preemptive version and is 2.618-competitive. Moreover, it is shown that the algorithm can be improved further using randomization. More precisely, randomized algorithms with a competitive ratio strictly smaller than two are given for any number of machines, approaching to two as the number of machines grows. This improves former algorithms by \\textit{A. S. Schulz} and \\textit{M. Skutella} [SIAM J. Discrete Math. 15, No. 4, 450--469 (2002; Zbl 1055.90040)]. Finally, computational results are given for problems with up to 500 jobs and 25 machines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1013970$8879BCC4-EAFE-4F79-A6EF-B1EF8C694DBA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f9f554eb64639799bf090dd0dfa97bafd06e8c2c","datavalue":{"value":{"entity-type":"item","numeric-id":229433,"id":"Q229433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$FC122260-A81C-444A-B78F-EBCE14285DF9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$6CCD64D5-BC41-4AA4-8C94-5278478C49CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$1681BDD8-507C-48B7-B52A-721D67B9C397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$A55A971E-E9DE-4E54-9696-6E2118475BE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$D3B374F7-F8A8-4E93-9970-92C407593CB2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83b497c3601371953adbd3ad83e3f9d96fde0992","datavalue":{"value":"5547232","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$1973AF94-0898-4F02-89CD-21B00F79A9AB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e3c9edeb0b6a061c73376b5c23a1683f11ba0b7","datavalue":{"value":"Online algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1013970$9829AEA8-5B0B-4F33-8827-250CB776913C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1cbfb83e5f2c90cd52c8e434b389f2cc8452fd5","datavalue":{"value":"Parallel machine scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1013970$7BE67C06-55BE-4585-929C-52D2D6A56578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f08e6f5bf1425f8a71e217aa4b317b9b92047961","datavalue":{"value":"Linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1013970$7269BEED-B1CB-448E-93AB-94B9F7AC4853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c0a7039ae0cc7eb50e7517e575bbb855145f560","datavalue":{"value":"Weighted sum of completion times","type":"string"},"datatype":"string"},"type":"statement","id":"Q1013970$461BC433-B4FF-4DA2-9FDE-6589C82799BF","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":"Q1013970$6B408AB3-FDFD-4737-BC67-4781A9A40901","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b38d6b359e06d60c1e037b2716ba25ee4b458260","datavalue":{"value":"W2061672548","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$C21352E3-B00A-4DC2-AB47-D41349CA0A18","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"de0e56fd0ae6e8d27888d69a98c737ce5dbd0cd9","datavalue":{"value":"Q65553909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$77EC1CAE-ECB6-43A7-A33E-CF55BB1E7223","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4df972dbd2b40ec0e16a24b57bf45b5de585d4ce","datavalue":{"value":{"entity-type":"item","numeric-id":5463426,"id":"Q5463426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$8582DBB5-6F62-4344-8AD9-3B29611FFD74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bb45ef6e519aad3a64659db1ebc8c1b05efa7e4","datavalue":{"value":{"entity-type":"item","numeric-id":5704194,"id":"Q5704194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$6D83D657-FBA0-45F1-B2C2-9C987B3ECEEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f52f74350bb6bf04f474acf82faa65473e1b3ac","datavalue":{"value":{"entity-type":"item","numeric-id":4818873,"id":"Q4818873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$3E8BFE6C-FD76-4755-94CA-8C75827A9B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99ee1bccd358a77d151edad7eae6836a4db4c985","datavalue":{"value":{"entity-type":"item","numeric-id":2719134,"id":"Q2719134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$E084BF92-F412-45FD-AF9C-62EDE1F75856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4946da158ecc84ed76d56199f159b3f987359508","datavalue":{"value":{"entity-type":"item","numeric-id":2490322,"id":"Q2490322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$8ABA1455-C285-4266-AD1C-ABBECBAE56A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"809a9f827119a1a7d9cead9f3ff240c54a485c59","datavalue":{"value":{"entity-type":"item","numeric-id":5501838,"id":"Q5501838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$BCCE236F-B7F2-49AE-81A6-8889C13E4060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"864aa90b180e1c1166cb27aab62e39e47d6494b0","datavalue":{"value":{"entity-type":"item","numeric-id":2784510,"id":"Q2784510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$49DD33EF-AD7F-44B9-B77B-9C1438B1E59F","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":"Q1013970$B4B25D39-E73F-4738-8DDC-9446F410FAEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61a5f8b5781385bf6675409ca206dfdb61796f54","datavalue":{"value":{"entity-type":"item","numeric-id":4361782,"id":"Q4361782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$8E6063A4-4D5A-4790-BFA4-E94D011FC09B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c901734bd579355a7ba64889250fe648f0722302","datavalue":{"value":{"entity-type":"item","numeric-id":4875178,"id":"Q4875178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$855E9F71-8B7F-4656-9777-786E3404E4B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0925a2e52051b5f7c6bd2ba95333ff1f08432dec","datavalue":{"value":{"entity-type":"item","numeric-id":3612411,"id":"Q3612411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$B0F923FE-D107-4917-9862-222A88BA9475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76658abc0d8d16e18fd193c3a3b49eca8e9ea214","datavalue":{"value":{"entity-type":"item","numeric-id":703266,"id":"Q703266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$F128B5E3-D2EE-4424-84DA-C307F9E5FCA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45828c3ef5bcd7258917581fe6e78dd62dcc0940","datavalue":{"value":{"entity-type":"item","numeric-id":1290642,"id":"Q1290642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$34BF3B0D-3E4A-4E37-A8B8-46B2A3F2A0B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a40a3fc8ce74cd38f1c55a7fcc416f0046287e53","datavalue":{"value":{"entity-type":"item","numeric-id":2890462,"id":"Q2890462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$EA10DBBD-EC39-4F7D-BDE0-D678CEEA350E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5faec7978823cbd1765d0fad10943ba0529d1a","datavalue":{"value":{"entity-type":"item","numeric-id":4785695,"id":"Q4785695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$A812C250-A4BD-4333-9578-38F2CBFE48DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67a2be64a5f3c971c2622b1acc548263df5b1068","datavalue":{"value":{"entity-type":"item","numeric-id":1600001,"id":"Q1600001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$292DA70C-1E7F-41AF-BA7E-8BDCAE555C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"befd7263aa97bbccadb9c1092987d402091a9f6a","datavalue":{"value":{"entity-type":"item","numeric-id":3192029,"id":"Q3192029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$DA5172C5-2FD3-42BD-AEAE-FCCEC631E8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82a5b100421bd83d059125cdd03db246402db9d8","datavalue":{"value":{"entity-type":"item","numeric-id":5450810,"id":"Q5450810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$955B9F62-5B1B-4A6A-8F82-E6FD23227B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"210c98741c4fbe9357a9bfc81e1ac660c0954cbb","datavalue":{"value":{"entity-type":"item","numeric-id":1612009,"id":"Q1612009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$42E7EB11-1A1E-4778-A047-2AE32113CBDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dad54c9c3ec8a4f3c2e4fe2be4dca529fe5a68e3","datavalue":{"value":{"entity-type":"item","numeric-id":4368485,"id":"Q4368485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1013970$89432A40-A807-4770-A7C1-995D59E9A088","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35e66a59244ce52fdb97a3d8d47a2316f8c37924","datavalue":{"value":"10.1007/S10107-007-0204-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1013970$6C4F8407-0A38-4BEA-A07B-0571B03BBDE5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f321cf841fbf445e5431915dab286c7a90b93a9","datavalue":{"value":{"entity-type":"item","numeric-id":3596362,"id":"Q3596362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc55a408232796228f1512f6b097433e8ccc2357","datavalue":{"value":{"amount":"+0.9904564619064332","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":"Q1013970$1080FBFE-A3ED-47FA-8E27-20BB0DD097E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"047e596d0bec95f02cefd49730da91437570efb6","datavalue":{"value":{"entity-type":"item","numeric-id":4875178,"id":"Q4875178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cd29761c6e3e64fc3fae2e2b0bc3ead5e2e44f7","datavalue":{"value":{"amount":"+0.8675473928451538","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":"Q1013970$7B326660-94EB-4297-9BE1-C6F8AC3A8F2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e69cca8408c87673a60cb526413a8e644f1422a2","datavalue":{"value":{"entity-type":"item","numeric-id":1603586,"id":"Q1603586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cd29761c6e3e64fc3fae2e2b0bc3ead5e2e44f7","datavalue":{"value":{"amount":"+0.8675473928451538","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":"Q1013970$F11935D2-6CE8-43FE-A0F5-79E80FCC3AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"befbfcdf252cd16a560c77eff40a13eb7276673a","datavalue":{"value":{"entity-type":"item","numeric-id":5896935,"id":"Q5896935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a040d981310934d899aeb39cd50b6665d3febcab","datavalue":{"value":{"amount":"+0.857866644859314","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":"Q1013970$82EB1FB2-A40C-432A-9535-6827010229F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89d97bf45c4e35993f603eccb59ac38617f4da03","datavalue":{"value":{"entity-type":"item","numeric-id":5505682,"id":"Q5505682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f066131c3d2525c868d87764af6c61d485dd556a","datavalue":{"value":{"amount":"+0.852514922618866","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":"Q1013970$8772EEC3-98CE-4A0A-B2F6-5C678DB64D01","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"LP-based online scheduling: From single to parallel machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/LP-based_online_scheduling:_From_single_to_parallel_machines"}}}}}