{"entities":{"Q1821023":{"pageid":1831765,"ns":120,"title":"Item:Q1821023","lastrevid":43347860,"modified":"2025-07-24T23:55:43Z","type":"item","id":"Q1821023","labels":{"en":{"language":"en","value":"Reversible-shop scheduling"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3997538"}},"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":"Q1821023$3646079C-437A-4762-A1F7-83019647E14D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fcb872ead2d2d88823c8fc7ba99bced5acb6edfb","datavalue":{"value":{"text":"Reversible-shop scheduling","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1821023$7B22DDF7-4E94-4B3B-BDBD-06CF5FCD22D5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ad7cbe45c91afc5d1056563ef7253f89923210dd","datavalue":{"value":"0615.90060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821023$D9608277-BC50-4A53-BDA6-081B174F0895","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ad434218c0eb2cdcb312f7aba600e07cb072253","datavalue":{"value":"10.1016/0377-2217(87)90197-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821023$7738F17B-5383-4EAE-A7DD-67248895C882","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0e82da88dd0b9baac90ad1e8f93eee8e35c9d22","datavalue":{"value":{"entity-type":"item","numeric-id":1821022,"id":"Q1821022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821023$F3F645CA-FBC8-435F-B9A9-3A0D0E22AA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"73c276f9bfa07a13cf31558f7a066ce86709bb49","datavalue":{"value":{"entity-type":"item","numeric-id":795723,"id":"Q795723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821023$4D6D923C-F954-4E00-AF07-915F41D9473B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ed112921449c1b8aea35108e135e26eaa72299f0","datavalue":{"value":{"entity-type":"item","numeric-id":1111017,"id":"Q1111017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821023$2AB57290-42DB-40AA-B10F-A85A046A020A","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":"Q1821023$F14CBB1E-7445-4110-88F3-A906456B5DF4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1821023$DE8A9856-65AF-4FF4-96AD-9DC045A12EB0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f84f3f0f4232db4c4b021b86b9d34c2864408322","datavalue":{"value":"The concepts of reversible-shop and route-dependent reversible-shop are defined. In a reversible shop a job is processed on the machines in a given order, say \\(M_ 1,M_ 2,...,M_ m\\) or in the reverse order \\(M_ m,M_{m-1},...,M_ 1\\). The processing time on each machine is independent of the route taken by the job. For the route-dependent reversible shop the processing times differs for each of the two routes. For two machines the reversible shop is an open shop. It is shown that minimizing the makespan for a reversible shop with 3 machines is binary NP-hard. Efficient algorithms are given for some special cases involving dominating machines. Machine \\(M_ k\\) is dominated by \\(M_ r\\) iff the maximum processing time of an operation on \\(M_ k\\) is less than or equal to the minimum processing time of an operation on \\(M_ r\\). Efficient algorithms are given for the 3 machines \\(M_ 1\\), \\(M_ 2\\), \\(M_ 3\\) where \\(M_ 2\\) dominates the other two, or \\(M_ 1\\) dominates \\(M_ 2\\) and \\(M_ 2\\) dominates \\(M_ 3\\). When all processing times are equal to 1 for an arbitrary number of machines efficient algorithms are given for minimizing the makespan and minimizing the sum of completion times both in the case of infinite and zero storage space between the machines. For route-dependent reversible-shop with 3 machines an efficient algorithm is presented for the case machine \\(M_ 2\\) dominates the other two machines \\(M_ 1\\), \\(M_ 3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821023$F4ACFFC2-9FD8-49CD-870A-802F4AE96B7E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821023$8BFDA539-FBCA-4699-8D4A-CBEF0DDD80E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821023$DB3D8108-539B-42E2-A12F-15E2D3827E95","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1a8d92e3ddfbb82b514450ebf30f1b349bd136b8","datavalue":{"value":"3997538","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821023$085CDC85-BC41-48D1-84DF-F831243B2D5A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25b44e6c20b6b0ec2601e92830bb95d7827f9cd","datavalue":{"value":"reversible-shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821023$7B7761AF-AF4D-4123-A647-E6DE9FA7C36C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28a6f26af86dd2f2f1917280f919b8ad3d524d69","datavalue":{"value":"route-dependent reversible-shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821023$3F47D768-8765-4124-BF0B-E1627B3E5DA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821023$03253216-D7A7-4951-9D6D-2F24D979BBA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a7a0ee40117b3ffad7d160dd84041d71eaa9084","datavalue":{"value":"binary NP- hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821023$D8C427E0-C506-44FF-9589-D6BE7F086050","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":"Q1821023$AF394460-106B-4592-BD68-D9B0A5A480F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f15c90572fb6e31b9f6cd0d0ed3629242c43380e","datavalue":{"value":"https://doi.org/10.1016/0377-2217(87)90197-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1821023$FB8CB12C-6DDF-4E4C-A990-B358728BC851","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dfb3f2c2f5371d77366248bb0f82e25cf4cdbaba","datavalue":{"value":"W2080906250","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821023$FFF0AEE2-9C84-466A-A8A7-262958D51B27","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bdb27d2bbe345b9cd8347ca62925f13d80b4745","datavalue":{"value":{"entity-type":"item","numeric-id":3954823,"id":"Q3954823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821023$A6580714-2A9F-46AA-95AE-C831CD25319D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfbd785c98ffff9164411c97d0cfacab892ef9ed","datavalue":{"value":{"entity-type":"item","numeric-id":4111095,"id":"Q4111095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821023$9C54170C-1893-4E76-9BB2-492E70393FDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdcd526725f29c306d768e61c2cba0a5fc0c2ed7","datavalue":{"value":{"entity-type":"item","numeric-id":4742542,"id":"Q4742542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821023$05CEF9B4-B338-4DBB-8BFF-DD1D3E78AA5E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"996b80f17785ef919aeb6dc4245d339d566bb114","datavalue":{"value":{"entity-type":"item","numeric-id":319298,"id":"Q319298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c5f57277d472ffa4929e02f3ecf40c823f8b9d5","datavalue":{"value":{"amount":"+0.880688","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$520D9C02-CBCF-41B8-9E71-EF8C327A9CAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a77626466e5561dc9cfa1facd16625c5a84beba","datavalue":{"value":{"entity-type":"item","numeric-id":2282537,"id":"Q2282537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8542d4ad4107330a82ad3d3f8baed45e93565f7","datavalue":{"value":{"amount":"+0.8694704","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$1CAD002F-1BDB-4038-B7A2-B0754E6C1B16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08a72a47065286d6690ba505d62f8338c6646a0d","datavalue":{"value":{"entity-type":"item","numeric-id":2453159,"id":"Q2453159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a9d5a503f19475013dda40aed875b260200a1ec","datavalue":{"value":{"amount":"+0.8440256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$76139065-1731-41C0-B17C-A97801B4C65D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b80482d7c0071e6a917c183cbcba9b0e5d8ae48d","datavalue":{"value":{"entity-type":"item","numeric-id":4852849,"id":"Q4852849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb84e75d2a6f94d384f5a80ee59c5e3499951054","datavalue":{"value":{"amount":"+0.8404024","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$85BCE092-391A-427E-A1F7-6A79E1DFB548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c4401de9410b4a7628c254b9935a0c30dca5b66","datavalue":{"value":{"entity-type":"item","numeric-id":863980,"id":"Q863980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a6a98c47b2cf36132f00002c3703a8c11431a29","datavalue":{"value":{"amount":"+0.8370415","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$ED8B85F3-217A-42F6-B59A-EA31E2E8EA5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4813ad3c071850f6d7d5efbbafe5cc06a0152c60","datavalue":{"value":{"entity-type":"item","numeric-id":5174109,"id":"Q5174109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11138883cd801f21a8f6abce29d266858c0339e8","datavalue":{"value":{"amount":"+0.83254695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$F9144216-8E5B-4BB8-8432-EEB7307A6D9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f8fa1c68a289bed84cb9318f2415070a384e910","datavalue":{"value":{"entity-type":"item","numeric-id":4497162,"id":"Q4497162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"688fc9846d3e986dfc6e8f935eae4a0e8fc26a87","datavalue":{"value":{"amount":"+0.83146715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$1F03A630-3B67-42F7-A91C-E1B329DF97FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78cf88063f5a34b43dad733895355939c0535035","datavalue":{"value":{"entity-type":"item","numeric-id":2294890,"id":"Q2294890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"882b36c5cf68382474822b82b42e4f3edde13862","datavalue":{"value":{"amount":"+0.8259998","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$F06E687E-238E-4DA5-81B4-AB31EF7E0AFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74617b4e989a3be10fb3ff81f234dc71df4eb891","datavalue":{"value":{"entity-type":"item","numeric-id":2564878,"id":"Q2564878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"972ece3677bc48ace1ee2d4329d1f16f2cbcceff","datavalue":{"value":{"amount":"+0.8238548","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$B01DD5CF-9C50-4690-B33A-C8282AD65AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"116b03a44e697e7181de9ed84586d990fef4521d","datavalue":{"value":{"entity-type":"item","numeric-id":1296087,"id":"Q1296087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37b31a8a1686433e5f33316fa47ecc38905dc432","datavalue":{"value":{"amount":"+0.8229766","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1821023$5894189A-5422-40CC-AE15-0FEC6A62162E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1821023","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1821023"}}}}}