{"entities":{"Q1080771":{"pageid":1091523,"ns":120,"title":"Item:Q1080771","lastrevid":66672120,"modified":"2026-04-12T11:45:30Z","type":"item","id":"Q1080771","labels":{"en":{"language":"en","value":"Average and worst-case analysis of heuristics for the maximum tardiness problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3968301"}},"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":"Q1080771$52396ED9-FEB7-41D8-81EB-4B0FC17EB862","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"069713e2e4ac3c142e148f948dfccd6baad3b7c0","datavalue":{"value":{"text":"Average and worst-case analysis of heuristics for the maximum tardiness problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1080771$04A5630A-FE41-40DB-95F2-636B6A0FF44C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eb82686eee7b40cf3bdef12b1cd3cee3cc6423cc","datavalue":{"value":"0599.90054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080771$F58B15B6-C5C9-4276-8AF9-0ED210B5051C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"79e15a41dbabccfae424fc18222e2a2f2649fe4c","datavalue":{"value":"10.1016/0377-2217(86)90190-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080771$DDFDD8CF-8DC6-4272-A78E-74051C80DA17","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":"Q1080771$EC5B82F7-E6CE-4542-80FB-A4FC865DB308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ccc9bca209c19c4229359c66b59776fbdc7115b0","datavalue":{"value":{"entity-type":"item","numeric-id":579130,"id":"Q579130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$F36E5964-F8F6-4CE4-9C83-B03080C0B682","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":"Q1080771$85EF61EA-3731-45FD-A02D-0EC42213E53B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1080771$45D20D68-C5FF-4389-81AC-B71C43A82C42","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8742a72ce9b28cf6a86eccdbbcd3eff66a6b9a17","datavalue":{"value":"We study the problem of scheduling n jobs with known ready times, processing times and due dates, on a single processor, so as to minimize the tardiness of the job which is latest relative to its due date. We develop a number of heuristic approaches for this problem and study their average error (heuristic value compared to the optimal solution value), over a large number of randomly generated problems. We use linear programming to estimate worst-case performance bounds for all the heuristics. Nonparametric statistical tests show a very strong relationship between worst-case and average-case error, and also between worst-case error and the frequency with which the heuristics identify optimal solutions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080771$88D37375-416F-4E9E-8C8D-426281005AAE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080771$D36D6A82-A8AC-4EBE-A73E-124E064DAC17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080771$CB9C0FB9-170F-46D5-B9F5-B437635F549C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3c5d6d4ac28f8ba3d88b8d89881f2ddbcb4cd37a","datavalue":{"value":"3968301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080771$2E7AF725-2485-49C2-AB30-3589FCD77D74","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a5ba010773d5fde62715dd744b8f150d9ad6180","datavalue":{"value":"maximum tardiness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080771$BB5438A8-4639-4A64-A580-A1AAC5907791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85bc172cde99fa354628fd32fbf699a86e8d8c0f","datavalue":{"value":"known ready times, processing times and due dates","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080771$3E56D666-22D3-453F-A88F-A5116C46F50C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbd4bc26baabcbae091630e4b9e44960328dad8a","datavalue":{"value":"single processor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080771$AEB6719E-F57D-4E1F-B9C6-9AB9C10269DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f218de4bb64deb6097f2d9902a45d5c51710a53e","datavalue":{"value":"heuristic approaches","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080771$4EE74CF3-8188-4667-9DBB-542F71D0A955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13049c3f2f96af87b4cd649d9836a0d7818ccc63","datavalue":{"value":"average error","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080771$163B8C57-0B49-4AD7-A2CD-8BF0D9D70B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cd10c9144c52ec895b194876a63b4c157f97670","datavalue":{"value":"worst-case performance bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080771$C40D7B00-91A6-45BC-96C7-086D1A794B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13f350c60dbda7edf9b8d75f0d3f50f40eab6a62","datavalue":{"value":"Nonparametric statistical tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080771$2BEB02F8-66D6-419B-AE30-01C465D80DEA","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":"Q1080771$90D59E63-C28C-4E4E-865A-B050E74C42B6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bc70dfde45d0e1e199e3e4e34628c5795ccba325","datavalue":{"value":"https://doi.org/10.1016/0377-2217(86)90190-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1080771$4AFDE689-6800-42FA-B625-9D98C23680C7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"de0795f989f0a56d562222f005342af3a29d6b5f","datavalue":{"value":"W1984847202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080771$EAF7678B-3056-4B91-B643-0AC293BAEC56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d924891d31c3626d9f3cad339222f9775fe85237","datavalue":{"value":{"entity-type":"item","numeric-id":4404007,"id":"Q4404007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$B5B1BB59-39D1-4A5D-966F-F3C14BDCEBE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b49831ffa1b847141ffe4d70b0a36ebaa8beccc","datavalue":{"value":{"entity-type":"item","numeric-id":3875704,"id":"Q3875704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$56E8263A-D9C4-4CF2-890D-81D190DA40B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8506cb0dca743fcc107548c7d84f0a553edc56a","datavalue":{"value":{"entity-type":"item","numeric-id":3895229,"id":"Q3895229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$3DABE33C-98D1-4DB5-B7CE-E8A72C13A10D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63edff7cf44469335c2cef00a2281ef8a2ceb484","datavalue":{"value":{"entity-type":"item","numeric-id":798566,"id":"Q798566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$F6AA62F8-A425-4987-A703-6D8C36E368C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$FDBC91EB-5C59-42A8-96BD-DA48241C5F56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a54363cab19ddaa83ba50c46c8127b159b14d03","datavalue":{"value":{"entity-type":"item","numeric-id":4055377,"id":"Q4055377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$2BB95C34-5A68-4D54-ACFE-4A7E3D4BB5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0930d57b126d4670b8351b41154baa4cb1f96e2","datavalue":{"value":{"entity-type":"item","numeric-id":5671788,"id":"Q5671788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$91A8E9D4-2D43-48A4-8707-ABA0A0414AC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a12563e368d3698646fcffe8a5fed64030ebcac","datavalue":{"value":{"entity-type":"item","numeric-id":4055376,"id":"Q4055376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$58571501-606A-47AE-B9F4-F0D6D2AE3810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696d2c12656116930cbe8540683b849a20624320","datavalue":{"value":{"entity-type":"item","numeric-id":3893644,"id":"Q3893644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080771$AF2BBD8A-BB65-4822-8677-15E0263594B0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c136c90ffd6020b0db9f7bd58c74b6ea60c7f15","datavalue":{"value":{"entity-type":"item","numeric-id":4735025,"id":"Q4735025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ef2927326573e0fda3cb787f5b00c82abfd3d2b","datavalue":{"value":{"amount":"+0.8373140692710876","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":"Q1080771$687F3043-A287-4290-8CCC-EFDDFBAD7694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7c755161b7eeb28bf382a6fefe02c8b26b76f6b","datavalue":{"value":{"entity-type":"item","numeric-id":1317079,"id":"Q1317079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e4b5f36b09385f640eceb1bd78c870545120b0f","datavalue":{"value":{"amount":"+0.8298766613006592","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":"Q1080771$6BF8C83E-DE5D-471D-A0D0-46D05F80088B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5370c663ef8c0b7f6bfb280ca9c1c1d28f4a1194","datavalue":{"value":{"entity-type":"item","numeric-id":5167620,"id":"Q5167620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e4b5f36b09385f640eceb1bd78c870545120b0f","datavalue":{"value":{"amount":"+0.8298766613006592","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":"Q1080771$9EEC99DD-82A4-4366-BC7B-990000337D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bb7e63f58e32f341658a82756652a357cf7e1d4","datavalue":{"value":{"entity-type":"item","numeric-id":1310015,"id":"Q1310015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e817ddb0b6e8d78e63c42b4fa5372bf977e74d5","datavalue":{"value":{"amount":"+0.8083189129829407","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":"Q1080771$9F8588C8-5FA6-417B-82BD-F0C2D7D6BDC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a4b0115a8a84666c47bc8358613bc87a791e19f","datavalue":{"value":{"entity-type":"item","numeric-id":5920391,"id":"Q5920391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"029b583abfdbb2cf0a68aac4b1d9a1db1b03408b","datavalue":{"value":{"amount":"+0.8065626621246338","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":"Q1080771$8C75736F-A03E-4F16-A0EA-666DE1BE8135","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Average and worst-case analysis of heuristics for the maximum tardiness problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Average_and_worst-case_analysis_of_heuristics_for_the_maximum_tardiness_problem"}}}}}