{"entities":{"Q2627247":{"pageid":2637990,"ns":120,"title":"Item:Q2627247","lastrevid":44521359,"modified":"2025-11-23T12:43:07Z","type":"item","id":"Q2627247","labels":{"en":{"language":"en","value":"Minimising variance of job completion times in a single machine"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6724628"}},"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":"Q2627247$902A6CA4-5F79-484F-A902-CB563138B2F5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"22435d69cc34763bd7a757e0ce81af79bffe587f","datavalue":{"value":{"text":"Minimising variance of job completion times in a single machine","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2627247$49B834DA-DD86-40C0-9786-5DBA033F6F7D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d8ea72cb46f24f0ec75bb23a364f6724e75c809b","datavalue":{"value":"1362.90214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627247$EB3DF493-1784-49A6-8028-75522E7AC3B2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a22024e9cfd6dd84cdc7efdba3fdbcafc969037e","datavalue":{"value":"10.1504/IJOR.2012.044030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627247$91283230-9CF4-48EA-A817-52C716848ADF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627247$ED5C0856-9F27-4F23-8DBD-C3D1902D5622","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":"Q2627247$7A3B10F3-44A4-43F3-B7F4-77366CAA290F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7d49858a0afe4b614990a77fa152712e1ae2b828","datavalue":{"value":{"time":"+2017-05-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2627247$124FDA51-78B3-4D9C-9F1C-B8D148B425F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"98f72fc128e91c99f750dd1587b5e4e79a8efe58","datavalue":{"value":"Summary: In this paper, we consider a deterministic \\(n\\)-job, single-machine sequencing problem with the objective of minimising the variance of job completion times. Completion time variance (CTV) is relevant in situations where uniformity in service is needed. CTV is a non-regular performance measure that can decrease when one or more completion times increases. It penalises jobs that are completed early as well as late. Minimising CTV in a single machine is a 'hard' problem. The objective of this paper is to provide an exact algorithm to solve the single-machine CTV minimisation problem based on implicit enumeration. We develop a lower bound for a given partial sequence and present a branch and bound algorithm to solve the problem. Computational results show that optimal solutions for problems up to 80 jobs can be obtained with less computational time when compared to an existing pseudo-polynomial algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627247$173A9634-EBD1-463B-8203-F0255D3B3806","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627247$8A5F8EAD-D543-475D-AA81-E6AE368C812E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d72c9b74fd180629dc32244c2f4414d7474387b8","datavalue":{"value":"6724628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627247$84599E28-7A80-45D7-AE73-33DF1AD4D00C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0e3d728e919b501eeffb6cfc4b13649fe92461f","datavalue":{"value":"single machine scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627247$A0981D9A-AF97-4ED8-B58E-F28C68A6223F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63b10a6beab0339415e1ac54b10415ad5a52f989","datavalue":{"value":"completion time variance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627247$CC4FB54D-6EF7-4137-A8C7-3AAB1DF2E488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627247$7AEE54C6-A8D4-4E3C-9B29-92CB8930B7F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d03f4ce46999846183a567b06f057f20b2bc218","datavalue":{"value":"job completion times","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627247$13945791-A10A-4343-B628-C2410DAC0089","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":"Q2627247$44992F8E-480C-4675-859E-B074948A6B3A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"715d234351be47c60ba5f49281bdea9a4045ee93","datavalue":{"value":"https://doi.org/10.1504/ijor.2012.044030","type":"string"},"datatype":"url"},"type":"statement","id":"Q2627247$B7571804-7C73-40CD-BFF5-EC56B49C06D1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4f8ff46684fc037190dac5e0065829177004f06b","datavalue":{"value":"W2098672997","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627247$F5A5C67A-B84A-4655-A079-6EEB7ED48651","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1604db3599947c384d37082028b0641f80288c3a","datavalue":{"value":{"entity-type":"item","numeric-id":4717390,"id":"Q4717390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d007861e573c0ee23dda0d411db3229d7a6d5d17","datavalue":{"value":{"amount":"+0.96470916","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":"Q2627247$495DAD5E-9019-4CBF-B05D-AE08F56D5477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ca80f8ad3a3c6df32fcb0b952a553067f53ed6e","datavalue":{"value":{"entity-type":"item","numeric-id":733521,"id":"Q733521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c4549981d8ee502b76ef508c553fe9c40efbbf7","datavalue":{"value":{"amount":"+0.93492293","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":"Q2627247$DFC7BCFF-B9A6-48FF-A45F-B2AC31EAA91A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11338a000dbf53691ead84d537835bf71ef9fe6a","datavalue":{"value":{"entity-type":"item","numeric-id":4346869,"id":"Q4346869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"090fc7e93530e77e437846194ffe5fc15c3183a5","datavalue":{"value":{"amount":"+0.92038906","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":"Q2627247$866C4243-F8D6-46D5-AE26-C5B37754A974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e851f5a7643d6ae049d56d101c3595a7e7f16d6e","datavalue":{"value":{"entity-type":"item","numeric-id":2239979,"id":"Q2239979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab9269adada3b5a5cbb3619983edcd51ee041687","datavalue":{"value":{"amount":"+0.9129712","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":"Q2627247$FB60C84A-DE6F-4A42-9788-5C688338CD60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"894a0b59197b5f6c1c4d74647219bf7ef58185ad","datavalue":{"value":{"entity-type":"item","numeric-id":1317023,"id":"Q1317023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9efaa40ea1502bc9adadd48e4a59fb6146251b81","datavalue":{"value":{"amount":"+0.91181207","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":"Q2627247$F4184D8D-D4B3-4D9E-BEFD-A85115602FD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df13e451ea12317f4e90ed4e70b59084953d22c0","datavalue":{"value":{"entity-type":"item","numeric-id":5202822,"id":"Q5202822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"036905d65a5001f5cf5c88ea2214fb73cb70c5f5","datavalue":{"value":{"amount":"+0.90244025","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":"Q2627247$DBE5EF14-9A59-4BC0-9B33-96B507BE4FA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cae77b3c66d9c179e120afce94321f2b25effe2","datavalue":{"value":{"entity-type":"item","numeric-id":3518841,"id":"Q3518841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96f531e6abddec37598e585dff41b41b838aad49","datavalue":{"value":{"amount":"+0.89532745","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":"Q2627247$900BF77A-48DA-452D-9D89-6B760ADF610D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51bd871bae3b5a572c51b60324513e618f3500f5","datavalue":{"value":{"entity-type":"item","numeric-id":4526923,"id":"Q4526923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddb47e07e6a7a945ea9b97df8bd73f4d0dd4acc4","datavalue":{"value":{"amount":"+0.88709474","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":"Q2627247$8664D159-16A9-4743-8D49-2D06F51E4EC1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2627247","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2627247"}}}}}