{"entities":{"Q4494436":{"pageid":6524029,"ns":120,"title":"Item:Q4494436","lastrevid":108615308,"modified":"2026-11-07T05:18:06Z","type":"item","id":"Q4494436","labels":{"en":{"language":"en","value":"Two-stage flow-shop scheduling problem with multiprocessor tasks at the first stage"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1487904"}},"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":"Q4494436$7AC5B3A1-B36A-43D2-BD25-EE4E84B7BBA4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e55ca4808ba08ba3b1d056e17c74513d7f68939b","datavalue":{"value":"0999.90018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4494436$1FD6C189-7976-4FC8-8B90-E8B5340D476C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0c3c3eaf5703e506961209d7172352e093b57811","datavalue":{"value":{"time":"+2002-11-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":"Q4494436$02941A73-780F-48FF-9BEE-1F608502E672","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4494436$EAD07CA9-5B44-4B58-9E55-B4574BF96A6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4494436$820DC032-F55D-4B6E-BED2-675483A790BD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd689b35647e6861a4bfaace2ea56a7c1380d4c4","datavalue":{"value":"1487904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4494436$B76C2D54-55FB-4B9A-A5C3-5F95EAE00672","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fbe9dcddbcc2afcb2f5b387c1303e0b82281922","datavalue":{"value":"flow shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q4494436$B4D39D47-0F56-44AE-8833-E7FE44014919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de956a77da074492c4bbae2ffb5c376b2cd70674","datavalue":{"value":"multiprocesor tasks","type":"string"},"datatype":"string"},"type":"statement","id":"Q4494436$500F5251-CC2C-48A3-9391-3A0FB47A8076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q4494436$0C282571-DAD8-47F5-8080-D4F1BB7E609B","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":"Q4494436$8F3E0A13-035B-4075-B132-D18848BF0668","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20692338969980ebd0139cef499839648b38c909","datavalue":{"value":{"entity-type":"item","numeric-id":1357780,"id":"Q1357780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91fc9fc6008967f79b803ec99bb369f7c666ada6","datavalue":{"value":{"amount":"+0.8478185534477234","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":"Q4494436$DBD07EFE-B7C4-4654-9F00-8FA16B789AA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71f3c3edb7413315c8e2d128ffdf51b32ed7466c","datavalue":{"value":{"entity-type":"item","numeric-id":1985613,"id":"Q1985613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bed57feaf93f61b70d23507bdf2f4d19b7e4f6be","datavalue":{"value":{"amount":"+0.8395964503288269","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":"Q4494436$05BFD9F3-6680-46E8-9E6A-3112ABE50701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2b064b40ed9ce457619980b92930c57b843b04d","datavalue":{"value":{"entity-type":"item","numeric-id":3780742,"id":"Q3780742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af210e70eac6138b1bd70713c54da605a52705a8","datavalue":{"value":{"amount":"+0.8380377888679504","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":"Q4494436$DFE0E2D2-00FF-40DD-9C78-3F5071188CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1eb4617244d5e4f23403c542bfc26840b5fc583","datavalue":{"value":{"entity-type":"item","numeric-id":1399584,"id":"Q1399584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37e07059ca2b96b6e54caa4bf9d5e850b721e0c8","datavalue":{"value":{"amount":"+0.8376171588897705","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":"Q4494436$B76EB61A-097D-40D2-9917-619A8AC6BA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f590f391e54676fc85202d7242c10ea94046fb5a","datavalue":{"value":{"entity-type":"item","numeric-id":3069763,"id":"Q3069763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f07c76d34eb78a83d50b7cf02df5b369e22fe133","datavalue":{"value":{"amount":"+0.8369803428649902","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":"Q4494436$D38869DD-823C-4703-A1D6-D0D7697D6FE7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60fac64d73379f5119101ea93b9c70a5fe62eb67","datavalue":{"value":{"text":"Two-stage flow-shop scheduling problem with multiprocessor tasks at the first stage","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4494436$3AE476C7-FE85-4826-A14A-58397A2946FD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"33b034315368fa91bd9f696b689048fcc8550382","datavalue":{"value":"The authors consider the following multiprocessor task scheduling problem. There is a set of independent and simultaneously available jobs. The jobs are to be processed in a two-stage flow-shop where stage 1 has two identical parallel processors and stage 2 has one processor. Each processor can handle no more than one job at a time. The jobs are divided into two groups, namely \\(G_1\\) and \\(G_2\\), according to their processor requirements at the first stage. The jobs in group \\(G_1\\) can be processed by any one of the two processors at the first stage. The jobs in group \\(G_2\\) must be processed simultaneously by both of the processors at the first stage. Hence there are multiprocessor tasks at the first stage. After finishing their processing at the first stage, all jobs, both in \\(G_1\\) and \\(G_2\\), should be processed on the processor at the second stage. The processing times are arbitrary. Preemptions are forbidden. The objective is to find a schedule minimizing the maximum completion time (makespan). Since this problem is NP-hard in the strong sense, the authors develop four \\(O(n \\log n)\\) heuristic algorithms to find approximate solutions to it. The proposed heuristics are based on well-known list scheduling associated with the subsequences obtained by \\textit{Johnson}'s algorithm [Naval Res. Logist. Q. 1, 61-68 (1954)]. The authors derive a lower bound on the makespan and show that the worst-case error bound of each heuristic is 2. Next, they perform computational experiments to analyze the performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the lower bound. The results of the computational experiment show that the proposed heuristic algorithms perform well. Besides, the reverse problem is shown to be equivalent to the problem under consideration. Finally, the authors identify a polynomially solvable special case of the problem. For the entire collection see [Zbl 0937.00057].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4494436$B8871F48-7939-41CB-9CF8-DDDC01F941E5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"34cb5fef76dc6f22c38eca96ee4a5771b1303036","datavalue":{"value":{"entity-type":"item","numeric-id":6370312,"id":"Q6370312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4494436$34C6E5EF-B514-46C2-8282-AA602FB72CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c6a632e43c4af8fd43b6181d663c469f0b6d322a","datavalue":{"value":{"entity-type":"item","numeric-id":333101,"id":"Q333101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4494436$E91DD443-048C-421E-A22B-6562CB779E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf40b2b0a2ad5e649c63e898a6610234d5cf9511","datavalue":{"value":{"entity-type":"item","numeric-id":4800614,"id":"Q4800614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4494436$DA77DD8C-124A-4DED-9F28-3AD95C6E9A5D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two-stage flow-shop scheduling problem with multiprocessor tasks at the first stage","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two-stage_flow-shop_scheduling_problem_with_multiprocessor_tasks_at_the_first_stage"}}}}}