{"entities":{"Q1326784":{"pageid":1337534,"ns":120,"title":"Item:Q1326784","lastrevid":68473026,"modified":"2026-04-12T23:56:26Z","type":"item","id":"Q1326784","labels":{"en":{"language":"en","value":"A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 584688"}},"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":"Q1326784$314E61D5-7333-43AF-8051-82D23137B5B6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"937bec104041673fa5fbf8445b36cd8207ffa0d8","datavalue":{"value":{"text":"A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1326784$D1A42A32-94E7-413D-8D82-77C3B7FB3EF4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cfed235417d386b76afeb4d718b310d3c3390145","datavalue":{"value":"0807.90061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326784$754A7F7B-77B7-4DAB-8768-16030B0AD3AF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fb94c18fab78a67160f2450c9bf01ff93bcc24cf","datavalue":{"value":"10.1007/BF01719698","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326784$B5261850-BFDC-4B81-87CF-F7108A897BAC","rank":"normal"}],"P16":[{"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":"Q1326784$FCDB85ED-D82F-4D45-815D-DD27EF803023","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9c43b2600d1729fd3bff9a1684164aec83749349","datavalue":{"value":{"entity-type":"item","numeric-id":202828,"id":"Q202828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1326784$859C0648-2169-47FB-B78F-854DA0AACD0D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"61c1795d228ab22211b26a23695343076442e1f3","datavalue":{"value":{"time":"+1994-06-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1326784$23308B3B-4DD5-4BF5-B64B-58C796C402E4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"287183a41aec1d63a7b9f5f78f1a7af1142e9ccc","datavalue":{"value":"The nonpreemptive job shop scheduling problem where \\(n\\) jobs are to processed on two machines so as to minimize the makespan (maximum completion time) is considered. Job \\(i\\) consists of \\(n_ i\\) operations and the sequence of operation processing is given in advance for each job. It is known that the problem is NP-hard for three machines and \\(n=3\\) and it is polynomially solvable for \\(n=2\\) and non fixed number of machines. It is known also an \\(O(r^ 4)\\) algorithm for the problem with two machines and \\(n=3\\), where \\(r\\) denotes the maximal number of operations per job.   The author proposes an \\(O(r^{3k})\\) algorithm for the problem with two machines and \\(n= k\\) (\\(k\\) is a fixed number). The algorithm can be easily transformed into \\(O(r^ 4)\\) algorithm for \\(n= 3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326784$6504B163-5FA9-4277-A8E1-A69721322938","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326784$1C1CB42E-694C-4196-B387-BB9064D81569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326784$31C7F22F-C05D-4EAD-A6CE-43554EE22B36","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"524e3a6229e40f3433d8931328c074240742f8b9","datavalue":{"value":"584688","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1326784$EEBF4691-8898-4E4A-B1BE-609ECA91B4A4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9389daaa71acd8cf54087e960ebc8692d59c2289","datavalue":{"value":"polynomially solvable case","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326784$4D92B2A2-D732-401F-9CDE-064003A061E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee9e29c8a50c0a0a29fdbbb38eaf996e2d241a09","datavalue":{"value":"nonpreemptive job shop scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326784$00E1C8C3-050F-47DF-8A6C-F68A77CCD0DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326784$152BFFB2-226D-4B1A-A01A-50B5222E4E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326784$2338D6B8-E1CF-45F8-8888-C1FC16EEE64F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f974f8886319845576e0e74fe6b937c9c984a68","datavalue":{"value":"two machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1326784$49CD86BF-2D17-4C1D-861D-B7FF427081B5","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":"Q1326784$FB83A1E2-BD46-4134-8F17-0CC145BE84A1","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":"Q1326784$276B8413-BEAF-4FF4-BA9A-B09338ACF395","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d489898259a08c284b0279dedfdd23de0bb5cf4","datavalue":{"value":{"entity-type":"item","numeric-id":1178530,"id":"Q1178530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1326784$AC9774F6-8BA2-4FBD-89D4-1A8D75F59471","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"630924b67b26e8b46f4b9ca53bb4eea125b9ff7a","datavalue":{"value":{"entity-type":"item","numeric-id":915632,"id":"Q915632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c49819c0c10e625f8bee7a71c45532a2f05e1637","datavalue":{"value":{"amount":"+0.9343733","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":"Q1326784$68150017-C97D-4109-A825-8F9AA7976C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8a8740c58894eaa6a84ba14528edf3043110c05","datavalue":{"value":{"entity-type":"item","numeric-id":1364482,"id":"Q1364482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b0c29d5b9235dfc91260bdcb4545869779e60a4","datavalue":{"value":{"amount":"+0.9006635","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":"Q1326784$F7AE1B16-4320-4379-BF93-5EEB97F2D859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe7e2f9c71c5a48c7d2663c80bc210aede0bea12","datavalue":{"value":{"entity-type":"item","numeric-id":2059090,"id":"Q2059090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8a17110cb404d35d1f9fc5fe77282f89a2b8358","datavalue":{"value":{"amount":"+0.88807976","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":"Q1326784$7345DAA7-9D29-4090-B6C8-BB94913100F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7aa07c69b22bb07c6d40a63fb498443f9a70d134","datavalue":{"value":{"entity-type":"item","numeric-id":1108919,"id":"Q1108919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9983fcaa8f890c1647b74a417f05a6243dca0b81","datavalue":{"value":{"amount":"+0.88594306","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":"Q1326784$89FCF418-5617-4D0C-B78C-453384FC7C0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e616c58ebe419a700f39a21c7a2881d9c3791940","datavalue":{"value":{"entity-type":"item","numeric-id":2757667,"id":"Q2757667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e379b51f247379047cf5fb1f9ed063adf964a9c","datavalue":{"value":{"amount":"+0.88338596","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":"Q1326784$BE46EC17-4205-4254-BC2F-42A9D0F070B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ac930bc3e543c52057026e2aefaee1a63599753","datavalue":{"value":{"entity-type":"item","numeric-id":2489279,"id":"Q2489279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88dfe50463342a934738de7469073da12601419f","datavalue":{"value":{"amount":"+0.87199956","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":"Q1326784$B634E072-B2DD-4526-9210-61B96CD4D788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89a6dab85b423ee34e0a2a477c5aa18ea58e6520","datavalue":{"value":{"entity-type":"item","numeric-id":1806278,"id":"Q1806278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60adb0aec670698d6418780f3974fbe24168203d","datavalue":{"value":{"amount":"+0.8687806","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":"Q1326784$BEA7B40E-2C99-49C6-ADD3-B3F931F63F85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91fce961516ce20efcfa7628230d9d2860ef6641","datavalue":{"value":{"entity-type":"item","numeric-id":1789013,"id":"Q1789013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e31440c9a62c9bb001f580e6739b1b68b898b61","datavalue":{"value":{"amount":"+0.8677686","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":"Q1326784$70C04D63-61D0-4F4C-B61D-288AF5A904B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"206c51139efe2aa01f8c9b0cba9c7f4c1d08e475","datavalue":{"value":{"entity-type":"item","numeric-id":6090515,"id":"Q6090515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a81acf86b4495a42fe60437c498f324b2b9aeb7","datavalue":{"value":{"amount":"+0.86689883","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":"Q1326784$B6DA944D-0B2F-4676-8C61-A4F1A4C37BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f6490904858822d71baa9139f592cb5fe80d1b8","datavalue":{"value":{"entity-type":"item","numeric-id":1374404,"id":"Q1374404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bf7f3fb39d72ab1b53164d35ff742453100aa88","datavalue":{"value":{"amount":"+0.86596555","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":"Q1326784$6DAF7B9C-D2A0-40BF-B144-43770D044953","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_algorithm_for_the_two_machine_job-shop_scheduling_problem_with_a_fixed_number_of_jobs"}}}}}