{"entities":{"Q5958131":{"pageid":8134933,"ns":120,"title":"Item:Q5958131","lastrevid":40898018,"modified":"2025-04-13T21:58:29Z","type":"item","id":"Q5958131","labels":{"en":{"language":"en","value":"Preemptive multiprocessor scheduling with rejection"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715097"}},"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":"Q5958131$BD7B9F81-2240-4C9A-BE56-EFA5B3419B84","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4a3c2feebf1ea4086ceef0bc7603f4c598d64e35","datavalue":{"value":{"text":"Preemptive multiprocessor scheduling with rejection","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958131$7D5E3207-D2FB-4986-92EF-8CBC6D5BEE3C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f1f09f7af1a551bfc85e46d178aca22d604e0f3d","datavalue":{"value":"0992.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958131$B2DBFDA9-B2EE-4669-8C0E-EAF8E1D1FA3A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c42c9b4672cbd78b304c56f0d8a6897ff492e8b9","datavalue":{"value":"10.1016/S0304-3975(00)00288-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958131$2A81E457-5E62-4E84-8ECB-76ABCC65A6FC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"321ead4aa38f96e49f7f54e62d1af94731bd7588","datavalue":{"value":{"entity-type":"item","numeric-id":703066,"id":"Q703066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$18688E3B-1BE4-4CEE-A3FD-82C2FADDC9A0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$8E37A343-2D80-47F7-BE35-4212BF92506D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958131$CD374670-0631-4959-84F5-0CAE28BAB8D1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b1b4a71e2380023f0d884385c5e273fc23435140","datavalue":{"value":"The problem of online multiprocessor scheduling with rejection was introduced by \\textit{Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall} and \\textit{L. Stougie} [SIAM J. Discrete Math. 13, No. 1, 64-78 (2000; Zbl 0936.68012)]. They show that for this problem the competitive ratio is \\(1+\\phi \\approx 2.61803\\), where \\(\\phi\\) is the golden ratio. A modified model of multiprocessor scheduling with rejection is presented where preemption is allowed. For this model, it is shown that better performance is possible. An online algorithm which is \\((4+10)/3<2.38743\\)-competitive is presented. We prove that the competitive ratio of any online algorithm is at least 2.12457. We say that an algorithm schedules obliviously if the accepted jobs are scheduled without knowledge of the rejection penalties. We also show a lower bound of 2.33246 on the competitive ratio of any online algorithm which schedules obliviously. As a subroutine in our algorithm, we use a new optimal online algorithm for preemptive scheduling without rejection. This algorithm never achieves a larger makespan than that of the previously known algorithm of \\textit{B. Chen, A. van Vliet} and \\textit{G. J. Woeginger} [Oper. Res. Lett. 18, No. 3, 127-131 (1995; Zbl 0855.90069)], and achieves a smaller makespan for some inputs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958131$8EF5C62D-9666-4AB2-A0F2-B14EDC2A6B79","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958131$8FE6D021-7821-4B63-BDC5-EF9A5B087E18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"755087c68b2dbb859a4f4133746011b47660d235","datavalue":{"value":"1715097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958131$8FA80240-09FB-4236-9B8C-D3EFB90764B7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958131$3DF1E9DE-816A-4E7A-B080-1E52133B403A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958131$7E7A7B5B-BFF3-4169-956B-18719040E7CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0fca5ac8cddc8f74e7908fc7842929c55342241","datavalue":{"value":"online algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958131$5A039C23-6B9B-4363-9EC7-323427A2B8DF","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":"Q5958131$CB8176E6-61A9-499A-8CA6-D60B78FB5219","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b222c01bf8dffb910779a77358cda2cc5cb9ca3","datavalue":{"value":{"entity-type":"item","numeric-id":4268892,"id":"Q4268892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$F9A213C9-251C-471D-8BD4-0544D1B6D9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8695ab8067903991d76b877211314b9ae0d3706","datavalue":{"value":{"entity-type":"item","numeric-id":960514,"id":"Q960514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$933F50A0-78E4-4A7F-A1E5-2883EBD0E541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc238fce2f1266e0e5ff64e32c9d01cc67a4d327","datavalue":{"value":{"entity-type":"item","numeric-id":1327292,"id":"Q1327292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$4C796617-6EBF-4D31-9463-E7038A49A30A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac783a875a957c8817d93a18fc9982b7ce7f5d71","datavalue":{"value":{"entity-type":"item","numeric-id":4943705,"id":"Q4943705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$2613067E-A517-4DC2-90CD-BFE262AFED85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"392907b60e306d2faa3b5505f8451e97e9dbff07","datavalue":{"value":{"entity-type":"item","numeric-id":1336752,"id":"Q1336752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$4D0D48A3-1F8E-49D2-A154-33EC95C5CB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1acfff9cc0db0552a74f079291e8d7fdd7b0f0f8","datavalue":{"value":{"entity-type":"item","numeric-id":1892104,"id":"Q1892104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$39533162-0730-4680-85BE-337273A9CA9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b546d4be6791f7d4b96d8de0454eeaef69fe7a97","datavalue":{"value":{"entity-type":"item","numeric-id":1919176,"id":"Q1919176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$9D8E02A3-D9A2-49FD-829D-6317DB854884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcc862222d6d6fc145822303945725d33af59d97","datavalue":{"value":{"entity-type":"item","numeric-id":4820909,"id":"Q4820909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$A3D9168F-CCAA-4D5C-A78E-1AC0D67F4BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c83dfe2ccb91b882717379addb0276d9d17e5ee4","datavalue":{"value":{"entity-type":"item","numeric-id":3031924,"id":"Q3031924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$84954573-B286-4AC8-8B77-DCB4ECE8B662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d62d6529573636f59e17c08cac7a0627630d24d","datavalue":{"value":{"entity-type":"item","numeric-id":4032943,"id":"Q4032943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$2BC778B3-A1B0-4B12-82D8-5908A18920B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6433036aaaf40b2f1fee444e1e892bf2330f855f","datavalue":{"value":{"entity-type":"item","numeric-id":4876699,"id":"Q4876699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$B386DFDE-6278-458E-AD1C-787EBC7949F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cccb79fb5b3ed62e52a5d342e03db6043286613d","datavalue":{"value":{"entity-type":"item","numeric-id":1103391,"id":"Q1103391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$617D95ED-65FD-4CF8-BFE8-FCD47F127130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2274507b702603eaf8f83c638f8eb27174be915b","datavalue":{"value":{"entity-type":"item","numeric-id":2768989,"id":"Q2768989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$F4321B9E-9DED-4E88-B57A-1D02FF3DE5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b175cfa902618789905a496e3fd44270a4046653","datavalue":{"value":{"entity-type":"item","numeric-id":5096939,"id":"Q5096939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$A394B75E-C8EC-4C54-93B6-755849411020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97c41907ae7fce9a093033a958e4099f19fbdb46","datavalue":{"value":{"entity-type":"item","numeric-id":287130,"id":"Q287130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958131$0D3D3965-4767-4F2F-BAA9-27CD86ED2EA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83e477b8106cb90117b2f7f4e5c1fc4f29d127e4","datavalue":{"value":{"entity-type":"item","numeric-id":4943705,"id":"Q4943705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30860c7b3429e10ae87893230fa4a8b2f96fc495","datavalue":{"value":{"amount":"+0.96278465","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$C9A64304-3CBA-4826-BE79-B77121997056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35dfc0a304924591fe66e2c1a1747287cdd80484","datavalue":{"value":{"entity-type":"item","numeric-id":4875173,"id":"Q4875173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30860c7b3429e10ae87893230fa4a8b2f96fc495","datavalue":{"value":{"amount":"+0.96278465","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$AE94E198-7DD2-4E58-AF0A-C4A8B35EA8E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"feee1c119826344af8c3a13de03370e5ade86f1e","datavalue":{"value":{"entity-type":"item","numeric-id":1411622,"id":"Q1411622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9a4eee3433dca3247197ba38dcabc586ef7730f","datavalue":{"value":{"amount":"+0.9507308","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$AF889EF1-BAAD-4C53-87AE-3F31CA95976C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ff238b28b4ac2ec4327c451e0370250a84b29f7","datavalue":{"value":{"entity-type":"item","numeric-id":2753942,"id":"Q2753942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e111e8e0563561228a5b4dfc8e59fa090b437da","datavalue":{"value":{"amount":"+0.94405687","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$4AC1075B-8376-42D6-B9B7-33B91F6DAA9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2840139b8f6216c812fe6165f2546e0ceac5ea1b","datavalue":{"value":{"entity-type":"item","numeric-id":2817893,"id":"Q2817893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22729afc98dd65aedb63fb8c11c42e0c4f7001db","datavalue":{"value":{"amount":"+0.91669005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$54461B4A-ECBE-4F74-B44F-8D734FA34310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3774069bbb46b05581941ae6c6b96dacf3d26bd","datavalue":{"value":{"entity-type":"item","numeric-id":4507343,"id":"Q4507343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae72909be6eea32711f74b08ca39c03acdb868f4","datavalue":{"value":{"amount":"+0.90584064","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$F7248AB0-514D-4E87-B61E-E0950C69A01B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e386b910f1abe2ad4844f35d34710a0e7e65b30","datavalue":{"value":{"entity-type":"item","numeric-id":4875180,"id":"Q4875180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae72909be6eea32711f74b08ca39c03acdb868f4","datavalue":{"value":{"amount":"+0.90584064","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$9B58FA75-620A-4595-98EB-49182D5AF89C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c5a1bde8a399031b819b73ab19200031a387e9e","datavalue":{"value":{"entity-type":"item","numeric-id":2917044,"id":"Q2917044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8596ae9e042e5fe2b82b41d5e1452e561a5bc279","datavalue":{"value":{"amount":"+0.89333165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$3C68CD94-F180-4994-9FBB-04E7A210CFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0165e05130d0c36d6bd2e4bfb2b48dd32d65e7aa","datavalue":{"value":{"entity-type":"item","numeric-id":4139680,"id":"Q4139680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d1f266a4ce23e47e3cb5fc4cf4db35a108bd4df","datavalue":{"value":{"amount":"+0.89312977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958131$743D0898-9981-4266-ADF6-F203DA5BD562","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958131","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958131"}}}}}