{"entities":{"Q423933":{"pageid":425700,"ns":120,"title":"Item:Q423933","lastrevid":51476957,"modified":"2026-01-18T10:45:34Z","type":"item","id":"Q423933","labels":{"en":{"language":"en","value":"An improved on-line algorithm for single parallel-batch machine scheduling with delivery times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6039487"}},"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":"Q423933$712AC0C7-CFE2-4DD1-A220-7C92C01B6F1A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b8281d5fbd46751d045635d6c88d9c81beefa660","datavalue":{"value":{"text":"An improved on-line algorithm for single parallel-batch machine scheduling with delivery times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q423933$EB99FCF7-7EA1-44B4-8CAC-33FB391A5662","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e735b640c4793ddd8187ffdc5e31c20e2544feb9","datavalue":{"value":"1252.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q423933$A0B66CD6-0B61-40E8-9678-6FE2177AC6C4","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":"Q423933$D48DD222-7938-40B3-A9A3-B026B0A4FADD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9cf2f505c732bca65c95db37822678ba6da7d9b6","datavalue":{"value":{"time":"+2012-05-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q423933$B6B0A9EA-97EA-4162-BD06-A134351B748E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q423933$6B64BE0B-2503-4B2E-A859-A66DE89C5F05","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2d421dd0b79012d9c5ae15014b6a0add30db07f4","datavalue":{"value":"6039487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q423933$3BDCE47A-C082-483B-8150-2E3FAA588696","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28555eccd293c836f47292caf8a1c98fae6d0a32","datavalue":{"value":"on-line scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q423933$914838EC-179A-455C-8CDF-84CB5A84F98A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78dfe9680430335ae5941d0068ced9704bcc3d46","datavalue":{"value":"parallel-batch machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q423933$055468B6-75C4-46BE-A1A4-CC408F0F1895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26621796b85ee3c686e3125acd56b45d84e25533","datavalue":{"value":"delivery times","type":"string"},"datatype":"string"},"type":"statement","id":"Q423933$07842CF6-348E-45D0-A1C0-10F189EAEBFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56d85aa22959094ecc003ac28085d2ab6f8f44c0","datavalue":{"value":"competitive ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q423933$C177C489-845A-4F1D-A7F1-037364B5FF5C","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":"Q423933$AC444079-6DE6-43C7-9B1D-10C4724BF596","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"63d4e1531500938b52c69ffd7faa3b4c65c93168","datavalue":{"value":"https://doi.org/10.1016/j.dam.2011.12.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q423933$A0FFD709-8F0F-4FC4-AD0E-AA31BE379237","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cb384620d9ad86da6a335aca1f0a50fcfe0d743e","datavalue":{"value":"W2080477217","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q423933$4DF303E8-A4BE-4643-9B0E-EAF660217BF3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af3b00240994d9bd1c5edc5e1f0eaee75ba0e5f","datavalue":{"value":{"entity-type":"item","numeric-id":1417850,"id":"Q1417850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$EF2B4273-3A87-41BA-8E99-AE1435959E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb43afa73a3d7411be4fc2e85784ab0784f5b305","datavalue":{"value":{"entity-type":"item","numeric-id":411231,"id":"Q411231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$0B990729-48A9-4720-B5C4-94BE67375878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36334078b919fd4b1bf0c128eca1a6aeff211707","datavalue":{"value":{"entity-type":"item","numeric-id":4943704,"id":"Q4943704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$8CD51124-B5A6-42EE-A3DA-E2E69318D759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2213a31159418a3eb8dbd93ccf2be60c49d0db5","datavalue":{"value":{"entity-type":"item","numeric-id":3995531,"id":"Q3995531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$0B85F983-6DB5-4D8F-8850-B3301B2F687B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3e2fd276b267541c50ef5979b9f269fd691eeb9","datavalue":{"value":{"entity-type":"item","numeric-id":4245414,"id":"Q4245414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$580902E8-0CB0-4EB8-A9D9-2822B5834C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5e8193040eb34b04f40fbd5c3eef324efd1af60","datavalue":{"value":{"entity-type":"item","numeric-id":4022933,"id":"Q4022933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$A7202371-8FAB-43E8-847E-85A55D42C7F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dc8ce063a17554b86f778e7f4fac0499d85d920","datavalue":{"value":{"entity-type":"item","numeric-id":1772971,"id":"Q1772971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$D5C834FC-8787-493D-9804-317CDF837998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b614e83d7f40113f7b9942de4f7a3d0164abd83","datavalue":{"value":{"entity-type":"item","numeric-id":1781801,"id":"Q1781801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$7A4C250A-7E31-4919-A1BE-7EC045C9F4FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99d629173719b9e06e84b3fbcc643a968e6094d7","datavalue":{"value":{"entity-type":"item","numeric-id":1022586,"id":"Q1022586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$83B77413-DE8D-42F6-9A37-E689C0ECF835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"431183d15fb8b9eadb490a5011888a75e09f00fa","datavalue":{"value":{"entity-type":"item","numeric-id":1944199,"id":"Q1944199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$21811D37-68F0-4F09-AD6B-731659B04973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66a2bf388740dee623db29201c80e598466aa48a","datavalue":{"value":{"entity-type":"item","numeric-id":841603,"id":"Q841603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$140551DE-9A59-4D8C-A6F0-0153EBFA4315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d94983f26976505f70b629fd5aa375872ae3147c","datavalue":{"value":{"entity-type":"item","numeric-id":2741218,"id":"Q2741218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$95B66F04-99D1-45CD-A9BF-177BE55FAF81","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a47acd96d47df97d61b5afb072af3d1d40768588","datavalue":{"value":"10.1016/J.DAM.2011.12.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q423933$588A54F3-4B66-447F-A0A1-54B4365CD101","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7ce643f96655b053aeea327cbf0128450ab2797","datavalue":{"value":{"entity-type":"item","numeric-id":300968,"id":"Q300968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$DFB18FD7-C5FC-434C-940D-C6DABEBA55EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c776795cdde5f51b3c300f0b87440aed88df58e1","datavalue":{"value":{"entity-type":"item","numeric-id":162228,"id":"Q162228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$B7060D1A-5C76-4671-A820-E8948A0F07F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"71c1c3a14ff20c3a61bad2960ecd14fab5082449","datavalue":{"value":{"entity-type":"item","numeric-id":850245,"id":"Q850245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$E2C26964-3F61-4131-9695-94CC2E7720E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d70565714f38c0cb96e85c14fdd2dbb0790eda0a","datavalue":{"value":{"entity-type":"item","numeric-id":215029,"id":"Q215029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$3311B95C-A995-49F1-8F15-854E26F8F9D0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fc863a2cd992e8405d2d2550732c1a1380055274","datavalue":{"value":"Scheduling algorithms are approximation algorithms which assign jobs to the execution units of a machine such that a low overall processing time results. Due to the different nature of jobs, machines or information available, there exists a large variety of specific scheduling problems and each problem requires its own scheduling algorithms. In this article, a specific scheduling algorithm is proposed together with theorems and proofs concerning its quality. The contents is very well described by its abstract:NEWLINENEWLINE``We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio \\(\\approx 1.828\\) source, which improves on a 2-competitive on-line algorithm for this problem in the literature.''NEWLINENEWLINEThe article is written in a mathematical and formal style.","type":"string"},"datatype":"string"},"type":"statement","id":"Q423933$7D880B1E-691F-4834-A03E-EEE988B7216D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6df8df5cc882f061094d94b8ada6643a823409c7","datavalue":{"value":{"entity-type":"item","numeric-id":362569,"id":"Q362569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q423933$2AB18940-7A33-413E-829F-DEAB0E2C669E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b13ffe8b2e913af0f05760c5c808c965b368d6c6","datavalue":{"value":{"entity-type":"item","numeric-id":719274,"id":"Q719274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0441d798bed879d6b0128e8fb1156fd2a223a82f","datavalue":{"value":{"amount":"+0.9422566294670104","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":"Q423933$8D30A3DB-9EDA-46F8-8017-3BAC8E4A06C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32eed9f8d23e0b9e1cf02bab497a98befcb03d6f","datavalue":{"value":{"entity-type":"item","numeric-id":841603,"id":"Q841603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa7d78eea25922014cb84cc411124b363983a46e","datavalue":{"value":{"amount":"+0.937401533126831","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":"Q423933$A48B1A10-715A-4F79-A0BF-9C38FDA55B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4daf60c7f16e9206429f481d9162b4ce35d282f","datavalue":{"value":{"entity-type":"item","numeric-id":1944199,"id":"Q1944199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40dfbb830895fee8fb5f12d1b251cdc7f61f3b60","datavalue":{"value":{"amount":"+0.9279341697692872","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":"Q423933$76E30E67-EF3C-49EC-933A-F722167502A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"027aeb903c68a3d86fe1b286e3b99d128d8ba1f6","datavalue":{"value":{"entity-type":"item","numeric-id":1022586,"id":"Q1022586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2294365e13ef4c88c01c7aaaf933ebd8e052b66a","datavalue":{"value":{"amount":"+0.9208399057388306","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":"Q423933$AECAAD03-BF88-4D29-A0A8-DC29A678B0A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b07e50ca7376ebe576bec7db629e54d1f4b93f48","datavalue":{"value":{"entity-type":"item","numeric-id":4925230,"id":"Q4925230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c03c5324baf7f2a4cc0a67c616364a22fe1b640d","datavalue":{"value":{"amount":"+0.906472146511078","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":"Q423933$586A7C32-46D3-4FB6-8B4A-1A1192FE4CDD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:423933","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:423933"}}}}}