{"entities":{"Q1315994":{"pageid":1326744,"ns":120,"title":"Item:Q1315994","lastrevid":47232973,"modified":"2026-01-01T02:12:37Z","type":"item","id":"Q1315994","labels":{"en":{"language":"en","value":"Parallel machine scheduling to minimize costs for earliness and number of tardy jobs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 516869"}},"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":"Q1315994$C85FEBD7-A718-4401-9195-DC4A67A83435","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b875382dd28e5b668b82f38b23cc021fa9304af3","datavalue":{"value":{"text":"Parallel machine scheduling to minimize costs for earliness and number of tardy jobs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1315994$7A743C1C-668C-4879-9578-24A1D76A174B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aef6dcb1fedc6cec3e316b369839946e57bdc485","datavalue":{"value":"0816.90084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315994$D2891410-9A3A-4AF3-A8B8-E0AA57B68519","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8ed96e7f73a7f985c8cea91ff8bab59346c18d18","datavalue":{"value":"10.1016/0166-218X(93)90088-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315994$E10EFC43-D852-4A0E-8536-6A6A4F184E72","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$0FA92006-78FB-4CAB-BFF2-AB8B2A002A83","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9691c94e4d74442d83c12cd315e5e8ae0243473c","datavalue":{"value":{"time":"+1995-07-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1315994$B5E3EE8B-38F6-4A45-8619-71FEBA0D7314","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e06ff60b25302eaa3508cdd277ea1d4ff40cad04","datavalue":{"value":"This paper discusses problems of scheduling \\(n\\) independent jobs on \\(m\\) identical parallel machines so as to minimize costs for earliness, due date assignment and weighted number of tardy jobs. The main complexity result is as follows: (1) The single machine problem with an adjustable common due date is solvable in \\(O(n\\log n)\\) time if tardiness penalties \\(w\\) are equal, earliness cost \\(f\\) and due date assignment cost \\(g\\) are arbitrary, solvable in \\(O(n^ 4)\\) time if \\(w\\) is different, and \\(f\\) and \\(g\\) are linear, but NP-hard if one of \\(f\\) and \\(g\\) is arbitrary. (2) The single machine problem with an externally given common due date is solvable if machine idle time are allowed, but is open if machine idle times are forbidden. (3) The multiple machine problem with an adjustable common due date is NP-hard except \\(g= 0\\) and \\(f\\) is linear (or \\(g\\) is linear and \\(f= 0\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315994$5D83869C-BDC1-41C1-A2CD-C534F3B959DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315994$4E4DCB52-2778-4B51-B329-02A7D2BAE02C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315994$5EF529E5-9D74-41D6-85B3-E3CDC2057C26","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4a63cd30dbca80775bbd642a12a5f4081fb4f8d1","datavalue":{"value":"516869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315994$1D908075-CBE4-40B2-98F6-398D0B57FAE5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb3d5d67ecc295abfe474c8e632a944f8b951c80","datavalue":{"value":"independent jobs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315994$AECC37AD-BF16-40E8-96FD-89ED190E7AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01768ba8b6bf78e7c3dea4e88b2aee1c86740f4a","datavalue":{"value":"identical parallel machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315994$340D29BE-E5ED-4411-B21E-5299BD9CBE23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41b8226b7f0f6874adaf5ec4de245586221332c3","datavalue":{"value":"earliness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315994$DED1B868-C83B-41A7-96C8-7B70346DEC67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"590a5709b6e48369f3075773679ecf557956e216","datavalue":{"value":"due date assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315994$A47FEDF8-C13D-400D-99D1-20C94E6C24EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11f752944ce06c766f8b7d361da4ec58b94a2e71","datavalue":{"value":"weighted number of tardy jobs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1315994$B280F912-A224-4BCC-9185-B67A35E8D1E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e915a4f0cbbdecbece0fc5ded5c35fccb86aef03","datavalue":{"value":{"entity-type":"item","numeric-id":778892,"id":"Q778892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$9B61A080-76B1-4713-A13E-554DEE6EE17B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c776795cdde5f51b3c300f0b87440aed88df58e1","datavalue":{"value":{"entity-type":"item","numeric-id":162228,"id":"Q162228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$2FFDE8A5-FE8B-4859-BD60-75A6C7BBFC8D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a7bbab595bf22c8a34ba4e5e45cac27e2f25bec","datavalue":{"value":{"entity-type":"item","numeric-id":1278535,"id":"Q1278535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$3EEB6370-3500-43C1-AD51-652372BC49EB","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":"Q1315994$0853278E-89DA-4577-802A-28DC6188D59D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"352d76e928fc0b288720faa428b5bd6bde8f8438","datavalue":{"value":{"entity-type":"item","numeric-id":3478250,"id":"Q3478250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$25A26385-739D-481B-9106-3B1DAD0E4CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"233d96d4cc8cec7838f97ab402a2b182a37d511a","datavalue":{"value":{"entity-type":"item","numeric-id":1111925,"id":"Q1111925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$A5E36E1C-5E9A-45D8-8946-A2BF0D7E16E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc40b4793979cc74e04f47dbf4ce7936b5d03171","datavalue":{"value":{"entity-type":"item","numeric-id":1321352,"id":"Q1321352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$A39419B6-BB37-40D9-9ED8-C65E67C7FDB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c92054e707464fd7a32753364e9e618b45aba05","datavalue":{"value":{"entity-type":"item","numeric-id":919994,"id":"Q919994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$CE616A54-2479-485B-A0A2-441569A5287F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f69a74e308f73d0ad3e29bde22f0c7cd163d4f","datavalue":{"value":{"entity-type":"item","numeric-id":4658190,"id":"Q4658190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$C06AA0C1-6D34-4F93-BB04-B29E6FEBF482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b2fdfb7bfccbd600544c9c780804bfcfeb735dd","datavalue":{"value":{"entity-type":"item","numeric-id":1210806,"id":"Q1210806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$D1E43C25-8B5A-4636-BAAA-B4497936BF37","rank":"normal"},{"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":"Q1315994$40F404A4-3B0B-4606-A0DF-BE2E8C69E1A1","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":"Q1315994$751A839C-FA7A-4BA3-BDD7-BEF3368A6024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7573bd2dc5356e9f3fcd86f5f2cea9404b45569","datavalue":{"value":{"entity-type":"item","numeric-id":3824090,"id":"Q3824090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$14A01CA7-3233-4D19-B293-45402EADBC0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$01E7A7E5-67AE-4584-87DE-3F968AD75626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bac4a81fb70ae3c21e20795935cdb66a608a7063","datavalue":{"value":{"entity-type":"item","numeric-id":4156114,"id":"Q4156114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$B4D1B39E-5339-4F1A-83C6-357B122D6824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed72b5c0a1a3fe346e2cabc2f98e3083e734c281","datavalue":{"value":{"entity-type":"item","numeric-id":4099215,"id":"Q4099215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$06F4C423-3BA7-4744-83F8-B3924F3CBC09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565dd9f994f9ad40804f24534c6e2ebb318c8a1d","datavalue":{"value":{"entity-type":"item","numeric-id":5576138,"id":"Q5576138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$3DF14A47-A694-475E-9965-3DCC7B379487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26f5c9c0d19a64b0c056775889c7c06a1dc0a906","datavalue":{"value":{"entity-type":"item","numeric-id":5548719,"id":"Q5548719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$D6C26445-C5BC-4490-B482-9A1298F377C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78fd43ce161284ef499548e4b4a3d24dc0e6abed","datavalue":{"value":{"entity-type":"item","numeric-id":3804431,"id":"Q3804431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$E103F6E7-0873-4A0E-9566-9A04982F0F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4e5c165b27a8c400c619f85f58908fa263e6f2b","datavalue":{"value":{"entity-type":"item","numeric-id":4143017,"id":"Q4143017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$6BBDAC00-A0DE-44FA-9892-DDE3AE9A017F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc9afb1325f4a76ebd398fe250e591065c467d9b","datavalue":{"value":{"entity-type":"item","numeric-id":5181074,"id":"Q5181074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$66F7D057-8B5F-45B0-B11B-74B41758CA8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7304626d8132537d82d1f8adffbf7ed39425fda9","datavalue":{"value":{"entity-type":"item","numeric-id":5613006,"id":"Q5613006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1315994$815BDED8-7AA5-4C05-8F4E-3429B6F5FBE4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f1c75495e602251eddf7a8a5c581f73ffd45e749","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90088-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1315994$31D203EE-A814-4FD9-A6AD-16951581A4F5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1f99a9aa96233876c75474730687ed03b2d41504","datavalue":{"value":"W2072586897","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315994$9B5779B3-5EC2-4C64-9802-F7F229D50384","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7b014f8c7dd91122eafd8eb1b2575e11abef7e68","datavalue":{"value":"Q127110775","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1315994$B95C44AF-6F1D-428D-BE74-05A794C7D274","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0240c5a93cc24f90ce4274f1e463231b55ab9f0e","datavalue":{"value":{"entity-type":"item","numeric-id":4279269,"id":"Q4279269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd54769171e73ebd22b7d16ae6ce745adb767d90","datavalue":{"value":{"amount":"+0.9074224829673768","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":"Q1315994$3A567786-7BF9-44A5-8580-A0CDCC713C0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5fea6b70aab1ef3c37be3590c26480e8b2dba9a","datavalue":{"value":{"entity-type":"item","numeric-id":5953163,"id":"Q5953163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd54769171e73ebd22b7d16ae6ce745adb767d90","datavalue":{"value":{"amount":"+0.9074224829673768","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":"Q1315994$9783E936-A252-4C29-85E2-AFEA2A4DDEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"936c9ab64f488e7945f0a9123b81b916ec913b23","datavalue":{"value":{"entity-type":"item","numeric-id":2510197,"id":"Q2510197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54b574d15ce74a4f5e6ba3266ee09ed7f54f92a5","datavalue":{"value":{"amount":"+0.8829087018966675","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":"Q1315994$BEBEA13F-0F6E-4EFC-AD2E-A45A976BF355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"819c825db2b97699feeb6354988a4438fa8b6e54","datavalue":{"value":{"entity-type":"item","numeric-id":5937720,"id":"Q5937720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d891a06d690f86d01c765f32631a871ab4af85b","datavalue":{"value":{"amount":"+0.8716506361961365","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":"Q1315994$8169E033-F9E0-4F9D-A54C-CAC57FF811C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbf7647ef4ec84302b64abfcf539acd595603089","datavalue":{"value":{"entity-type":"item","numeric-id":2490167,"id":"Q2490167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72a9085b42376e507cc1425b30e6ecd5f7a95759","datavalue":{"value":{"amount":"+0.8690187335014343","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":"Q1315994$42AE821F-4EF4-473A-A769-779379D4D0DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1315994","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1315994"}}}}}