{"entities":{"Q1178637":{"pageid":1189386,"ns":120,"title":"Item:Q1178637","lastrevid":66436608,"modified":"2026-04-12T10:04:00Z","type":"item","id":"Q1178637","labels":{"en":{"language":"en","value":"Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 21983"}},"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":"Q1178637$D9BB6554-72E3-4B48-85FA-9CE69615F6F3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a94b76a39fb390f9b3b47a8bbe0beed82eb15d3e","datavalue":{"value":{"text":"Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178637$B54BFF4C-9567-4A96-8079-1F0B8C73A4EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5959b6843fde24bc2f71202b3d1e6b2a26358508","datavalue":{"value":"0745.90035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178637$91D7CA9E-62C8-41C0-AE7B-D302E85AFB43","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"63acca7580daa615c2730dcac4c82165a578b0a7","datavalue":{"value":"10.1016/0377-2217(91)90310-R","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178637$810A3237-F3B1-478F-8AEF-8BC857E3D134","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":"Q1178637$1D7E8181-DF08-4C93-9CD5-3FF78638868C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1178637$5349C1FE-3E83-419D-8A9D-4695B2351AC0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f316057aed2055f8e993b2d44ba5c92a248bdaa","datavalue":{"value":"The problem of due date assignment and sequencing of \\(n\\) independent jobs with random processing times on a single machine is considered. The job processing times \\(p_ i\\) are mutually independent random variables having distribution functions \\(G_ i(p_ i)\\) with a finite mean \\(\\mu_ i\\). For each job \\(i\\) a due date \\(d_ i=p_ i+k_ i\\) is assigned, where \\(k_ i\\geq 0\\) is waiting allowance. It is assumed that, for a given job sequence \\(s\\), the due date assignment cost for job \\(i\\) is \\(\\varphi(k_ i| s)\\) and the missed due date cost of job \\(i\\) is \\(\\theta_ i((c_ i-d_ i)^ 2| s)\\), where \\(c_ i\\) is the completion time of job \\(i\\) under the job sequence \\(s\\).   The aim is to assign due dates \\(d_ i\\) and to choose a job sequence \\(s\\) such that the expected value of the total cost for assigned due dates and missed due dates is minimized:  \\[ E[c(k| s)]=\\sum_{i=1}^ n\\left\\{\\varphi_ i(k_ i| s)+\\int_ 0^ \\infty \\int_{p_ i}^ \\infty \\theta_ i((c_ i-d_ i)^ 2| s)f_ i(p_ i,c_ i)dc_ idp_ i\\right\\}, \\]  where \\(f_ i(p_ i,c_ i)\\) is the joint density function of the processing time and the completion time of job \\(i\\). In further considerations the author supposes that \\(\\varphi(k_ i| s)\\) and \\(\\theta_ i((c_ i-d_ i)^ 2| s)\\) are linear functions with coefficients \\(\\alpha_ i>0\\) and \\(\\beta_ i>0\\) respectively. For this case the optimal due date assignment is  \\[ k^*_{[i]}=\\sum_{j=1}^{i-1}\\mu_{[i]}- \\alpha_{[i]}/2\\beta_{[i]}, \\]  where \\([i]\\) denotes the job in position \\(i\\) of the job sequence \\(s\\). For the case \\(\\alpha_ i=\\alpha>0\\), \\(\\beta_ i-\\beta>0\\) for all \\(i\\) an \\(O(n \\log n)\\) algorithm for optimal sequence construction is proposed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178637$8C53AA51-9B15-49D3-B94B-62D8A67BF91E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178637$C96FDA3A-AC55-4BE8-8A2E-A7CB339A8F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178637$D2E21F92-6D21-48EE-AE9D-FF20A6784D85","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"506d5af531876afdba86b2f2466af68aa39d7950","datavalue":{"value":"21983","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178637$0DF2A267-5C36-4A96-B601-DC05B1F9B5F2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"590a5709b6e48369f3075773679ecf557956e216","datavalue":{"value":"due date assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178637$C104319E-6587-4683-8D28-841E9109D617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38c268a3c15ca9a080e1f9bc04eccd1a966b3891","datavalue":{"value":"sequencing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178637$CD8B37E7-679F-4FD6-961D-44C1F6A791E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb3d5d67ecc295abfe474c8e632a944f8b951c80","datavalue":{"value":"independent jobs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178637$299CE16B-FA66-4948-9DDD-538DC84362F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd6f9de64c5e655ff504861a2c902a85be5e142c","datavalue":{"value":"random processing times","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178637$049EEBEE-CAA1-4FD0-B7C6-19978123D0EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1ca53a04f8c624238a62137bcb0acb8058cd7ee","datavalue":{"value":"single machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178637$2B24DBCB-6E80-4C8B-80A2-B65974F07312","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c776795cdde5f51b3c300f0b87440aed88df58e1","datavalue":{"value":{"entity-type":"item","numeric-id":162228,"id":"Q162228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$A6F752FD-4ECE-40CD-BAF1-D1DF42ABDC88","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c54e16c51cf038e39d211f26a20642444a0ea747","datavalue":{"value":{"entity-type":"item","numeric-id":612204,"id":"Q612204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$7AA40F8F-4330-44BD-828B-9BB4E6988C46","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":"Q1178637$01CC9748-CA92-4CA0-B5E4-A0E95760BFDC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6ec7c17f6711a309d544d64426292e6d5eb86ed","datavalue":{"value":{"entity-type":"item","numeric-id":3315256,"id":"Q3315256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$396FC86D-E395-40FB-9B8D-3509BE42F8C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f34151dd5330c89326bd0601ad3295b6b1743dcf","datavalue":{"value":{"entity-type":"item","numeric-id":3694969,"id":"Q3694969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$8FB90100-B91C-4B03-BD9D-25A5E20E5840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"023a72503fb1d3c51754cdbaaae45c28fed97562","datavalue":{"value":{"entity-type":"item","numeric-id":3737189,"id":"Q3737189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$492E37BB-4BD1-4F4E-8D9C-66CE62A01FB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a38f3b086c37aaa9c39a4ea8934e277f74fdf7a4","datavalue":{"value":{"entity-type":"item","numeric-id":3712114,"id":"Q3712114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$321C5A51-2F87-4C4F-B516-65D6A4669A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6235d11d5a1948794f3d9fd90d8ffe3e0442e67e","datavalue":{"value":{"entity-type":"item","numeric-id":3778530,"id":"Q3778530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$3236B97E-53B9-46FB-8B72-8002827ED526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"233d96d4cc8cec7838f97ab402a2b182a37d511a","datavalue":{"value":{"entity-type":"item","numeric-id":1111925,"id":"Q1111925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$EB2156C2-027A-4967-A165-7796BDE5E151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f69a74e308f73d0ad3e29bde22f0c7cd163d4f","datavalue":{"value":{"entity-type":"item","numeric-id":4658190,"id":"Q4658190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$0CF7116C-D05F-421E-9D08-117B0533126B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$62734A11-4BB9-4DD7-9409-EBF8E1F5AFB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84fb706ba08f9a1383f33764246fd5240619bbb5","datavalue":{"value":{"entity-type":"item","numeric-id":4039929,"id":"Q4039929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$FA5C9A9C-BDE0-4906-BD1A-F285B34C2518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b53b6dd616c259b68807afb7fc98c3ef2501cc6","datavalue":{"value":{"entity-type":"item","numeric-id":3340483,"id":"Q3340483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$20A5CFF3-E1B5-4420-86B8-50C3F7BB8814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2aac606cea45388139f9361383d2081682b5296","datavalue":{"value":{"entity-type":"item","numeric-id":3939582,"id":"Q3939582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$6DF6068B-24A6-4989-8835-0214335A93F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfd26f96174109ef130ef12884ef62f1b6417f7c","datavalue":{"value":{"entity-type":"item","numeric-id":3748046,"id":"Q3748046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$2BFE6948-59F3-424C-9BCD-94F08C875F7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e9139b660b82ad72d0bbca4ec06a9442c7151c1","datavalue":{"value":{"entity-type":"item","numeric-id":3905049,"id":"Q3905049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$8FF32482-EC4D-40FD-9421-8A7CAFECE589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fef05a29d34826f54b60869dbc6b786ccddecee9","datavalue":{"value":{"entity-type":"item","numeric-id":4197605,"id":"Q4197605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$68605F83-C172-4AE3-9C29-1FDF21F975D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a47f41c0d9db5ee5496ad7c9ffb6618ad168ba63","datavalue":{"value":{"entity-type":"item","numeric-id":4094646,"id":"Q4094646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178637$5300C24C-9B6B-4158-9D71-3E6338D334FD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8922688b46d00870635c7ba07a0a3f64c7eb1f9b","datavalue":{"value":"https://doi.org/10.1016/0377-2217(91)90310-r","type":"string"},"datatype":"url"},"type":"statement","id":"Q1178637$63332413-4639-4BB1-B026-8CF711BAAFCB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fd025e4721198eb9784e2f7a198aba860de46163","datavalue":{"value":"W2125143950","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178637$4D312882-ED90-4D8F-AA19-CD6C979B3DA5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"612b60f78c4b897a99e70881d94405565124d479","datavalue":{"value":{"entity-type":"item","numeric-id":3737189,"id":"Q3737189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcdedaa221734546f5445c43331eec77945fb417","datavalue":{"value":{"amount":"+0.9233081340789796","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":"Q1178637$8289B186-0349-47EF-B632-47363E1786C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e5d2eaf55904eeb24c37f286694f09d9b54905e","datavalue":{"value":{"entity-type":"item","numeric-id":3779987,"id":"Q3779987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f346c6408525e9e1f8a12471a0f8aac4ce374ce2","datavalue":{"value":{"amount":"+0.902699649333954","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":"Q1178637$01C87C3D-7B15-46A1-9A45-0D51B156D1E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7fed0ab3b55acbabad15fcf00e9c22c34d29611","datavalue":{"value":{"entity-type":"item","numeric-id":3070917,"id":"Q3070917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad1d2aaad82c17edeb0735a4953a96e0057a4cd2","datavalue":{"value":{"amount":"+0.8934214115142822","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":"Q1178637$5C5F60B1-7E4C-4A6B-AC23-D2436BDB13CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b20d39c0185a9236b96cb8d2557d141b24991db","datavalue":{"value":{"entity-type":"item","numeric-id":3315256,"id":"Q3315256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cec661c738adf013ab1063f8d1492cefe79d0b45","datavalue":{"value":{"amount":"+0.8615427017211914","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":"Q1178637$A9DC50AB-3D09-427D-A475-E31B1B222B91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9702720abab21c57b13564f7438658cd2e5bcbd","datavalue":{"value":{"entity-type":"item","numeric-id":917429,"id":"Q917429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a0e007ab53ed5b9164dec40b59fe9a8eee7c93d","datavalue":{"value":{"amount":"+0.8582887649536133","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":"Q1178637$88D572D9-96F9-4DD8-94D1-1BB03275B1D0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_assignment_of_slack_due-dates_and_sequencing_of_jobs_with_random_processing_times_on_a_single_machine"}}}}}