{"entities":{"Q2331605":{"pageid":2342348,"ns":120,"title":"Item:Q2331605","lastrevid":71867931,"modified":"2026-04-14T01:04:15Z","type":"item","id":"Q2331605","labels":{"en":{"language":"en","value":"Scheduling a single machine with primary and secondary objectives"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7124199"}},"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":"Q2331605$6DE4787E-7C79-4F2D-ADC6-222428160933","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"814827823b8a396d6ce8ddf73f8771721b9af98f","datavalue":{"value":{"text":"Scheduling a single machine with primary and secondary objectives","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2331605$A2097DA3-2800-4DBF-9869-616A0013F5F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f179dcdecce487eb19fb4e1bc1374226c013c0de","datavalue":{"value":"1460.90091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331605$7CA83B74-67F8-4F7A-A2A5-1681C34A9433","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2759ac1168b4b7e946426aa487b4f4191fa8e2b7","datavalue":{"value":{"entity-type":"item","numeric-id":221901,"id":"Q221901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$CB854AAB-2158-4B52-B92A-908B00149A97","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$1E239FD0-6D21-40BD-A69B-079199BE0B61","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cf3c9392a3a411e1401dab8af8f22fd364f2a018","datavalue":{"value":{"time":"+2019-10-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2331605$9FF1A095-E79E-45B6-B588-F60C846E4058","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e3a5603f549b983174c5a9094ea7a206f1e272f3","datavalue":{"value":"Summary: We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with the secondary objective to minimize the maximum job completion time. The problem of finding the Pareto-optimal set of feasible solutions with these two objective criteria is strongly NP-hard. We give the dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time. These properties, together with our general framework, provide the theoretical background, so that the basic framework can be expanded to (exponential-time) implicit enumeration algorithms and polynomial-time approximation algorithms (generating the Pareto sub-optimal frontier with a fair balance between the two objectives). Some available in the literature experimental results confirm the practical efficiency of the proposed framework.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331605$94B64550-1E65-42A0-98C1-A71E2F447160","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331605$21DFEF94-4C10-40F3-BB01-8947A49B2EBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331605$5D99D887-2A79-4FC1-9818-270C24786253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331605$3C6507DE-7709-4F5B-B62E-EAACA324E223","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"55cbaa80d64c2128d51310bee886e58ca01c7e03","datavalue":{"value":"7124199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331605$68B685D4-A81B-4EAD-9FE1-659FF71231EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2a4dc03993659d63f98d667cd71850458fbc43b","datavalue":{"value":"scheduling single machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331605$FC5A5085-0586-456F-B027-899D6DE0C56E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c4197c2138bcd9ed69790046b97776c17f0305d","datavalue":{"value":"release time","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331605$9E05AF74-3F38-496C-A3BD-A498CC1A4C62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d45afc6f769635b477b3970225aba7f4bb2dfabd","datavalue":{"value":"lateness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331605$02C29533-E216-4AF1-A915-9C10384EB906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331605$EA329A69-5B0F-4526-86C3-67010B1171F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2d5f2795685b244454f4f7260e4183f11ed60f0","datavalue":{"value":"bi-criteria scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331605$4A1E78FB-950E-4D0A-8DF1-1EEB69926AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e80445422a8e52fb16d0bcfe514494308db9dc4","datavalue":{"value":"Pareto-optimal solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q2331605$B4BF8988-2B60-411F-AA2B-039BEA73B23A","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":"Q2331605$7EBC601C-1374-4447-8B1A-B00BC2500C18","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ac3e315d3cdb551caf88af9646186fb3e7e94bfa","datavalue":{"value":"https://doi.org/10.3390/a11060080","type":"string"},"datatype":"url"},"type":"statement","id":"Q2331605$C61A4330-AE0C-48C6-BA54-B590B21D94F3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e18b7fc467a532b8cdc31496a25cb6bddbb8069d","datavalue":{"value":"W2805567963","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331605$21DF8D33-36A0-493E-A435-725F73937459","rank":"normal"}],"P223":[{"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":"Q2331605$9593B09E-A6CA-4002-8DE7-8B8D7E686A2E","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":"Q2331605$47916B34-A757-4FA3-A3A7-86C7A6D4E83E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e8f5fdd7bd82e2d3ffd63779bd9ac47d7f91caa","datavalue":{"value":{"entity-type":"item","numeric-id":4016707,"id":"Q4016707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$A99172D5-422C-4AAB-B874-BC152133ACA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2d5082be7d3230e7a593f52ed7e57bf1cd8029b","datavalue":{"value":{"entity-type":"item","numeric-id":1314328,"id":"Q1314328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$A416B9F9-15CE-4776-8D64-0DA5FA987432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69c815ba2665f73c27c56567d2e4051d671ff30e","datavalue":{"value":{"entity-type":"item","numeric-id":3863414,"id":"Q3863414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$7FB99B8F-BFD1-4088-A79C-0407B9252CE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"562344d3dbe50bb8faf4dafa69edf26510bb5092","datavalue":{"value":{"entity-type":"item","numeric-id":1665791,"id":"Q1665791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$808378C2-1F0A-4C54-9E17-337755DB63C1","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":"Q2331605$F7325181-3984-46C5-BFFD-A4D819393468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f1d093b01eb63a522b353371a5cda71ab1c0889","datavalue":{"value":{"entity-type":"item","numeric-id":1162927,"id":"Q1162927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$7D1DD9A8-F6D8-41D1-88D4-435DE4237125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d61eb7d9a58a3113cab166621a33b6b0781faac","datavalue":{"value":{"entity-type":"item","numeric-id":1083026,"id":"Q1083026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$96D16E43-07E6-4630-A190-2CC10D36412A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7a4fceb4d3744509698bf33da85b0b0c4c0396e","datavalue":{"value":{"entity-type":"item","numeric-id":2569091,"id":"Q2569091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$FEABCAF1-D84E-4046-B379-EC7786BFD903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19e99b80b5dbcad9c9fc91b1d641e32daf7ee927","datavalue":{"value":{"entity-type":"item","numeric-id":2270437,"id":"Q2270437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$930EC839-C72A-4F9A-93AE-1405936F808B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec76b8fb7d23af9ac9aa157e4c22d91fc75b6246","datavalue":{"value":{"entity-type":"item","numeric-id":991363,"id":"Q991363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$F09A97F3-AB45-4384-B7C6-6A81D6E67F87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4ae368f5009736f85a97fcebaf4630774830353","datavalue":{"value":{"entity-type":"item","numeric-id":4124328,"id":"Q4124328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$D237BBC6-4573-4D70-9608-6FD0A7ACCB9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ba0c3b7c9ae186d1f7b8a18c9bcb2eea55fbc1c","datavalue":{"value":{"entity-type":"item","numeric-id":496647,"id":"Q496647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$C2E12349-E724-4D95-899A-581629C8A5FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d0a8d399b1d7711a30b15dfebd41a2f019155db","datavalue":{"value":{"entity-type":"item","numeric-id":1951910,"id":"Q1951910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$CBBD304F-EED6-4107-92E1-C134C182ABD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8a5274a92b6ca747df718e7670f788006e00b40","datavalue":{"value":{"entity-type":"item","numeric-id":2361139,"id":"Q2361139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$F12CDB96-EEC1-4E47-9414-DEA3EB07AE8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64fbdaf1b01d4f3ead414c2fc2922d5ab8abd7e5","datavalue":{"value":{"entity-type":"item","numeric-id":955319,"id":"Q955319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$6512E0F8-87E1-4B1D-9792-19D7B5454187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"424a8f70ebc2b48c42897f847d81f046cb287caa","datavalue":{"value":{"entity-type":"item","numeric-id":5311858,"id":"Q5311858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$2A397A25-8EB7-4CC1-A06B-3BC05A6E2374","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa798571f8dafbf5880c4cec0aa9518327977905","datavalue":{"value":{"entity-type":"item","numeric-id":4458881,"id":"Q4458881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$81941E9D-E46C-46FB-9749-2BC015D978C2","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ba48855c10ab7b40b44b0c446679822710e84ac1","datavalue":{"value":"Q129723364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331605$B40EAE1B-5EA2-47B9-A024-26BF0724EDF6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ebddbe5609fe2c3b7cfd8e8f8707b164aab9e202","datavalue":{"value":"10.3390/A11060080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2331605$A8C73C71-1431-4202-8484-CCF0E3345161","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55ca406463cb76d94c4d82db8d5ab83f26924356","datavalue":{"value":{"entity-type":"item","numeric-id":1951910,"id":"Q1951910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e8616ff7cff5af564ee8e54004eaee21441ced0","datavalue":{"value":{"amount":"+0.8549410104751587","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":"Q2331605$0F33A1FD-B346-4F29-919C-351F21F7D6F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"310f74db1e5320a42f0f473d96af3946b35ff39d","datavalue":{"value":{"entity-type":"item","numeric-id":2457015,"id":"Q2457015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afc6bd52512c048f6ce171a501e0608da8d8b249","datavalue":{"value":{"amount":"+0.8397680521011353","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":"Q2331605$2490ABEF-4D03-43DD-80E1-A62BB35D4891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1e87b0d8cdb56dd283e44d305b9ba876847d5a5","datavalue":{"value":{"entity-type":"item","numeric-id":6077487,"id":"Q6077487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c527045764e4a72f2b5751e59a54dd04faf9a658","datavalue":{"value":{"amount":"+0.8372010588645935","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":"Q2331605$DCED9384-7C47-4070-ACD1-645B380F2453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"043632142029b873d848b69ec84ff864145b715a","datavalue":{"value":{"entity-type":"item","numeric-id":4880879,"id":"Q4880879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8c1053b83be6c12f69db76e191594539252ceb8","datavalue":{"value":{"amount":"+0.8310062289237976","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":"Q2331605$EF36C8D2-699F-4F72-A994-8FFAA14C539B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfc967aee82b2ce27cedae130312cf76dcea9218","datavalue":{"value":{"entity-type":"item","numeric-id":1823849,"id":"Q1823849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8c1053b83be6c12f69db76e191594539252ceb8","datavalue":{"value":{"amount":"+0.8310062289237976","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":"Q2331605$75C3A4C1-0560-4B43-B126-973FFF93B491","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2331605$C378550D-CC6C-4964-9EBB-38811D9C77E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling a single machine with primary and secondary objectives","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scheduling_a_single_machine_with_primary_and_secondary_objectives"}}}}}