{"entities":{"Q1664968":{"pageid":1675709,"ns":120,"title":"Item:Q1664968","lastrevid":68183163,"modified":"2026-04-12T21:59:32Z","type":"item","id":"Q1664968","labels":{"en":{"language":"en","value":"Scheduling jobs with maintenance subject to load-dependent duration on a single machine"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6925744"}},"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":"Q1664968$E7E397F3-D463-430D-9166-267B32972C51","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3e758dc00117442fd446ac8e58fc2efb03cbbe60","datavalue":{"value":{"text":"Scheduling jobs with maintenance subject to load-dependent duration on a single machine","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1664968$0A22A29F-32C9-46AA-BBFE-FBEAD7DB35E5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a6f7633b446ddc2df44bed3bf41f9e4167fd703","datavalue":{"value":"1394.90299","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664968$D50BB809-0A96-47F3-A290-A2E42413DFFC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"64afa2eb9eb3a88626b0b23f548d805d8eabb02a","datavalue":{"value":"10.1155/2015/198950","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664968$62A0BCF9-38BC-4FCB-8F82-69C463B58791","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7a86d0de01034cc9ded6cde9978e15c503b7f0d","datavalue":{"value":{"entity-type":"item","numeric-id":391786,"id":"Q391786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$785753F2-62BA-405E-B3EF-6355A04D23A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d08a624cd3a802d3985cbbab96b2b652169377e4","datavalue":{"value":{"entity-type":"item","numeric-id":1664967,"id":"Q1664967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$355BB6EF-7026-4469-9774-DAE873831B92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9154a52df9c2de9c4e2605f3d3d3682c8ef2e5bd","datavalue":{"value":{"entity-type":"item","numeric-id":511957,"id":"Q511957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$86CAEBB9-DCAD-4BB8-95AF-FE48969A2A45","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$1CAD779A-7C6C-4C38-9A97-2B9AD809DCEA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"07d78b2809f727a96c8c6621733f1ab3a1973328","datavalue":{"value":{"time":"+2018-08-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":"Q1664968$0F2C5BA7-FC6D-4579-A0F3-FF48AE81CF88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05d56a638a3e8dab7d7c6d5cd32dd71a2bac349a","datavalue":{"value":"Summary: This paper investigates a scheduling problem on a single machine with maintenance, in which the starting time of the maintenance is given in advance but its duration depends on the load of the machine before the maintenance. The goal is to minimize the makespan. We formulate it as an integer programming model and show that it is NP-hard in the ordinary sense. Then, we propose an FPTAS and point out that a special case is polynomial solvable. Finally, we design fast heuristic algorithms to solve the scheduling problem. Numerical experiments are implemented to evaluate the performance of the proposed heuristic algorithms. The results show the proposed heuristic algorithms are effective.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664968$13AB0BD5-327A-42BB-8EF1-21B286CF51ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664968$6344921D-2BF6-4E42-AAF5-B5B7436550F4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"37add8b082f024d8b216b5957bf9dcf788421e04","datavalue":{"value":"6925744","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664968$0FDAF48B-6AC7-45D4-9306-7CD196C0949D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"cc00dc5ed489dad262c85ccc1c258aeb8bc5622b","datavalue":{"value":"Q59117579","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664968$C857051E-E954-4635-B5B3-9B58F3DEA0F5","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":"Q1664968$4D0F3A34-6F82-4A50-9779-89F41683D64D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9b2d50f233ef051113bbcf055353f9e3f4681ddb","datavalue":{"value":"https://doi.org/10.1155/2015/198950","type":"string"},"datatype":"url"},"type":"statement","id":"Q1664968$E579DBEB-B4BE-49D1-8FC5-CC474E2F5AC9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"68490df89e1f97ee4892a9be356cf5381f76665d","datavalue":{"value":"W1553440580","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664968$57551F01-3872-4918-B68C-44F6C447C29B","rank":"normal"}],"P223":[{"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":"Q1664968$10802B5E-54B6-4A4B-BED4-76C8B49D3DBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42331cc8cbcbcae2536f435f7dc6f4d2891ef252","datavalue":{"value":{"entity-type":"item","numeric-id":3102810,"id":"Q3102810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$7BB2839D-A44F-47F8-872E-2C1083D082F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f6dc2333c08dd387976f36369e55c28df25d80f","datavalue":{"value":{"entity-type":"item","numeric-id":1969884,"id":"Q1969884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$5D3BF7AD-E350-43F9-9605-A7D74723BCC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ada29d2bd676ee832890ce6dfcbaa3a831bac6f","datavalue":{"value":{"entity-type":"item","numeric-id":2564885,"id":"Q2564885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$EB65889E-102E-4E03-8324-9195F934849D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"429b17376da9777883885a33f020c58afab816ab","datavalue":{"value":{"entity-type":"item","numeric-id":4680430,"id":"Q4680430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$951A34F9-E0AF-41A8-B967-26840A6A2486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c38f533e397bc700a039d0d0a15426b178e4ed44","datavalue":{"value":{"entity-type":"item","numeric-id":1395372,"id":"Q1395372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$BC27DD1D-AAC4-42AD-8A7F-A4D01B61ED8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fc743c5fedd5716698252e18e6e72dd53c6f0c4","datavalue":{"value":{"entity-type":"item","numeric-id":1014400,"id":"Q1014400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$41C1FC76-A0BE-4963-948E-778BA201B9CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4663b89ef150ac1f5c9a4f44e6a219924fa3c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":869201,"id":"Q869201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$7F258E22-D412-4149-8C40-90AF1EA1084F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2b2e8ea5857f0dd2acda570926e2eadb2ac4be3","datavalue":{"value":{"entity-type":"item","numeric-id":2508968,"id":"Q2508968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$F38AFD7C-780C-4EA4-942E-F702E0F79FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf4ff34dc980596959363eb1b4a4beb0054d0016","datavalue":{"value":{"entity-type":"item","numeric-id":757232,"id":"Q757232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$ED9B5EF0-3C43-4F8B-A5DD-A6AEC19C9F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b05d793898ac7642e6e837e0d767f87dea6d8a1","datavalue":{"value":{"entity-type":"item","numeric-id":1962027,"id":"Q1962027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$FD18241E-633A-4D4F-89C8-DD0C66456AFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"041a802624c9114fbff7d384ad29a0a983cf4f3e","datavalue":{"value":{"entity-type":"item","numeric-id":1775060,"id":"Q1775060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$880E1C74-951A-47C7-8058-3F3C32D9F64A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b07d375cd31c9d5e0bd5e1459fe4dc576ca5cb41","datavalue":{"value":{"entity-type":"item","numeric-id":1887910,"id":"Q1887910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$0D2CC9B1-51C5-4CC7-AD5E-5FD27B344F1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a26c6e4290e0d4d0449f6dc4cf0b0845d36265ad","datavalue":{"value":{"entity-type":"item","numeric-id":2384614,"id":"Q2384614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$5BA72750-F010-43F9-8A61-55E22BBE26C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3371921b52bc3848c33e12233cecc699fa32363f","datavalue":{"value":{"entity-type":"item","numeric-id":2255964,"id":"Q2255964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$7F00802B-C1FC-4979-A145-3855B778676B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f5aca50cc3dae742220c98c8e9fbb921a4a9603","datavalue":{"value":{"entity-type":"item","numeric-id":2815833,"id":"Q2815833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$06072EAC-4065-43EF-B02B-B8C8F4A5ACA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2892426233efa9cca12df4af92af0236470650d7","datavalue":{"value":{"entity-type":"item","numeric-id":726392,"id":"Q726392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$684E6BDB-AB5B-4F14-882B-37644CF8FF14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"997010fa0fe64c5416cb73d2fbd5d4d0e35de9ba","datavalue":{"value":{"entity-type":"item","numeric-id":4821303,"id":"Q4821303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$673F505F-AE3A-43AB-BFE9-CBD3922A76C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fdeef2f5956c401cf7a2bb47aae3597405cb70c","datavalue":{"value":{"entity-type":"item","numeric-id":3154418,"id":"Q3154418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa01b1c2b39f5e2b23d5c4c7998a82585bc2d1bf","datavalue":{"value":{"amount":"+0.862154483795166","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":"Q1664968$4D7B2253-5F1D-43BD-9048-BDB019DD270B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9473a3e1ad7707c7dc0504d1ffceefdf07967ba5","datavalue":{"value":{"entity-type":"item","numeric-id":1666458,"id":"Q1666458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b9b5ce9e7330caee1b4b2b2fbb8800cb4176533","datavalue":{"value":{"amount":"+0.8600050806999207","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":"Q1664968$A4CFE753-29FA-4969-AFF1-5B52904C671B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"976dd49ab9d2ee2954436c3e0a0c2a2f13c442b0","datavalue":{"value":{"entity-type":"item","numeric-id":3418856,"id":"Q3418856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f701b85c267cc1f3aad11d3ca950effd9aa9ea3","datavalue":{"value":{"amount":"+0.851507842540741","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":"Q1664968$1A62A529-2BE1-4654-905E-682FF8F7534A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb4cf773ef2189935f93fe7c310c45935113b99b","datavalue":{"value":{"entity-type":"item","numeric-id":2997966,"id":"Q2997966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f54b564846833769f42436b455d46bfcfd16bb3","datavalue":{"value":{"amount":"+0.8362555503845215","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":"Q1664968$29BB3B04-9E64-4268-9D0E-D7B04F88A938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ac96337a49cbc88be2a734daf69ce31df320744","datavalue":{"value":{"entity-type":"item","numeric-id":2266971,"id":"Q2266971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75e9291a70c197a985d782e9b46ad674bdc76d8d","datavalue":{"value":{"amount":"+0.8361471891403198","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":"Q1664968$38579499-533E-419D-B335-8A3041EAA416","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"daf5f856a5d861312ad309ab567540337a5f61d6","datavalue":{"value":{"entity-type":"item","numeric-id":57050,"id":"Q57050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664968$AEA57DDB-4D5F-478F-ABD9-47374D6832A9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling jobs with maintenance subject to load-dependent duration on a single machine","badges":[]}}}}}