{"entities":{"Q1860370":{"pageid":1871112,"ns":120,"title":"Item:Q1860370","lastrevid":74249103,"modified":"2026-04-14T19:10:55Z","type":"item","id":"Q1860370","labels":{"en":{"language":"en","value":"Complexity results for parallel machine problems with a single server"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1872732"}},"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":"Q1860370$DA545C0D-1B8D-4658-AACD-95A21D366A3D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f37827439b5407191aa8989f52274cad460f09a1","datavalue":{"value":{"text":"Complexity results for parallel machine problems with a single server","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1860370$04BC8509-2420-45D0-8226-B5E9C6DE2321","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9518ad5ec8c365cbd91e4ad4c9ec6a7716f67280","datavalue":{"value":"1040.90016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$62F3035C-D944-407F-99B4-689541080B2C","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":"Q1860370$468EDD45-8782-4D15-BA15-2DAAB0C87B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dfacc5a02325e4addab7e054e966b31c46b7320","datavalue":{"value":{"entity-type":"item","numeric-id":238064,"id":"Q238064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$4B08613C-A3EC-4733-83B3-F223DA0100AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b110a86ad0503810549a5e5e98af9f1fdf618de1","datavalue":{"value":{"entity-type":"item","numeric-id":210525,"id":"Q210525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$FA8C8B6C-196D-4640-A9F5-DBE922C3C867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae4297110811956800cc75fa054c51e0e0312945","datavalue":{"value":{"entity-type":"item","numeric-id":336765,"id":"Q336765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$637A2761-CBBC-4CE1-8C25-DAEC42C3BC02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"78641eb2f75653702db92c9a7fb811442353ea2b","datavalue":{"value":{"entity-type":"item","numeric-id":229433,"id":"Q229433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$F1A56E31-2143-4C82-90BB-D6FDF447697F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39245fc27c04eb23fa7211454c51f34f7f46a9a0","datavalue":{"value":{"entity-type":"item","numeric-id":177699,"id":"Q177699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$FF115224-91DE-4E7A-BC41-60A046F708D9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d938f7e86a16fca407a88e08e757329bded54291","datavalue":{"value":{"time":"+2003-02-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1860370$0F516CFD-0C97-4553-8DB2-CB405C47D7E7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a6eeb3abbbbc4f2811dd42e8b41f8dd63f795cd8","datavalue":{"value":"The authors consider parallel machine problems with a single server. There are \\(n\\) jobs and \\(m\\) identical parallel machines. Job \\(j\\) (\\(1\\leq j\\leq n\\)) has to be processed without preemption on one of the machines for \\(p_j\\) time units. Immediately before processing, it must be loaded on the machine, which takes a set-up time of \\(s_j\\) time units. During such set-up the machine is also involved in the process, i.e. no other job can be processed on it. All set-ups have to be done by a single server which can handle at most one job at a time. The goal is to determine a feasible schedule which minimizes a given objective function.  To specify classes of scheduling problems, the authors use the well-known \\(\\alpha | \\beta | \\gamma\\) notation, which has been extended to server problems by \\textit{N. Hall, C. Potts} and \\textit{C. Sriskandarajah} [Discrete Appl. Math. 102, 223--243 (2000; Zbl 0972.90031)]. This extension includes the following additional information. In the \\(\\alpha\\)-field, the entry \\(S1\\) indicates the presence of a single server. In the \\(\\beta\\)-field, some information on the set-up times is indicated. Here arbitrary set-up times \\(s_j\\) and constant set-up times \\(s_j=s\\) are distinguished. All numerical data are supposed to be non-negative integers.  Complexity results for parallel machine problems with a single server were obtained by N. Hall, et al. (loc. cit.) and by \\textit{S. A. Kravchenko} and \\textit{F. Werner} [Math. Comput. Model. 26, 1--11 (1997)]. In this paper the authors derive some new complexity results.  They show that parallel machine problems with a single server, arbitrary processing times and unit set-up times are at least as difficult as the corresponding classical parallel machine problems without set-up times. On the other hand, the authors show that parallel machine problems with a single server, unit processing times, but arbitrary set-up times are at least as difficult as the corresponding single-machine problems with arbitrary processing times. These reductions lead to several NP-hardness results for problems with a single server. A number of results are also derived for the problem \\(P,S1| p_j=p, s_j=s| \\sum f_j\\), where the objective function \\(\\sum f_j\\) is a sum of increasing functions.  The authors proved that the problems \\(P2,S1| p_j=p| C_{\\max}\\) and \\(P2,S1| p_j=p| \\sum C_j\\) are NP-hard, and the problem \\(P,S1| s_j=1| \\sum C_j\\) is NP-hard in the strong sense.  An \\(O(n\\log n)\\) algorithm is presented for the problem \\(P,S1| s_j=1, p_j\\geq {m-2}| \\sum C_j\\). The authors also consider the problem \\(P3,S1| s_j=1| \\sum C_j\\) (under the assumption that zero processing times are possible) and derive an \\(O(n^7)\\) algorithm for it.  In the conclusion of the paper, an overview of all known to the authors complexity results for parallel machine scheduling problems with a single server and some open problems are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1860370$B15FA4DF-3E81-4B5C-BD7C-6C93B732F4D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$CC117164-68CB-41D1-A3F4-3D85CC434505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$DAB2C89A-301C-4C6F-A0D0-31BA2C55C49D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$E93BB40A-F033-4D19-8E5B-022032A136C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$C04D3871-1EB0-4DC8-8C59-3DE67887D494","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8654c13c851ee58ba6d24b129863859440c1ff00","datavalue":{"value":"1872732","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$5797F29D-8F28-4F7F-9603-BE78F42330EB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e2c88cf105fe5835137ad2fa3a42c08ea633895","datavalue":{"value":"complexity results","type":"string"},"datatype":"string"},"type":"statement","id":"Q1860370$EE046EB9-B3EB-4C6E-8C4C-52FB466C24B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3dacb73fa9efa57cb94c5b919ad076d0f9817dd","datavalue":{"value":"parallel machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1860370$9CB7A8F5-493F-4500-9573-40E8EE8868F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"365bce7f345e9f30fe1bee6c3998418ee62719a7","datavalue":{"value":"single server","type":"string"},"datatype":"string"},"type":"statement","id":"Q1860370$89989C4E-85C5-46EF-9213-543374421DB5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a3577ca3df4bfacea4e2f2b1a9a980c70611b787","datavalue":{"value":{"entity-type":"item","numeric-id":439606,"id":"Q439606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$D7E67216-3A01-4BED-ADFD-F521C2F129AB","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":"Q1860370$70595D05-1CF9-4EE1-828C-7087B82E95A7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c17f220fb7cade551b6e76639a65c192d8058e1","datavalue":{"value":"https://doi.org/10.1002/jos.120","type":"string"},"datatype":"url"},"type":"statement","id":"Q1860370$51312529-A73C-48C1-84A9-19F9598F9F88","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0a2ec56b860e9dfae60c0881ee1fafe6746551c8","datavalue":{"value":"W2089814876","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$4CE13CFD-DE0F-44E3-AFD8-8AD1B38590F4","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9dfab71c1cabf526a6dd628b855a55eac5018868","datavalue":{"value":"Q56920706","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$28A61BF9-EA81-41B7-9F69-0B5F379AE9A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9e7e5f39734ea8c86adfc6baf4d171c3df826b0","datavalue":{"value":{"entity-type":"item","numeric-id":1566574,"id":"Q1566574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$08046F07-63B0-4956-9521-B17B26189B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ef9baf3dcba699a878c514cd421e4879a8fe272","datavalue":{"value":{"entity-type":"item","numeric-id":969356,"id":"Q969356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$8A714196-0227-4884-9FBC-1119F22F79C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fca89d8873cf93e1f1ccdf19d46285e1ed76366","datavalue":{"value":{"entity-type":"item","numeric-id":4488782,"id":"Q4488782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$4EA9EC66-D909-4892-A4FB-38EC311CB447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bda8d11139fda6721b326a88f0ec50a5f4b97262","datavalue":{"value":{"entity-type":"item","numeric-id":1969294,"id":"Q1969294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$7CF0C3D2-1103-42B3-A0B1-D1EB50854DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1357c02bd2c27ebd694cd1fb2072133b8a2e1ce1","datavalue":{"value":{"entity-type":"item","numeric-id":1964481,"id":"Q1964481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$EB8454F4-8554-4CCB-95C9-387417573D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da1909b427fc19ec1609910b2bf5edd253b049d0","datavalue":{"value":{"entity-type":"item","numeric-id":1570817,"id":"Q1570817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$4C905538-F044-4FE4-BBF4-0D9EECF0D19F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55801f61218a09978e522427f1af64891f68dffe","datavalue":{"value":{"entity-type":"item","numeric-id":4323632,"id":"Q4323632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860370$6BD788C7-201C-405C-AB20-9B0D6ECC054F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d7b0de9a02f100ecbc3023d99a9cd2efb1457d0","datavalue":{"value":"10.1002/JOS.120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860370$EF8236B3-3344-4EA3-B05E-91169E8E6026","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e7b14ee7327a05ca29757f58ff850674c9fe68c","datavalue":{"value":{"entity-type":"item","numeric-id":969356,"id":"Q969356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b45550d891e3ca24fa606b4ba79ffaddf3853f2","datavalue":{"value":{"amount":"+0.905141830444336","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":"Q1860370$B52D48C8-5D40-4E20-A3A6-7F50D54FB3C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc78bb77d83d51c415047f1841dbaad53f0f2360","datavalue":{"value":{"entity-type":"item","numeric-id":612219,"id":"Q612219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"850b133e013952e4de1b31aac808b927754f58ea","datavalue":{"value":{"amount":"+0.8928492665290833","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":"Q1860370$7D410324-DCBD-4251-9A29-2AF7E254971F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62d04d815bae4e0b0dd6e9b1273a84c260b5832f","datavalue":{"value":{"entity-type":"item","numeric-id":1566574,"id":"Q1566574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18dfdbe20fd68d13d2a449f4813bc21829962095","datavalue":{"value":{"amount":"+0.8911041021347046","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":"Q1860370$30CED9EB-A8E0-48BC-87DB-1817BBD304C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd06a1a1d58cd59e065f5987412fbef1aca68206","datavalue":{"value":{"entity-type":"item","numeric-id":4488782,"id":"Q4488782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e2b449d4120bebe48ced728dd1668837e1e1aad","datavalue":{"value":{"amount":"+0.8830856084823608","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":"Q1860370$406B42C3-5AF7-440C-9A5D-86B4FAECD190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01279a0dc58f08a8289278e9a3ebe9cd9cec61bc","datavalue":{"value":{"entity-type":"item","numeric-id":5952789,"id":"Q5952789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46eb6c0a7c720ab75433201f135b440894078495","datavalue":{"value":{"amount":"+0.8740150332450867","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":"Q1860370$8BF71459-8EF9-43CA-BF5B-6A02BFE0A053","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity results for parallel machine problems with a single server","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_results_for_parallel_machine_problems_with_a_single_server"}}}}}