{"entities":{"Q1014305":{"pageid":1016153,"ns":120,"title":"Item:Q1014305","lastrevid":69420990,"modified":"2026-04-13T06:53:20Z","type":"item","id":"Q1014305","labels":{"en":{"language":"en","value":"A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5547525"}},"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":"Q1014305$1941213E-83E3-48EA-BE7E-B52844DD5511","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef14f50e0a9fda3e0811b984520fa7a87ca393d4","datavalue":{"value":{"text":"A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1014305$61996137-9158-4E54-8DFB-ACB1A9623CA7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c9c71c3d9d5b0daf6a34ee1bf8af7dd84a46008","datavalue":{"value":"1167.90005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014305$A3E2D811-ECE1-4FB7-88E1-F64A1128437A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d1a856767e9063b4a5f7634410faae579ca0f1f","datavalue":{"value":{"entity-type":"item","numeric-id":1014304,"id":"Q1014304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014305$30796179-55BE-4C2E-8417-1CDA512E6176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f6c98afeeece270017fa964fb0ced99c4c060ec","datavalue":{"value":{"entity-type":"item","numeric-id":510928,"id":"Q510928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014305$05373B6D-2A75-4CFD-858A-0011FFB8BE8C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a1409dc6862a31a77f154ad0a1f54092232038ca","datavalue":{"value":{"entity-type":"item","numeric-id":244038,"id":"Q244038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014305$61EFA691-636E-4085-BE74-9D71059E1B10","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f40d4a7d32e7e554cba8a4f57f931cf8b36f1589","datavalue":{"value":{"time":"+2009-04-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":"Q1014305$7D14438E-249E-445F-B6D1-014482D6CF4C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5619c96ad2ca4888f243a4b9cf661dabb35b2024","datavalue":{"value":"The problem of minimizing the makespan on one machine is considered. Each job has a release date. The processing time of each job depends on the starting time linearly. For this strongly NP-hard problem an exact optimization algorithm with exponential worst-case complexity is presented. Polynomial solvable subproblems and upper and lower bounds to the makespan are described. Two different sets of experiments are performed. The first set of experiments is aimed at studying how the time consumption of the algorithm depends on the data. The second set of experiments compares different search policies.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1014305$E2F5251B-C291-4E36-BDF3-FA11AA2D1ED7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"937feade3061e9f7774221fad1a9d078a901d790","datavalue":{"value":{"entity-type":"item","numeric-id":336765,"id":"Q336765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014305$6B7E035B-985B-4817-953B-428B922D511A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014305$EDF95C96-3211-453D-A568-A9C4F5A9750A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014305$8C89D49B-40FF-48CD-95CB-C23EF7519B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014305$C8A57C11-929F-4A0B-A066-B6DA2E4F67A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b54ec7633bd30c4876d974e531756ef3ce3fd602","datavalue":{"value":"5547525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014305$7CB1EC64-C8EC-49F0-9EEE-8F02654C8831","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1014305$0D789DE5-52D2-4EA1-AE61-A3A228DB9A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1014305$A7BD0C27-B087-4A5C-AB62-A9CDA6A2B235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1014305$A641F4A7-2D05-421B-BF20-3141648037DF","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":"Q1014305$A044F36C-57D0-4102-83AF-53A49B1BCCCE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"482c426b8d45dccf4330cbe1f9a84c72e6647b30","datavalue":{"value":"https://doi.org/10.1007/s00186-008-0258-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1014305$266D0095-9F6F-4BF9-B79A-723974B3401F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"36d6f13ff05d7a9cc14537c1ade9cd23d781b99a","datavalue":{"value":"W2035495488","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014305$3F518C0E-408E-4CF9-83CD-AB1FF341CF6F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"69a871e0376931e861aa8fa1c4802f0bafd76d79","datavalue":{"value":{"entity-type":"item","numeric-id":3439490,"id":"Q3439490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014305$30830639-691E-437A-AE7A-C8856F9D95D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c86ace6b4e4f5fe9a95a30477aac9736fddaa28","datavalue":{"value":{"entity-type":"item","numeric-id":3483073,"id":"Q3483073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014305$C19CD2A8-EF60-41DC-893A-60D959956BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36c56b21239d54898d8687ab5f1fe5fe6f479117","datavalue":{"value":{"entity-type":"item","numeric-id":293188,"id":"Q293188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014305$0B288D3D-B080-44CA-B7D6-BA6D075927A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0510052fb475c32170b04f7b29cf61e24d4d5dfe","datavalue":{"value":{"entity-type":"item","numeric-id":1410319,"id":"Q1410319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1014305$E3409EE8-63FA-4797-9442-E34A0B6B4D01","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2f00a9ccb19b0ad8e711f14e1730c59c077e26c7","datavalue":{"value":"10.1007/S00186-008-0258-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1014305$FE304C5A-04E8-45C9-8AD4-EE4B596BEFD1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32cc43602a39a3dae52cc5bdeb0df8af60f22265","datavalue":{"value":{"entity-type":"item","numeric-id":4661133,"id":"Q4661133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f00d4fd72315d8cf6c662c90853b90d2ab52298a","datavalue":{"value":{"amount":"+0.8577167987823486","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":"Q1014305$931BA695-CD12-45EC-AD69-21C31B1E93EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57f1c7b3c31cfa581891b6979bd0f89777b9b5b8","datavalue":{"value":{"entity-type":"item","numeric-id":3166735,"id":"Q3166735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fcdea8045af6a3a0a845ce865cba1c14db79aff","datavalue":{"value":{"amount":"+0.8530215620994568","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":"Q1014305$74C5770C-81B6-4F17-A7D8-63431B906E45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7d4cc85d04d0ef1419eb260f08a24680d180060","datavalue":{"value":{"entity-type":"item","numeric-id":4248925,"id":"Q4248925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9bc05d3b4f6b83cb5535f15eca581d9a4120252","datavalue":{"value":{"amount":"+0.8512982130050659","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":"Q1014305$2761C318-9058-4AEC-93F9-FC5849C5DD5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38c86c790276191e38da9a7673cf153ebdf1e4b8","datavalue":{"value":{"entity-type":"item","numeric-id":1271170,"id":"Q1271170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65be2fca69fd9de3d32f3654c49f920fab102dcb","datavalue":{"value":{"amount":"+0.8489741086959839","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":"Q1014305$0CB89B8D-8CF7-4CF2-90AF-A790B647706A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35b0281e6c94f2524b8884330e9b5e4b9ec1f558","datavalue":{"value":{"entity-type":"item","numeric-id":3169889,"id":"Q3169889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b80e7f90705d07c2d2636fea64bfc768b2374431","datavalue":{"value":{"amount":"+0.8455362319946289","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":"Q1014305$6114D708-6DC2-4182-AEC4-A195DCC0980A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_dynamic_programming_algorithm_for_the_single-machine_scheduling_problem_with_release_dates_and_deteriorating_processing_times"}}}}}