{"entities":{"Q1338896":{"pageid":1349635,"ns":120,"title":"Item:Q1338896","lastrevid":68500599,"modified":"2026-04-13T00:07:44Z","type":"item","id":"Q1338896","labels":{"en":{"language":"en","value":"Heuristics for parallel machine scheduling with delivery times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 695004"}},"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":"Q1338896$58A7FD99-B994-48F0-A825-AF0343B8BAF1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e88dc972e04cd4d433c682295234b33ce7c2185","datavalue":{"value":{"text":"Heuristics for parallel machine scheduling with delivery times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1338896$8353D572-F5D2-4C57-B7EC-48A12C74B809","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e750ede93224da2c51b82ad5c3f5646b5810607b","datavalue":{"value":"0818.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338896$187B6950-41EA-468E-8EC8-C9C5A608764F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5f2341dcac21345deacf66cd290488256aa4bfc7","datavalue":{"value":"10.1007/BF01213203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338896$36957012-40C9-44BA-960D-BAC572FCE913","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a99c5b7728e1965ef01019ed8fae6583a2f22e4","datavalue":{"value":{"entity-type":"item","numeric-id":170010,"id":"Q170010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338896$29373F18-E42A-49A5-85A6-95B3A2FE6EC2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338896$546B655F-3CF4-4E9C-AA42-7359A2A74508","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3816e5ad4c8d1e2e98cee6e1e740e168fa32f19b","datavalue":{"value":{"time":"+1994-11-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1338896$AB405CD3-EC5E-4C9D-B7A6-1E385160EA3D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a035a4eb52c3f8c08d4753b74dd001bf2c94eebc","datavalue":{"value":"A parallel machine scheduling problem is considered in which each job has a processing time and a delivery time. The objective is to find a schedule which minimizes the time by which all jobs are delivered. For a single machine this problem is easily solved in polynomial time, for \\(m \\geq 2\\) machines it becomes NP-hard. Several heuristics using list scheduling as a subroutine are proposed and a tight worst-case analysis is given. The best one of our heuristics has a worst-case performance guarantee of \\(2 - 2/(m + 1)\\). For the on-line case we give a heuristic with the (best possible) worst-case performance of two.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338896$751A7555-1CB0-4557-9DCA-0D8320EACFCA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338896$72566C66-E238-4DA9-8D27-0C57400857B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338896$071E503F-7135-49D6-A519-FCD3D125C36D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e68b636f5fe189551ff6f5ae48bf1df793e243c0","datavalue":{"value":"695004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338896$D710D495-791A-41F8-84F4-B77792423C07","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01768ba8b6bf78e7c3dea4e88b2aee1c86740f4a","datavalue":{"value":"identical parallel machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338896$AB994CE2-C24C-43F2-9DD6-F2C95EB2B33D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e4c4a08a9ec69f58dcc487bba01bd49401804d3","datavalue":{"value":"parallel machine scheduling problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338896$08B7E908-901C-413D-A120-4FBCFDD46666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89be3be00803201dd21b57bb6aacdf87d1707caa","datavalue":{"value":"delivery time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338896$E3F21708-5C19-499A-9C88-3CBCA371AD78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338896$49C2C009-605E-4ED5-BDC6-A1FFB8C8AFC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14f5692e185b1488dd97e357834d4b024a1d4fa4","datavalue":{"value":"worst-case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338896$F64D0C5B-EA6D-4A1E-B06B-6705E3FDE743","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":"Q1338896$3E77BACB-D1CA-4EB8-91B5-677FC8922C44","rank":"normal"}],"P223":[{"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":"Q1338896$AE958E1B-0215-4EEB-8AB9-384C1FCBEC5E","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":"Q1338896$1B953030-0BC8-4D06-BF39-19B20C05E30E","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":"Q1338896$DABD6C46-1FF9-485E-B09B-0B12F4F1B586","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":"Q1338896$744C9A7B-6FCB-460C-9A36-4D136F3796CE","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":"Q1338896$970EBB86-3E05-4B49-828E-DAFF37E794BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e8f5fdd7bd82e2d3ffd63779bd9ac47d7f91caa","datavalue":{"value":{"entity-type":"item","numeric-id":4016707,"id":"Q4016707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338896$BEB68180-DBE9-4E90-8760-28973BBD2FF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09abae86cc1ed38b7527e20b0a54f0f51ad25c1f","datavalue":{"value":{"entity-type":"item","numeric-id":1099951,"id":"Q1099951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338896$96C9BD55-F1C4-4C80-A042-3969A0AACC8E","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":"Q1338896$1EF8835D-C772-4F0A-AFEA-C55AFE3AE632","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3c6a2aa10dd607ed7e2e12284cf3b820b5afd045","datavalue":{"value":"https://doi.org/10.1007/bf01213203","type":"string"},"datatype":"url"},"type":"statement","id":"Q1338896$E676C09A-33E2-45B0-9492-C9CE05294A75","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"10c3176e010790abe069d80b52592cfea81743bc","datavalue":{"value":"W2007044196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338896$2C05829D-F9AB-4DDA-A20A-C9402C6BA2ED","rank":"normal"}],"P1643":[{"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":"a060c53e9c56ccd399e5cac53d90889a0f8c7b6f","datavalue":{"value":{"amount":"+0.8747236132621765","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":"Q1338896$11BBFBED-5313-4A05-8456-11816A32E2E4","rank":"normal"},{"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":"d2c3539f01ce562757ccb5880ca37a26aa6b1b5b","datavalue":{"value":{"amount":"+0.8739724159240723","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":"Q1338896$3EC000CC-ED91-4C1B-9A32-87151D87C4E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf64376cc9bc03174cbec541393f91955d494c0a","datavalue":{"value":{"entity-type":"item","numeric-id":2296256,"id":"Q2296256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc64a8893d974b93c299df4f38988625d8e3edd3","datavalue":{"value":{"amount":"+0.872776210308075","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":"Q1338896$7CB198CE-1810-4097-8A9D-A0400BFF156E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"779f4ceea88ffed0024a2b0a83693b68609077d0","datavalue":{"value":{"entity-type":"item","numeric-id":1061599,"id":"Q1061599"},"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":"Q1338896$E0B179B4-A3E5-4301-A83C-6D7B58067855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ec1b80714108606a176dbac1e733527f3441910","datavalue":{"value":{"entity-type":"item","numeric-id":5370785,"id":"Q5370785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3088dc451af3e864f54642358a6c03b3ae619e3","datavalue":{"value":{"amount":"+0.8467820286750793","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":"Q1338896$2D1D6FD8-07C9-4F37-911B-4D8B0BA8CB92","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Heuristics for parallel machine scheduling with delivery times","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Heuristics_for_parallel_machine_scheduling_with_delivery_times"}}}}}