{"entities":{"Q1179195":{"pageid":1189944,"ns":120,"title":"Item:Q1179195","lastrevid":69811740,"modified":"2026-04-13T09:33:23Z","type":"item","id":"Q1179195","labels":{"en":{"language":"en","value":"Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 24117"}},"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":"Q1179195$6635508C-4928-43D1-AFDA-A410505102DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ac2be6c4abc2b29bd240779dc3e4c4af60e4339","datavalue":{"value":{"text":"Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179195$8EE86864-6B22-4836-98D0-82C820C452CB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bfc54865a85c8e2e38f037063bcda4ed3ec1985e","datavalue":{"value":"0741.90038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179195$5DD5C9A8-C1DA-48BD-91D5-0EB69ABD477F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"abda156d7ecb710c3926a027898c19565ab8dbdb","datavalue":{"value":"10.1016/0377-2217(91)90250-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179195$CD993B88-CDDC-4AB3-97F7-C741C9452955","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac05114ba19da03d2c5d80abdf4db552bc715014","datavalue":{"value":{"entity-type":"item","numeric-id":1065704,"id":"Q1065704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179195$81CEAF0B-6E44-4F9B-8E58-9A4163B3F816","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179195$BDF1D104-7E88-46AE-96F3-286DDDA56274","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1179195$B262E847-5DEF-4BA9-9E3F-CA8E4998F23D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9ad11e2b0dd3c03d6da2823934c08e3e210b99a","datavalue":{"value":"The author considers the problem of minimizing maximum delivery time on a single machine under the assumption that the set of \\(n\\) jobs is partitioned into batches and a unit set-up time is associated with every switching from a job in one batch to a job in another batch. The problem is known to be NP-hard [see \\textit{J. Bruno} and \\textit{P. Downey}, SIAM J. Computing 7, 393-403 (1978; Zbl 0386.68050)]. Here, three polynomial-time approximation algorithms are presented and their worst-case behavior is analyzed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179195$75AB580D-D81F-40DC-A848-2B658814817A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179195$E6379A33-DDBD-400E-9467-6EEEC8C39516","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8136c71f0115e3eaaee4153e96bb5893b202c946","datavalue":{"value":"24117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179195$F3C0C965-A4A2-4639-BE1E-168D0E93BE6D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc5d263d0c5e9e0e8d9380c29b0aac561b81f31f","datavalue":{"value":"maximum delivery time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179195$65E02FAF-3498-43BA-BC40-C8E460A19791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1ca53a04f8c624238a62137bcb0acb8058cd7ee","datavalue":{"value":"single machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179195$60E81950-B5FB-47EF-A717-D8564BAA7199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8e109b6de1349a57994e690a195a32f5bb9b7b4","datavalue":{"value":"unit set-up time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179195$B3560477-79C8-486C-A870-FBDDAAA64B94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179195$B7EEFBFA-C110-4E07-8185-3F45E1F6ABA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d3c7940bc375be33dc4e18a484afe173830b4f3","datavalue":{"value":"polynomial-time approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179195$84EDEC44-7EEB-47A4-8B49-9AD82AEF1705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84da93b2d5f45a9347fafdc03b0b5f74af0d84c2","datavalue":{"value":"worst-case behavior","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179195$6EA15A15-0981-4333-BFF3-2739FF77B147","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1ba4a6e46d39a41518db65f4f97cbfd2a0693778","datavalue":{"value":{"entity-type":"item","numeric-id":238069,"id":"Q238069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179195$83A05F9E-F4F0-4E58-AB78-6DBD8E73805B","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":"Q1179195$C1B7E88E-531E-43C6-9D09-4157F7E08404","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"947bab426625048ec240ec204ddc70202132f16f","datavalue":{"value":{"entity-type":"item","numeric-id":4167580,"id":"Q4167580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179195$7F668BFC-014F-4879-A668-D4F6438B4BD4","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":"Q1179195$6D9C4BB0-8BF3-4814-810C-E0D3091881E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ad7ced05e0b3593fcfa0932bd21860f0e19e123","datavalue":{"value":{"entity-type":"item","numeric-id":4205231,"id":"Q4205231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179195$21C7831C-132C-4DE4-AB3C-A7B5290221B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eddecf9b06ea7288ca58a7666320441adbe28f47","datavalue":{"value":{"entity-type":"item","numeric-id":3879034,"id":"Q3879034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179195$6C3713F5-E3CD-43EB-A456-E603B66FF6C1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a1a5b5dae8dfd4d18391f02833737e14083a6b5b","datavalue":{"value":"https://doi.org/10.1016/0377-2217(91)90250-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1179195$11CC093E-1F8D-48DF-B8E3-865D6D639774","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6847f24563fd33625cbda214644e2478dccce8e7","datavalue":{"value":"W1975973671","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179195$4C0F1617-88F1-422D-8090-433FB21A5E59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b935680437fb8f42547bb97090d915faabfc46a7","datavalue":{"value":{"entity-type":"item","numeric-id":3486355,"id":"Q3486355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c073d4711b29930c9abfb9d08276edacf8b90200","datavalue":{"value":{"amount":"+0.911144196987152","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":"Q1179195$83D80C9F-A89D-4FAB-8B84-7F1B274C692B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d278604f497a7db71f1855cedc9c91383ca547b0","datavalue":{"value":{"entity-type":"item","numeric-id":1268839,"id":"Q1268839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a48157f0246aace4824b88114e256cc9378d9ad","datavalue":{"value":{"amount":"+0.9107388854026794","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":"Q1179195$0256F497-CBDD-4320-B384-230A735ABD67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f73e673939182dbb80cf794bede122a48613e4da","datavalue":{"value":{"entity-type":"item","numeric-id":4319788,"id":"Q4319788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efe7358083ed863efb1fc92272c01ddfce55775f","datavalue":{"value":{"amount":"+0.8415834307670593","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":"Q1179195$2F68AE89-0704-48B2-A7A0-863C986FC34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fad4b3c8a0c878e88e0ece4ab4fe6f0b5bf5111","datavalue":{"value":{"entity-type":"item","numeric-id":4526946,"id":"Q4526946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f54784b3a6287b5bfc18271954d6f17ca84ee833","datavalue":{"value":{"amount":"+0.8346633911132812","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":"Q1179195$3C863DCC-5A24-489D-90C4-37FF34527367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e097623434052d1a26d97cb75345f144f80523d","datavalue":{"value":{"entity-type":"item","numeric-id":1768605,"id":"Q1768605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e741980e573cf794e66b62cdcb5c06aa9177fad4","datavalue":{"value":{"amount":"+0.83316570520401","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":"Q1179195$A4ECEB24-994F-4CB3-9A81-6CC7411CA608","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithms_for_single-machine_sequencing_with_delivery_times_and_unit_batch_set-up_times"}}}}}