{"entities":{"Q995579":{"pageid":997427,"ns":120,"title":"Item:Q995579","lastrevid":65779557,"modified":"2026-04-12T05:18:38Z","type":"item","id":"Q995579","labels":{"en":{"language":"en","value":"Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5186618"}},"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":"Q995579$04BE9502-C7F3-4FFB-9127-DD3A398D3794","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0b43a1c964bdbf99ead867ba7de626d6133f7637","datavalue":{"value":{"text":"Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q995579$74314167-D200-4DE7-8C86-0EFE026EFDAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a5d54cecf6d566c58fa649d1bf4b3267293ad94a","datavalue":{"value":"1206.90043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995579$A63DE191-1DBA-423D-8516-112E9B5221FB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"946657af101e201809d3162fa6bc03957d5d1691","datavalue":{"value":{"entity-type":"item","numeric-id":262443,"id":"Q262443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$D2052243-ECBE-4661-9E7F-58DE19A62795","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":"Q995579$65C848C1-C8C5-40E1-B2B3-A15C55C276EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7a60909d1c148a53c40db1baa3543530a5558fa","datavalue":{"value":{"entity-type":"item","numeric-id":176697,"id":"Q176697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$DBE72DC7-B87A-49F2-9D40-3C14A7EB3FA1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$CC044E02-DB6A-4264-A95C-9558D2741D7D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d4ccb5809271d2f0bf96f65b85084aa847fe92ef","datavalue":{"value":{"time":"+2007-09-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q995579$7EDA1A53-7480-4DCA-AAE1-D0C22CB67E60","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"637173a65405971cc9d59842b573989b03134eb5","datavalue":{"value":"This paper studies the bicriteria problem of scheduling \\(n\\) jobs on a batching machine to minimize maximum lateness and makespan simultaneously. The authors consider the parallel-batching model in which the jobs that are processed together form a batch with the same starting time and completion time, and the processing time of a batch is equal to the largest processing time of jobs in it. A parallel-batching machine can handle up to \\(b\\) jobs in a batch. The authors analyse the unbounded model in which the number of jobs in each batch is unlimited, denoted by \\(``b\\geq n\"\\) in short. Based on the result by [\\textit{P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. N. Potts, T. Tautenhahn} and \\textit{S. L. van de Velde}, J. Sched. 1, No. 1, 31--54 (1998; Zbl 0909.90172)], the authors show that for the bicriteria problem under consideration one can order the jobs according to the well-known SPT rule and then form an optimal schedule, specified by the jobs that start each batch. In the paper a dynamic programming algorithm (DP-algorithm) is developed to find a Pareto optimal schedule for the bicriteria problem. The running time of DP-algorithm is \\(O(n)\\). To generate all Pareto optimal solutions, a basic method is the so-called \\(\\epsilon\\)-constrained approach (see \\textit{H. Hoogeveen} [Eur. J. Oper. Res. 167, No. 3, 592--623 (2005; Zbl 1154.90458)]). Using this approach and the DP algorithm, the authors demonstrate how to produce all Pareto optimal solutions to the problem under consideration in \\(O(n^3)\\) time. The number of Pareto optimal schedules for this bicriteria problem is proved to be at most \\(n(n-1)/2 +1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q995579$FBEEAE84-52E3-4BC6-B617-2380A61D4306","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995579$D6D57AE9-804F-4DCD-9E0E-D29B72093297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995579$87516264-722E-4154-9EFC-098DBCFB229B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"304d76723333cac76cdf237e257d18a861e1fb31","datavalue":{"value":"5186618","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995579$AAD3B0B3-6F38-4A65-A81C-CB27B0014635","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"012532a18d8733d390a51206f2d53a0b0a1b1f6a","datavalue":{"value":"multicriteria scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q995579$B1CB2547-A6B6-40BA-896F-7C76C08F88BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97a3e81a52b51bd197022044d5af0e9e562654e5","datavalue":{"value":"batching machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q995579$9BFCA6F4-56A1-4CEC-96D1-8FB96BF89331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d16cc5a85aeee9b68b2e66907bf512d1671f689","datavalue":{"value":"maximum lateness","type":"string"},"datatype":"string"},"type":"statement","id":"Q995579$A71E4A96-3F42-4A06-89DB-09AFBEC48C50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88287ae1e5ff19619095f2b01a97004beb3cc988","datavalue":{"value":"Pareto optimal solutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q995579$55A9AC1B-65A3-446C-B3E8-E1254A6EF8DC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a3577ca3df4bfacea4e2f2b1a9a980c70611b787","datavalue":{"value":{"entity-type":"item","numeric-id":439606,"id":"Q439606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$88157917-171B-432F-8E63-9CD35D6AAC1F","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":"Q995579$872B90F6-5D6B-41D3-967A-60CDBE722932","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e23354a3eb9eded0855e5dd87f35f98cd95de209","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2007.04.034","type":"string"},"datatype":"url"},"type":"statement","id":"Q995579$916F74BB-A8FA-4678-9027-D77DF4D723E8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cb715927ccc322f6df7594c10881f909223b924f","datavalue":{"value":"W2018793254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995579$1E222175-3E7B-4CBF-AE3A-19FEEA88BE71","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c11c623fc92ffc5911bd76a8fae8500b791774a","datavalue":{"value":{"entity-type":"item","numeric-id":3637420,"id":"Q3637420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$AA85E96C-9FBE-4C41-9F37-3F7034F52F52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"257342bf65f6149a7d51140283bfe30d953d5c50","datavalue":{"value":{"entity-type":"item","numeric-id":1268850,"id":"Q1268850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$CA408E3D-315C-4A22-8D01-1E97A1EB68B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"661e19aae08caab5ac91a3e9c25574dd2b7148fb","datavalue":{"value":{"entity-type":"item","numeric-id":2464375,"id":"Q2464375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$9AF49649-6A8C-4E7F-B2ED-00076D743668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d862f6471ed29c549efca1a8279194b1dd62987","datavalue":{"value":{"entity-type":"item","numeric-id":2734595,"id":"Q2734595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$1598F1AF-A237-4495-A4EE-6F9998130B07","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":"Q995579$8AC119AB-FF61-4ED3-BE3B-22E7ABEA2BFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1de75085269146fc0acbd46c7357d633d9732d88","datavalue":{"value":{"entity-type":"item","numeric-id":2566699,"id":"Q2566699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$D9F1E151-86C0-4E21-B4D1-AF7AD04CC603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9451258fe41e7dcf727e8e6611f1c7a494e957a9","datavalue":{"value":{"entity-type":"item","numeric-id":4895811,"id":"Q4895811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$08869C07-F315-4FBE-88C4-B2CE887EC4CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df619fa2660271ead4e263e8556654a9ceb9c922","datavalue":{"value":{"entity-type":"item","numeric-id":1924612,"id":"Q1924612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q995579$8BE571C9-3B31-4672-8E93-FE860268C707","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51f1fbbcce373e639366398d9eb82e497aee528d","datavalue":{"value":"10.1016/J.TCS.2007.04.034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q995579$F41445D5-3284-41DE-8C80-1FECB4DC9583","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2c0304a3f5ec7a4bf8b26a8973c5e66506562d9","datavalue":{"value":{"entity-type":"item","numeric-id":3070927,"id":"Q3070927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f0db988e2aa14b6f87cd29c2e4715af27b48ff4","datavalue":{"value":{"amount":"+0.92644703","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$D7313190-CB50-4CF2-8EC6-2F4AE2F956F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45bd9acef9991f1cb5ee163d8c0c7a1900b3d1cc","datavalue":{"value":{"entity-type":"item","numeric-id":1751110,"id":"Q1751110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a8ca4168d11d7430ceb249e1d565157a35e891b","datavalue":{"value":{"amount":"+0.8903306","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$0648AEAC-C4FB-4B34-A6BE-DDA3CF969896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5c61daf60e8f3608b8f1242935597a042853c3e","datavalue":{"value":{"entity-type":"item","numeric-id":300969,"id":"Q300969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f0b18de3199cdc015b6a67ffb2c1d1333064142","datavalue":{"value":{"amount":"+0.88443244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$15F9035D-7D82-4267-93EC-3F4DBBDD49FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29b03f2a1fb542645bd0ea4fbf9ebbd1d3bc4a72","datavalue":{"value":{"entity-type":"item","numeric-id":6041237,"id":"Q6041237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b7668fb337a1b1df9df750814aa9d8eded6c1c7","datavalue":{"value":{"amount":"+0.8837","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$13F6EC86-5ECE-42AC-B6AB-61846DBFBA18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"976a98dedb688bcf9a77923333f45b7d66a8ae5b","datavalue":{"value":{"entity-type":"item","numeric-id":2680241,"id":"Q2680241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"288283cd78bf56a2b2423ff8f2babec8edc84e9e","datavalue":{"value":{"amount":"+0.86995316","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$0F2239C4-6CBC-4C1E-B66F-4994B88CDD94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"448cbacff7bff289f767531794a90b9660914bdc","datavalue":{"value":{"entity-type":"item","numeric-id":2931723,"id":"Q2931723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2768967681b626506a9e50bb145b19a0c8bb4bfd","datavalue":{"value":{"amount":"+0.8659134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$D5AC49FA-7140-4565-B18A-F268654D12C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aea2ee71c86d3eba085017ef423ba56f42f7542f","datavalue":{"value":{"entity-type":"item","numeric-id":987835,"id":"Q987835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e782916eb7c2fe6db293f4cb4fb62a85a4fdd907","datavalue":{"value":{"amount":"+0.86506575","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$BE92370F-833A-4AA8-8D77-32C80F83EA01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d7df97cd9b1c4f1bded435aa7a6bf840e16ce15","datavalue":{"value":{"entity-type":"item","numeric-id":3778533,"id":"Q3778533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35f0f201a08cc65ac6766d1a7c4a0f18460dd3cb","datavalue":{"value":{"amount":"+0.86142766","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$FBC8FF49-DFFD-4392-A605-581B5704CF4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"457a29cd79d6340c8368087abfbbef49a6350fba","datavalue":{"value":{"entity-type":"item","numeric-id":2845028,"id":"Q2845028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c8483109c98119f90a6d443574f1bc2f8031d5a","datavalue":{"value":{"amount":"+0.8595291","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$6E8BD757-229C-4D3D-BB1C-53F19A059C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95d09b0d10774c4385f854959008f81c5169687f","datavalue":{"value":{"entity-type":"item","numeric-id":3405330,"id":"Q3405330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c195c03b2bcaeea3e388f5b982d7390f4c54006d","datavalue":{"value":{"amount":"+0.85152745","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q995579$26270F54-3C44-40E6-94DE-8FB2EAA7027F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bicriteria_scheduling_on_a_batching_machine_to_minimize_maximum_lateness_and_makespan"}}}}}