{"entities":{"Q757232":{"pageid":759081,"ns":120,"title":"Item:Q757232","lastrevid":49472641,"modified":"2026-01-07T05:27:19Z","type":"item","id":"Q757232","labels":{"en":{"language":"en","value":"Parallel machines scheduling with nonsimultaneous machine available time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4191383"}},"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":"Q757232$67CD8B61-7332-4F63-A57B-8BE88698F4BD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"de5ad81ad65e5fe28d842a0de821bc3481b0e41a","datavalue":{"value":{"text":"Parallel machines scheduling with nonsimultaneous machine available time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q757232$BE3FA709-BE68-43C5-B37B-6539816449A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ce6479b1ee3bf01909ddab0cf3aadfda1c52b02","datavalue":{"value":"0722.90032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757232$2CF1845F-E018-4F54-AC57-DC935C94242A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d7bf10b8dba0da95086b77274ee51a24cc20d48","datavalue":{"value":"10.1016/0166-218X(91)90013-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757232$9747EFEF-B563-4FCD-B404-31BCF61D18D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e454750c2fb4fbd7c325226ed92c521be961a5c","datavalue":{"value":{"entity-type":"item","numeric-id":177697,"id":"Q177697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$A0A5D4E1-8F08-449B-BD5C-C51DC2B2C260","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":"Q757232$9DD63719-902D-457D-8A18-E240312A6360","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q757232$DBEFDA26-27EE-4A84-9D00-824F7B9227E1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"063ee6808fe0cd1491bcfb7e3ecabc622bafd7f2","datavalue":{"value":"A generalization of the known m parallel identical machines non- preemptive scheduling problem in which the object is to minimize the makespan (the total completion time) is considered. The difference to other approaches consists in the presence of release times for the machines, i.e. for every machine \\(m_ i\\) the earliest time \\(a_ i\\) that the machine can start to process the jobs is given.    Two approximate algorithms are proposed. The following results are obtained. Denote by M and \\(M^*\\) the makespan for approximate and optimal schedule respectively. Then for the known LPT algorithm (the longest processing time) the relationship \\(M\\leq ((3/2)-(1/2m))M^*\\) holds. For a modification of the LPT algorithm the author obtained \\(M\\leq 4M^*/3\\). The time complexity of the algorithms is O(n log n\\(+n \\log m)\\) and \\(O((n+m)\\log (n+m)+(n+m)m)\\) respectively. As shown, the performance guarantee for the LPT algorithm is tight, i.e. a sample of the problem exists where \\(M=((3/2)+(1/2m))M^*\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q757232$660F25EF-3995-444F-9AF7-77137CC8C173","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757232$04DB486A-5B69-4469-9904-A23D091E1B9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757232$8E369C0E-EFC7-48F9-87FF-55F2306A7B2C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"daefca7ca301ecc3aeb08aa92b69659c97659c57","datavalue":{"value":"4191383","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757232$BB631D61-DD57-4095-9697-BF38E3A441EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4070a983d3fcf1c7f5f637be4184e698a33bd791","datavalue":{"value":"parallel identical machines non-preemptive scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q757232$49482770-3BEF-445A-AEB3-D2310360963D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q757232$8FFD94E2-A91F-45DD-94B8-91114B368B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b037e835bec10946c8275121512d8f5f0a03729","datavalue":{"value":"approximate algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q757232$BC15F077-ACD4-4E74-BCC6-D8F70FA48AF6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c54e16c51cf038e39d211f26a20642444a0ea747","datavalue":{"value":{"entity-type":"item","numeric-id":612204,"id":"Q612204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$34099D33-DF32-4FCC-A796-59EC3089FBE6","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":"Q757232$00E87D7F-ED06-440D-A229-44FBDA76114A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a62af7ec2eae31085b45e2485228d8678c8c12b0","datavalue":{"value":{"entity-type":"item","numeric-id":4151721,"id":"Q4151721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$207B0E11-6E21-416E-BF3B-239BCD58C174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf91d589b7422c3bd5126152fd793309d8b3739f","datavalue":{"value":{"entity-type":"item","numeric-id":3770267,"id":"Q3770267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$878F4442-C02A-4234-A4AE-1C9705B71ABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc17ad9868778f70eb43382620252bdd715f6c36","datavalue":{"value":{"entity-type":"item","numeric-id":3326834,"id":"Q3326834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$45FEF8C2-797F-4990-B0AB-5350737F979E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7988a07b6af9ebf84294ebb7cbd22eed7ca9deb","datavalue":{"value":{"entity-type":"item","numeric-id":3725543,"id":"Q3725543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$52E56D85-3339-44EE-A94B-B8710B86B16F","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":"Q757232$6C01A098-1946-4EC4-9F7B-4D64CF05950A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df399851d600f5fc66b83855263f74637e3a379d","datavalue":{"value":{"entity-type":"item","numeric-id":5555416,"id":"Q5555416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$4D5ECD13-9D95-4B2D-81FE-119F46717270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7470519bc10f2a005ff140469be5d8d581b53250","datavalue":{"value":{"entity-type":"item","numeric-id":5582060,"id":"Q5582060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$A3B692FB-8850-4E4C-A525-1692EB6313EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87dd51fe3f7e3ac28cf131db8e19ccce759f746b","datavalue":{"value":{"entity-type":"item","numeric-id":1109673,"id":"Q1109673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757232$6DA4DD75-9344-4635-92C9-DE2E16E13F90","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"77fbf0faf23c3c202e8a46c420a9d72f8ff15509","datavalue":{"value":"https://doi.org/10.1016/0166-218x(91)90013-m","type":"string"},"datatype":"url"},"type":"statement","id":"Q757232$F3275751-F3A7-4BF8-8725-EDD77E421378","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9663bccf48ffe348ded2b2d38356eaf86bef3af1","datavalue":{"value":"W2077711297","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757232$BFFEC9CF-EEBA-409A-876C-93595167C2EE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19bfeb12bce2b3e1eaa98ff0287d2411606a9c65","datavalue":{"value":{"entity-type":"item","numeric-id":4388434,"id":"Q4388434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6d4652b9dd1f3e0a522d22f220c43dd4f571ed2","datavalue":{"value":{"amount":"+0.9127283096313475","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":"Q757232$E88D95B9-D5A1-4E08-A894-CE855CCAB4AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51d443b65fd462af0f2a5149b65fae804fd20e5c","datavalue":{"value":{"entity-type":"item","numeric-id":1271384,"id":"Q1271384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4303870d242ec9842ed55954a7cf3489885cef03","datavalue":{"value":{"amount":"+0.9080223441123962","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":"Q757232$03FC310E-3923-45E7-88B9-A4FEBE5E49E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cc6c9b9aaaa1a136785b1aaba385878ae573cf5","datavalue":{"value":{"entity-type":"item","numeric-id":1355924,"id":"Q1355924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10b08512e78a64d920b2a722c2bfb1b4800d1317","datavalue":{"value":{"amount":"+0.8989869952201843","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":"Q757232$48B34F4A-AEF4-4FB0-9F6C-09DABC90D107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f38dedab37eb28ac8215340e23a24d0a74e0c74","datavalue":{"value":{"entity-type":"item","numeric-id":2910573,"id":"Q2910573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10b08512e78a64d920b2a722c2bfb1b4800d1317","datavalue":{"value":{"amount":"+0.8989869952201843","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":"Q757232$193D208E-9431-4D99-88E1-7C9C0359C212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c57d520960c816c537cbca1e7a35728254958d1","datavalue":{"value":{"entity-type":"item","numeric-id":3014094,"id":"Q3014094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d39f8d9708c8556ecca785300f7f8c8924f168e9","datavalue":{"value":{"amount":"+0.8926796913146973","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":"Q757232$5424B917-5250-4B91-8E13-5C49C660D03F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:757232","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:757232"}}}}}