{"entities":{"Q706379":{"pageid":708228,"ns":120,"title":"Item:Q706379","lastrevid":63772518,"modified":"2026-04-11T15:26:56Z","type":"item","id":"Q706379","labels":{"en":{"language":"en","value":"Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2132321"}},"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":"Q706379$58120BA4-7017-404D-8772-2D9301550E58","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e36fe26aaa8287603c93eb9421a19053a356532f","datavalue":{"value":{"text":"Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q706379$AC7D807A-35F9-4841-8D4C-D4773C494CC0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c2d1d8b3c00df292a19aeda7e0115bc1b8819f7a","datavalue":{"value":"1083.90021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706379$1AA7CC46-BDD3-4506-ACDD-75E02F7A4F2F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a54c07c31a39e4b53d57a10aae97dcd9b11e81ff","datavalue":{"value":{"entity-type":"item","numeric-id":207391,"id":"Q207391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706379$06ED4EE1-7B82-4DAF-AD23-768DA4FBB8C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea1a02b32a7c76de703232f5e20319b863b61fb1","datavalue":{"value":{"entity-type":"item","numeric-id":161994,"id":"Q161994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706379$3F4A9921-F54E-4FCC-803B-36EB6DEA4602","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":"Q706379$857F277C-7E78-4C8E-BDA1-587530AC3A8F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"831ff43a4969733a7698b320c2210720f63950ea","datavalue":{"value":{"time":"+2005-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q706379$315B1B23-90AC-40C7-BD22-A0DE25053751","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"edaeca9d40feeaf1f9c819df5256a721b95e0f1c","datavalue":{"value":"In this paper two-machine scheduling problems with unit processing times, release dates, precedence constraints and minimum total completion time are studied. More specifically, it is shown that problems \\(P2| prec,r_j,p_j=1| \\sum C_j\\) and \\(F2| prec,r_j,p_j=1| \\sum C_j\\) are polynomially solvable by reducing them to shortest path problems. Furthermore, the concept of ideal schedules (minimizing the makespan and total completion time simultaneously) is discusssed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q706379$A9343EE3-F92D-4404-AD05-C219252A89C4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e47c7ebb56a1f0496381a9a28be5aa2e34301ed2","datavalue":{"value":{"entity-type":"item","numeric-id":210525,"id":"Q210525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706379$24B3F1E3-2F37-4A3F-9D33-07129CDDA4BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706379$78BF1951-2145-4919-BA9F-57296122EF4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706379$3A1C6170-611D-45A1-B9E3-DA66D9AFBB78","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71777cc0ed2179b69e3e55e3687e514ab8641c3f","datavalue":{"value":"2132321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706379$832CF8EF-2B86-40DA-BB24-E9CE4AC6A675","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q706379$EF595AA6-E69A-4173-BEF6-7B8ED3CF14BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q706379$05E8867B-0ABA-40EF-85E4-000C7F22DD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3dacb73fa9efa57cb94c5b919ad076d0f9817dd","datavalue":{"value":"parallel machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q706379$4E78F6E7-E84E-441C-B1FC-2C2609C0C07A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fbe9dcddbcc2afcb2f5b387c1303e0b82281922","datavalue":{"value":"flow shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q706379$6BC7E013-5618-4857-9E5A-DDF13C96A050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3cd4f5f93f8fcf7a68891464be493ca1947d8efd","datavalue":{"value":"ideal schedule","type":"string"},"datatype":"string"},"type":"statement","id":"Q706379$85216EAD-4C59-480F-AB05-0D3375423455","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":"Q706379$3EC6D8B5-CA9A-4A58-8886-D661721445FF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"af13ff5dbbba9c4e93a09f93ca2e454733ef3a96","datavalue":{"value":"https://doi.org/10.1007/s001860300336","type":"string"},"datatype":"url"},"type":"statement","id":"Q706379$F6113E85-0A73-4733-AB1D-61D5E3003A74","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eb8192d972dbce562adfe2b1916b36b57afbe670","datavalue":{"value":"W2083845110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706379$319DE3F3-F2B7-4150-8B1A-E8FDB6AF8A8E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ab65e58f92fba0cad7defbbf31ffa71e751d3887","datavalue":{"value":"10.1007/S001860300336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706379$43B518D4-B9BC-4D09-BC36-EC880AA4149F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36c2969854f71e22051721fd5f22fb8be73da8bb","datavalue":{"value":{"entity-type":"item","numeric-id":5702311,"id":"Q5702311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f636e577fb690534b7415bef458891948f112e6e","datavalue":{"value":{"amount":"+0.8361808657646179","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":"Q706379$D09CA2D5-D7B7-477D-A741-A0181FBCC437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44a595b33185b2c827d95717ac65c6181065345f","datavalue":{"value":{"entity-type":"item","numeric-id":766186,"id":"Q766186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caa551c0a35b03565464ba832f20657cf572449f","datavalue":{"value":{"amount":"+0.835497260093689","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":"Q706379$5A4EB2B8-4588-4C2E-AA1A-7D0CA206887D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e1fbac0c021e608e3d2817f66a60b174ccc7408","datavalue":{"value":{"entity-type":"item","numeric-id":1424363,"id":"Q1424363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b46a4f0f40fc1e28ee4773c32582d5f3af9dcb3","datavalue":{"value":{"amount":"+0.8348670601844788","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":"Q706379$D75A5CE9-6A64-4D03-A5F3-254A9C0ECB06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e0799b3dffc385d39b6a7ca69a1fec44b9fffd0","datavalue":{"value":{"entity-type":"item","numeric-id":2576249,"id":"Q2576249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"825f1fc301d50da01d9e3e86f11962dcdf17cd65","datavalue":{"value":{"amount":"+0.8233768939971924","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":"Q706379$4D55AA17-003B-4FF0-84EE-4492F0C63437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9b99a4a262544008b7d4218bcc383b10b0bbd47","datavalue":{"value":{"entity-type":"item","numeric-id":1812291,"id":"Q1812291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e7c7798c073c6b806d09841026ac5f5359f6d7a","datavalue":{"value":{"amount":"+0.8225361704826355","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":"Q706379$B66DC937-28EF-4D09-B769-F318F350224F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Shortest_path_to_nonpreemptive_schedules_of_unit-time_jobs_on_two_identical_parallel_machines_with_minimum_total_completion_time"}}}}}