{"entities":{"Q2468842":{"pageid":2479585,"ns":120,"title":"Item:Q2468842","lastrevid":50271827,"modified":"2026-01-13T17:19:57Z","type":"item","id":"Q2468842","labels":{"en":{"language":"en","value":"Duplicating in batch scheduling"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5234142"}},"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":"Q2468842$03D6BC69-83A4-4B1B-B678-99A9B813489A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c2b90af4cbcd300cbfe8fe6fd96d2a09b5cf4143","datavalue":{"value":{"text":"Duplicating in batch scheduling","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2468842$CAEEFD55-E9CD-41CB-BCC6-DE86E49A3302","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d06e7c1a1102a8e4be255ce11abf0b7550866360","datavalue":{"value":"1166.90343","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2468842$4AB20024-BEF0-4C4F-BAE4-ACDF546141D8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac5d057859dc3e4a3c89f791480b89a12daf239c","datavalue":{"value":{"entity-type":"item","numeric-id":903375,"id":"Q903375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2468842$A574F87E-4C1F-4E84-9DBF-5CFADAA34F11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"831421abda5f4c2eca3763d39e99e4605077a4d8","datavalue":{"value":{"entity-type":"item","numeric-id":1721409,"id":"Q1721409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2468842$898E4986-17F8-4DBB-9F33-64188E3D955E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15dd0018ac59f3b22411758ee094f38fe0d273ac","datavalue":{"value":{"entity-type":"item","numeric-id":402365,"id":"Q402365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2468842$D7A01E9D-1CE8-4AD6-B7B2-E943CBFC662F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1c66f06955d7bd871dfd08914b88e36b16fafdc","datavalue":{"value":{"entity-type":"item","numeric-id":519219,"id":"Q519219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2468842$8F1F3F1F-C05B-4E52-AD2D-78AB3EEC2E99","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e44f3e93d903de82a8fbed99c0811e7cd35baeba","datavalue":{"value":{"entity-type":"item","numeric-id":380453,"id":"Q380453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2468842$8DCB0238-3349-465A-BE7E-803CCC942891","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e4800927b07ccd6fb9363320f84dd69946198de8","datavalue":{"value":{"time":"+2008-02-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2468842$A9AEC540-3621-433B-973F-053D11445692","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"28ecdf13b45056d3c37f7edee07f28a6147a8589","datavalue":{"value":"In this paper, we firstly propose a technique named Duplicating, which duplicates machines in batch scheduling environment. Then we discuss several applications of Duplicating in solving batch scheduling problems. For the batch scheduling problem on unrelated parallel machines to minimize makespan, we give a \\((4-\\frac2B)\\)-approximation algorithm and a \\((2-\\frac1B+\\varepsilon)\\) algorithm when \\(m\\) is fixed. We also present a \\(4(2-\\frac1B+\\varepsilon)\\)-competitive algorithm for the on-line scheduling problem on identical machines to minimize total weighted completion time by another technique-\\(\\rho\\)-dual, which is proposed originally by \\textit{L. A. Hall, A. S. Schulz, D. B. Shmoys} and \\textit{J. Wein} [Math. Oper. Res. 22, 513--544 (1997; Zbl 0883.90064)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2468842$AE5235A8-C617-4843-94EF-51841F809532","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2468842$1F74193C-8F09-414B-95A8-18E526B02C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2468842$E82353F5-C4FA-4CCA-99BD-2E1E99374776","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"12688639c66cca4762733a2ef61d4cff19da96dc","datavalue":{"value":"5234142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2468842$EFDD434C-EE40-4F78-A4D9-D15E98B2FAC5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2468842$DE1FF020-E9FD-4171-A40E-F172E0256291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2468842$CCD6E3C9-34CA-47F1-99E6-DFB655AADA51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2468842$B8116FE1-2D59-4067-8384-C22B0DA4EC28","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":"Q2468842$82BCD921-A9A6-4717-BB76-E13FBB55DC18","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"583f495b7f5502fccdd5ed1e9c2257a0822cfcc7","datavalue":{"value":"https://doi.org/10.3934/jimo.2007.3.685","type":"string"},"datatype":"url"},"type":"statement","id":"Q2468842$3D2B2851-97CF-4148-85D9-EC1CC78C163A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7c6798590d76f214666559700f3e6fcf039816f1","datavalue":{"value":"W2323692952","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2468842$AC6A83C3-C767-45E7-9289-DF08F25E82B8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5323d178c7572a765d960513c4a09ba21f37cf0c","datavalue":{"value":"10.3934/JIMO.2007.3.685","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2468842$D8F9ECDA-457F-4DA0-9D16-0728662132F2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8170e353964348355aca9c2e47b70d0365811834","datavalue":{"value":{"entity-type":"item","numeric-id":5453051,"id":"Q5453051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"160af2fc90d5716e099e23bd5907c2e8d4ff8c82","datavalue":{"value":{"amount":"+0.7855074405670166","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":"Q2468842$FB284188-F0AB-459D-90B7-E87C3FC496DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7456136474f0009c441a73cfbe2a9584e68a78e","datavalue":{"value":{"entity-type":"item","numeric-id":957356,"id":"Q957356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"472ed86f9ce40f7aa2e2f96796f17fbd1d66d042","datavalue":{"value":{"amount":"+0.7849193215370178","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":"Q2468842$E832A633-2E26-4897-AD82-3712D99F7DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73540f0f2421ac71de70b4e54ca1e37885f2eba5","datavalue":{"value":{"entity-type":"item","numeric-id":4472513,"id":"Q4472513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"492ef0775b0a5be9d88da9bb6c15a3b08a327065","datavalue":{"value":{"amount":"+0.7840079665184021","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":"Q2468842$6A6FADC6-37EC-4C37-A35D-E8C34B7438D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0391e7ba0cc4a606e7bff2b4faf3c8d16441b24c","datavalue":{"value":{"entity-type":"item","numeric-id":1656199,"id":"Q1656199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09cea6874cbdb8eaad81f664655d5f9904eea1a8","datavalue":{"value":{"amount":"+0.7834106683731079","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":"Q2468842$1410D152-CAE4-47A1-B37A-192BFEBA7D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ad4a502f073aecaa98dd924b30d2b8cc112bc00","datavalue":{"value":{"entity-type":"item","numeric-id":1882631,"id":"Q1882631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2644fc956a650d0ae2178883fd14719bc11d56b1","datavalue":{"value":{"amount":"+0.780353844165802","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":"Q2468842$520C7A5D-83F5-40E6-A129-7EE991DAFED2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2468842","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2468842"}}}}}