{"entities":{"Q614212":{"pageid":615988,"ns":120,"title":"Item:Q614212","lastrevid":63188031,"modified":"2026-04-11T11:11:34Z","type":"item","id":"Q614212","labels":{"en":{"language":"en","value":"Scheduling with arranged multi-purpose machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5829537"}},"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":"Q614212$BE2E8BB3-E8FE-4C32-813A-342ED5D1A60A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9c159473cf2a1688aadea0c14405366ee1ded13","datavalue":{"value":{"text":"Scheduling with arranged multi-purpose machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q614212$F85D9851-99B6-42C6-B55F-04588AD7C5E1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f34ebdf21944863bc27efca90908d27d8e0e5dbc","datavalue":{"value":"1202.90124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q614212$A737E8C9-1E8F-42D2-BBE5-D8A0EC43D225","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"704debd1f44fc34f6766dda08c0a920e5f7f19b4","datavalue":{"value":"10.1504/IJOR.2010.033545","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q614212$50260788-8A63-4D17-B202-0907A1488192","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae7a77c83a05737e50b4358f2d8826e7c3268c8e","datavalue":{"value":{"entity-type":"item","numeric-id":614210,"id":"Q614210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q614212$76C6CDDD-5E56-4A1F-B087-1898EB7802A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d2171f486f9d083aa26c27962f2fc8987f2e3639","datavalue":{"value":{"entity-type":"item","numeric-id":614211,"id":"Q614211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q614212$6830517F-D59A-4776-A92E-44BEFCE996BC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q614212$9F1F8584-5850-4C0F-B7B3-86C6C536CE4A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70c068d94055831ce053d48d1465bcd83ed50969","datavalue":{"value":{"time":"+2010-12-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q614212$B6026D20-E622-401E-85BC-F6B7F1550237","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f191c4cf7b139854ddf2c63e6c4691995fce2d7","datavalue":{"value":"Summary: In the present study, we consider a special case of multi-purpose machines (MPMs) in which there is a linear order given for the machines. In addition, for each job \\(J_i(1\\leq i\\leq n)\\), a ``first permissible'' machine \\(h_i (1\\leq h(i)\\leq m)\\) is given on which it can be processed. Thus, machines \\(M_{h_i},\\ldots , M_m\\) are capable of processing job \\(J_i\\) while machines \\(M_1,\\ldots , M_{h_i - 1}\\) cannot process job \\(J_i\\). Each job \\(J_i\\) requires a time \\(p_i\\) and the goal is to minimise the makespan. We prove the NP-hardness of the general problem and present some polynomial sub-problems. Heuristics with an exact algorithm of branch and bound type are also presented with numerical experimentations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q614212$51557BDB-FF83-427B-9DC9-F881FD0E23BD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q614212$AC94B4E8-DB06-4216-AAF2-BE8B4CC85EE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q614212$3AA76EAF-49CD-480B-85C7-307893B4582B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q614212$FBD879D8-C28C-400B-9CF9-B62D02183113","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c466f2451b9a12af92bb1a97dbaab33ed9b66627","datavalue":{"value":"5829537","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q614212$1D8B6CE6-D640-4413-BC9B-CDCD5321D62D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q614212$5A1891C1-1F22-4B4F-8965-C85E7E57D90C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q614212$FD39D5C7-5969-45BD-9407-0B1997312374","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q614212$B183F2AF-6E2F-4EEE-A4F4-970A0A6390DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe2310e4e2f5b7b2236a24947e6bed29260b3f8c","datavalue":{"value":"scheduling theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q614212$49DE4DD7-7BCA-49A6-B857-67318B3F70EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"787bbfff41a0c08989d4df011f217daa172f3520","datavalue":{"value":"MPMs","type":"string"},"datatype":"string"},"type":"statement","id":"Q614212$FFBDEB01-44C4-4869-B5EB-AD7EE7174636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2f9896f56e3116b793e1719213bec4ac57f3fa2","datavalue":{"value":"multi-purpose machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q614212$D1DF95D9-43F9-41A5-99CB-A6A745117051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q614212$B065C750-889F-464D-A7BF-ECF50ECFDF3E","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":"Q614212$73331413-181C-4D0B-9341-ED46A00D5535","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"71bbe380f5c57facc6a5aa512abd26e878f51a5b","datavalue":{"value":"https://doi.org/10.1504/ijor.2010.033545","type":"string"},"datatype":"url"},"type":"statement","id":"Q614212$51E54130-58E5-4C77-898C-616226410F7E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dbefc56abd4b2e49872f31614171b616803040a8","datavalue":{"value":"W2147205879","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q614212$E747D595-E1A6-46B5-BA5F-5A17D320AC51","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9574fb1ca5a9f60ae5a6f0b975546344f5f6c1c3","datavalue":{"value":{"entity-type":"item","numeric-id":4882527,"id":"Q4882527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8db5fa417d5e8e3ff68d48741ead2165bc2f1746","datavalue":{"value":{"amount":"+0.861167848110199","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":"Q614212$8D64B729-02B8-489B-89EE-A24EAC274EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7aa5fc088371991e687c74a56b29a8000a671b34","datavalue":{"value":{"entity-type":"item","numeric-id":1374420,"id":"Q1374420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6102ca7bab47ca17c12e83a0cc106c83317e2fd3","datavalue":{"value":{"amount":"+0.8495697379112244","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":"Q614212$90DAD16C-F878-4BED-A42F-F9618DE45F6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21f329335783749f9423acf498ac33658f94b254","datavalue":{"value":{"entity-type":"item","numeric-id":496686,"id":"Q496686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19101c6c82e7037071e5dec90798b58ecebc77b1","datavalue":{"value":{"amount":"+0.8357164859771729","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":"Q614212$8C91FB01-2F27-4BE3-95A6-F6F1F635F900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e150e0d953855c9155eb50b827e3348bf0e7296","datavalue":{"value":{"entity-type":"item","numeric-id":1410331,"id":"Q1410331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5296da726e50cad6674fcf8ac78e63a9a1efbe97","datavalue":{"value":{"amount":"+0.8322571516036987","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":"Q614212$F83A3942-AE5C-4F51-B847-BF441E23FF2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef04b79d89f8305da1fbd709ebf5e404476d0e84","datavalue":{"value":{"entity-type":"item","numeric-id":3641981,"id":"Q3641981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75bdc4d00a42b91a2e6f08dd2c329bc0b4e22053","datavalue":{"value":{"amount":"+0.8264943957328796","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":"Q614212$7FCE376A-6A04-4D4A-8C15-DEDDF252309B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling with arranged multi-purpose machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scheduling_with_arranged_multi-purpose_machines"}}}}}