{"entities":{"Q853793":{"pageid":855641,"ns":120,"title":"Item:Q853793","lastrevid":64878012,"modified":"2026-04-11T22:50:06Z","type":"item","id":"Q853793","labels":{"en":{"language":"en","value":"Scheduling equal processing time jobs to minimize the weighted number of late jobs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5073716"}},"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":"Q853793$0FD9F68D-4DCD-4BE8-9B0B-C9F3B286017E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2e87b1a78b648dfb95c1431da867b5620d07f48f","datavalue":{"value":{"text":"Scheduling equal processing time jobs to minimize the weighted number of late jobs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q853793$1D8B9A4E-D897-406F-85BD-94E1D080C473","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c09232c3b1a8b0c314db3870c67c9d3f2cb84615","datavalue":{"value":"1126.90019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q853793$388B5523-C2C0-4FE6-B5D6-C174AC333328","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae4297110811956800cc75fa054c51e0e0312945","datavalue":{"value":{"entity-type":"item","numeric-id":336765,"id":"Q336765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q853793$35D5F6FC-1928-4770-A67B-6CD43F85D8CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"daf0481954e7802993a7ffb0f5fbcfa71f15bb37","datavalue":{"value":{"entity-type":"item","numeric-id":177705,"id":"Q177705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q853793$E6266EC3-E309-449E-9CA5-9E82084755E2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2f72ad9c1803a90ff29745f6b35715c1a74581dc","datavalue":{"value":{"entity-type":"item","numeric-id":359405,"id":"Q359405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q853793$A8A7E0E3-227E-4C23-9E7F-6C5EF572E597","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e72da49a9cdc23965ff0d1c9fcf6159ca75a2a61","datavalue":{"value":{"time":"+2006-11-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q853793$AA69FC53-A125-414A-A2EC-B6867AD1C9EB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"715a16dda07dd2dbc2ab0376f5b331b7154db4be","datavalue":{"value":"The problem of scheduling \\(n\\) jobs with equal processing times on \\(m\\) parallel machine to minimize the weighted number of late jobs is discussed. Where -- as a surprise -- the preemtive version is proved to be an NP-hard problem using a reduction to the numerical matching with target sums problem (stated in Garey and Johnson (1979)). And the non-preemptive version is of complexity \\(O(n\\log n)\\). Beside these two complexity results, extensions and further open problems are stated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q853793$1B38E59A-1BBC-4941-8EEE-286674B159B9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0fde83111797a0d59e7015849b12b6c917e7b4a1","datavalue":{"value":{"entity-type":"item","numeric-id":778892,"id":"Q778892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q853793$8BE057D4-07D8-468A-BFA7-0F31068D275A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q853793$3890644E-CC34-413F-9036-7A39B0718A0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q853793$4362646E-694C-4586-AA05-FD5078A3CFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q853793$1933D92F-0B76-4474-A43B-1CFAF67510B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a45ac9e814cd2af3b3ad2d5e1a8022634ea120fa","datavalue":{"value":"5073716","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q853793$7A88EDA1-AD82-4AE1-87A5-95103A1FF8D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c44ed92f7b2112402367cc70efcf29e6cea62575","datavalue":{"value":"preemtive","type":"string"},"datatype":"string"},"type":"statement","id":"Q853793$4F0E4C02-4E8A-4216-84D1-28397CABE090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e9ef363e692af085cde5398b31152a16dd675d9","datavalue":{"value":"non-preemptive","type":"string"},"datatype":"string"},"type":"statement","id":"Q853793$D28D56C9-D32D-4FB7-9199-C80F29A6A293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q853793$2DC2F062-9305-4FD2-AE46-65608F9DD73F","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":"Q853793$EF3B93A1-A45B-4802-B453-5C84B73BD5A4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a20eb372109f61f6c464e15fdc8689b54334c9c6","datavalue":{"value":"https://doi.org/10.1007/s10852-005-9011-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q853793$7DC5297A-5B60-4A37-BBC2-0895DC67089D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"17ffccd68bc5c20966f59b9c3e53de3ad6ea6fc8","datavalue":{"value":"W2025422398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q853793$7F9B219D-7A0B-48EC-935D-18A974CFA128","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"43219cfa4e1f74b898f9a19611200ac83fddfc8a","datavalue":{"value":{"entity-type":"item","numeric-id":4396949,"id":"Q4396949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q853793$8DC29213-3738-43C7-B1A0-9C07B1D39A16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e61600355435f6146b17d0f0cea6c48daeb24928","datavalue":{"value":{"entity-type":"item","numeric-id":4031970,"id":"Q4031970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q853793$C01F49A6-9BDD-4BF5-874D-4CF872226F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6950f1b4e3fabff650d8b9323db8947294ac220","datavalue":{"value":{"entity-type":"item","numeric-id":1299919,"id":"Q1299919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q853793$A4CDF4E6-07F5-409B-A490-7189F5CBD85C","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":"Q853793$F0A5B5DB-6B18-4EC2-81C0-C9C2C6B746BE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b2f512b2c187c006dffb1e2c5cf9e88cde2337c","datavalue":{"value":"10.1007/S10852-005-9011-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q853793$3F6F8139-AFAA-4773-A5A2-51AC6BABCC93","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea049502c09b3c8be8f38ae5bfc6ca627d8ca582","datavalue":{"value":{"entity-type":"item","numeric-id":1964481,"id":"Q1964481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06d4428023a842b6815a9af3bf3c2060fd343dc5","datavalue":{"value":{"amount":"+0.883431613445282","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":"Q853793$4703C4F1-1227-4C53-8A3F-8DF0FD50CFD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f23f48410a69ecb4d702bd39f3d11da06633d15","datavalue":{"value":{"entity-type":"item","numeric-id":1962067,"id":"Q1962067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1743d4cc2288d1ad973c458aab2759d5e801441","datavalue":{"value":{"amount":"+0.8829516172409058","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":"Q853793$3648960B-E153-4C07-B43F-0394A07F72BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36c249f361f9e6e7ead04d118361d4a7680d629e","datavalue":{"value":{"entity-type":"item","numeric-id":3826352,"id":"Q3826352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a41cffa09e852d834a1bbff1a9fc3e963bc26986","datavalue":{"value":{"amount":"+0.856473982334137","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":"Q853793$EB3FF6BE-5195-4BBB-A58C-1CCB19E164DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bd943444330cf1702eb9a5e4acd7fd000d20d17","datavalue":{"value":{"entity-type":"item","numeric-id":293435,"id":"Q293435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"559ad032314ca47d49e708593fd6403d0a62bac6","datavalue":{"value":{"amount":"+0.8426432013511658","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":"Q853793$C197DADE-7B8D-441D-A8CB-D6F225AA4C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d67a274448bb1050852129196cfa75c409d9b09","datavalue":{"value":{"entity-type":"item","numeric-id":626963,"id":"Q626963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbb80cc057b57ddee991a5035828c68cc505e194","datavalue":{"value":{"amount":"+0.8320969939231873","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":"Q853793$DB2D2664-3FA0-4C6B-B8E9-12E1535B30CC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling equal processing time jobs to minimize the weighted number of late jobs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scheduling_equal_processing_time_jobs_to_minimize_the_weighted_number_of_late_jobs"}}}}}