{"entities":{"Q1183389":{"pageid":1194138,"ns":120,"title":"Item:Q1183389","lastrevid":66442581,"modified":"2026-04-12T10:06:14Z","type":"item","id":"Q1183389","labels":{"en":{"language":"en","value":"Proof of a conjecture of Schrage about the completion time variance problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33255"}},"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":"Q1183389$D5E617A2-4F6D-47EE-9B37-86DBCECD7344","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c940121c1457de11235d0cec2dd9f9ca924d121","datavalue":{"value":{"text":"Proof of a conjecture of Schrage about the completion time variance problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183389$E1ABD25A-EBAF-4352-B862-917B65CA0B38","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6fb6b537c50f2c5e9c3571e6883598e3a6ae18fd","datavalue":{"value":"0751.90037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183389$59BD95CE-FA5E-432B-AE39-6D60A416FC41","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5845fb9b8b664865023b093070f431a85b0bc947","datavalue":{"value":"10.1016/0167-6377(91)90024-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183389$B6CE45F5-B0F2-4F6A-A47E-7B094C2A8FB0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0983e0688b2ebfdef46f56e43c556cd29449983","datavalue":{"value":{"entity-type":"item","numeric-id":284834,"id":"Q284834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$6F4A61AC-0BFF-4424-B548-A6220A7E82E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"216e7a36a8992ef42057a8f0d0dcb9de6af5f9e9","datavalue":{"value":{"entity-type":"item","numeric-id":1575602,"id":"Q1575602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$2BCBE6F7-0632-4D6A-A1CE-019ECD9CB45B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$DF0910BC-6E09-4F61-82DB-6F2C3C981484","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183389$E62E068C-2572-43E2-A23D-42CDDFF3B3A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e28964ba30e4d9adf31155a928f05f764275ca8","datavalue":{"value":"The paper concerns the completion time variance scheduling problem in one machine, when jobs from a given set are to be scheduled for completion time variance of the jobs to be minimal. It was proved in the preliminary papers that the longest job must be scheduled first [\\textit{L. Schrage}, Manage. Sci., Theory 21, 540-543 (1975; Zbl 0302.90021)], and that an optimal schedule must be \\(V\\)-shaped [\\textit{S. Eilon} and \\textit{I. G. Chowdhury}, Manage. Sci. 23, 567-575 (1977; Zbl 0362.90051)], what means the jobs must be ordered by nonincreasing processing time if placed before the shortest job, and by nondecreasing order if placed after the shortest job. The weaker form of Schrage's conjecture was formulated that for every instance there is an optimal schedule where the longest job is first, the second longest job is last and the third longest job is second. This Schrage's conjecture was proved for less than or equal to 18 jobs in the preliminary paper by \\textit{V. Vani} and \\textit{M. Raghavachari} [Oper. Res. 35, 111-120 (1987; Zbl 0616.90027)]. The current paper provides a proof of Schrage's conjecture for any problem size using the preliminary results and carrying out careful analysis of five cases.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183389$9F3BCB35-A530-4BA2-BCBC-189B0491154C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183389$1C85FBB9-CE5F-450C-8747-0E9785BB3DEE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"df4daec5745468939072127b4daccda7c7c9a3aa","datavalue":{"value":"33255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183389$45F007AB-1B02-4DD9-A349-E32751D52CB5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0f233f0a94e6139f11ffd276130ae22bf5b88b1","datavalue":{"value":"completion time variance scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183389$044F6D6F-861A-426E-829E-37C2A95E6E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fcd398ac1e62ca3a441c68b2ef37e74b0293991","datavalue":{"value":"one machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183389$7CEF2A91-EF59-4D7E-A64B-04FE3AD55DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c72b16143569878bcbbe7b1521b0737729e3d8d","datavalue":{"value":"Schrage's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183389$9F6A2867-0DAD-413A-8236-D7F1C3779EE8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b2430c3d6b40b5d0914704a397f92d96d920a211","datavalue":{"value":"Q123127412","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183389$B686036D-DBE9-41EA-B70F-274D0F4EA4FC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ae0b178f7477e53e629254d2aa001e208822aec4","datavalue":{"value":{"entity-type":"item","numeric-id":301933,"id":"Q301933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$DD1F040E-1835-4ECB-BD0A-65C3045F7CF5","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":"Q1183389$0043FA5E-3D3B-4B06-8CFF-3FCFAC7798CC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6083daa9b27bc732780611c7f6cbff5cb57ac75","datavalue":{"value":{"entity-type":"item","numeric-id":4136913,"id":"Q4136913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$66752ABC-13DA-4571-AABE-33888AE5D907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1580131d64fcf0e42914bf7a9f8bb2ee77cc4764","datavalue":{"value":{"entity-type":"item","numeric-id":3929531,"id":"Q3929531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$47984417-E037-462A-9F6E-9883141FCD89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57a61e6cdd3bba579430ea08c0344599ee096c1a","datavalue":{"value":{"entity-type":"item","numeric-id":5668251,"id":"Q5668251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$80105FEE-54D0-4EB1-B411-E0AB7EB2B663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7adadadefaa7961280f40042bf262b6d3b775106","datavalue":{"value":{"entity-type":"item","numeric-id":4058801,"id":"Q4058801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$FA8AA5CA-D644-4DB9-9063-D16DDD18C514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12fdb96351cdac423393b5cfb398544b07a6ff86","datavalue":{"value":{"entity-type":"item","numeric-id":4726034,"id":"Q4726034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183389$6CBEA84F-9917-447C-A4B2-9C96EAD466DF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ed6730bd840de7d30ae6e20ba44dc6bd5149df5","datavalue":{"value":"https://doi.org/10.1016/0167-6377(91)90024-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183389$D5AB13E5-D162-4C31-A8AD-DC4C5C943E03","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"649d5bcb15993e5580918bf3010b65c1de4394cb","datavalue":{"value":"W1974085404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183389$46FF3BFD-F9FF-49A0-B5A9-94E2EDFDE21A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f127d26dc411340fe9fcbc2f173cf033b4510c4","datavalue":{"value":{"entity-type":"item","numeric-id":1205688,"id":"Q1205688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef78e6b838fbc08ad97e9123ebfea570208b2986","datavalue":{"value":{"amount":"+0.8244180679321289","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":"Q1183389$FFA2F464-BC9E-4637-A281-2DC0F00AB1A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b86914aedb03b7ad70204953d8a06265eb589f21","datavalue":{"value":{"entity-type":"item","numeric-id":4726034,"id":"Q4726034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f87d97f75a782416e5052c1fe454e2b43154cdf","datavalue":{"value":{"amount":"+0.8221426010131836","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":"Q1183389$ED25694A-CB0B-4402-B0B8-4643C7D7EF7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e9d93eb2c1c3fbfef5c52d84a287598f156d32a","datavalue":{"value":{"entity-type":"item","numeric-id":1392562,"id":"Q1392562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40d9da4da3a8f852d294ba189822a72eb6799a5b","datavalue":{"value":{"amount":"+0.8193827867507935","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":"Q1183389$B5BB3955-97E6-43E1-B6D8-4564241CDC6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0eb8dd13db4ba2005919d28f9f61e496318f9139","datavalue":{"value":{"entity-type":"item","numeric-id":1805454,"id":"Q1805454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff80db908aee8d135b9b85f6210b0a3d0e075ad2","datavalue":{"value":{"amount":"+0.8120935559272766","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":"Q1183389$719BD05E-EE0B-4199-B62F-D9340D0A28EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"728cbc7799645e543a26f69e8747a5f3be6e550d","datavalue":{"value":{"entity-type":"item","numeric-id":1069850,"id":"Q1069850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff80db908aee8d135b9b85f6210b0a3d0e075ad2","datavalue":{"value":{"amount":"+0.8120935559272766","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":"Q1183389$C8CD8D3E-77C2-49BD-8F5A-5DA9966F0A21","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Proof of a conjecture of Schrage about the completion time variance problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Proof_of_a_conjecture_of_Schrage_about_the_completion_time_variance_problem"}}}}}