{"entities":{"Q2627304":{"pageid":2638047,"ns":120,"title":"Item:Q2627304","lastrevid":52818839,"modified":"2026-01-23T14:00:04Z","type":"item","id":"Q2627304","labels":{"en":{"language":"en","value":"A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blocking"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6724662"}},"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":"Q2627304$C30981CF-FE6D-4766-97EB-BD585F1A5435","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e8900aa3d564423014c8857b87c0e81e1260433","datavalue":{"value":{"text":"A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blocking","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2627304$FBE5118E-C2EB-4AD7-AFE5-AAF2701DDEE6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"01e16d369e42a509c99fae013868836da4d5540e","datavalue":{"value":"1362.90179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627304$4DC2FECD-754E-42BB-A248-076BF01EF497","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f71c29da126a2f439254d5bd1b71668447dd633","datavalue":{"value":"10.1504/IJOR.2012.047094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627304$13956300-83B3-433E-9DA8-464710DF146B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a1f2391dd4e08f873f9c57088cee5af02d860dc","datavalue":{"value":{"entity-type":"item","numeric-id":2411178,"id":"Q2411178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627304$E9AA8698-BEA5-4AB4-AC54-CFA7316DD909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1bd1102f6d3783e604a2488663d7c8d82bccf626","datavalue":{"value":{"entity-type":"item","numeric-id":1717214,"id":"Q1717214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627304$BD0097F5-C9EA-460F-BBC1-44F97FDE11E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae7a77c83a05737e50b4358f2d8826e7c3268c8e","datavalue":{"value":{"entity-type":"item","numeric-id":614210,"id":"Q614210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627304$93A8B94C-DDFE-44C0-AB6B-855D635CA040","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627304$2639A1AC-B9C6-434A-A7D3-616E28F85998","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7d49858a0afe4b614990a77fa152712e1ae2b828","datavalue":{"value":{"time":"+2017-05-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2627304$F865CACE-AC85-4BDC-81CE-3BC02365666F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"48ae6bf98dc1841f8bf9fe3f38c3cad3bc33421c","datavalue":{"value":"Summary: In this paper, we study the job shop scheduling problem with blocking where the objective is to minimise the maximum completion time (i.e. makespan). To solve this non-polynomial-hard problem, we propose three algorithms. First, we propose a combination of a branch and bound algorithm with alternative graphs. We investigate the performance of this proposal to get an optimal solution in a reasonable time. Next, we develop two methods based on genetic algorithms (GAs): sequential and parallel GAs. In the former, we propose two different ways to encode the individuals: binary code using alternative arcs and priority rules code. In the latter, we propose a parallelisation of the GA, where the master computer is dedicated to the steps of selection, crossover and mutation, and the other computers (slaves) are concerned with the computation of the individuals fitness. At the end of this paper, we discuss the different results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627304$782CB5E1-1DF1-4903-B490-3BA0FA86C2E5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627304$C501684E-53C0-4059-A7D2-250FB3E54857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627304$6D287C02-3714-4316-9594-A75F6A2A89C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627304$1CC46487-B4DB-4662-B934-E8ACD6ECD581","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"92e21e0bfd1864dcbda2051c00ae9dbd9791d272","datavalue":{"value":"6724662","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627304$4F6DA893-AFB9-49C6-8E29-0AB4EE6225CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b68915f4a637f808d6faf817ad01d5fc56a655a4","datavalue":{"value":"job shop scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627304$28E3F232-10AD-4892-80AF-747C7327E44A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0599a57bd5607ff65212aaaf4d0acda0b4cd6576","datavalue":{"value":"blocking constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627304$0DC7E7B6-BE14-4322-9674-6CCEFF8DD61A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62f3f15b9ea1cb4d2fce3ac57749b66966dca393","datavalue":{"value":"alternative graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627304$1A62C4FA-3042-4FE9-8C86-F421ADB22CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"803d81a5588553e60b505a5dfea64faf9f9b1763","datavalue":{"value":"B\\&B","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627304$4E4596B4-C460-4DE9-8A49-D0584632F5FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627304$335A82F3-5537-4AF4-A6C6-8D282285F18D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75fe65e3fd667d9593c413b9ef971101a95efa67","datavalue":{"value":"parallel genetic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627304$394C7296-9612-466F-A4BC-9236BA75644A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2f7a2d8a09435f07477c37cd30dca31d790c56f","datavalue":{"value":"operational research","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627304$99C36DA0-F0A6-40CF-BF44-4EB2B691ECB5","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":"Q2627304$BA396602-6122-4565-B6DD-CFB78F86A80C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a3b12c70110c4ef40aea901561f5ad3850ad270a","datavalue":{"value":"https://doi.org/10.1504/ijor.2012.047094","type":"string"},"datatype":"url"},"type":"statement","id":"Q2627304$4045B73D-ADF6-4F14-9FCF-1603757F3BAA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"619f3566eb286f60430bbe096c2c16185cc302a4","datavalue":{"value":"W2058920015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627304$CEED2D5B-4928-4D02-84D9-49C704E1DD15","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07110963108bec1018c85dde2205a0058209c1d5","datavalue":{"value":{"entity-type":"item","numeric-id":2627356,"id":"Q2627356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67f4ab4439beba15a0db8dc099bbbfebc3f4405a","datavalue":{"value":{"amount":"+0.8866461515426636","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":"Q2627304$41340F72-9043-445E-A392-D9ACE49E8625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"767ebbebf62e8602d4a7498f0c21e94063085f76","datavalue":{"value":{"entity-type":"item","numeric-id":1273123,"id":"Q1273123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2947ff762991f462a6b2756c221011e6f50a7f87","datavalue":{"value":{"amount":"+0.8098877668380737","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":"Q2627304$6B01C5BA-6754-4C81-838C-653A116C39CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f9ea65fced16cb0600150a9178e4f175edc8d5a","datavalue":{"value":{"entity-type":"item","numeric-id":4980005,"id":"Q4980005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c36a35d1b21f35fb919289e590f265e57fa60cc7","datavalue":{"value":{"amount":"+0.7978617548942566","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":"Q2627304$F581C747-1BC2-4DE3-982A-85FB1DBE14A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ede429dfe128f9a8dff6581392824d853ddb76f","datavalue":{"value":{"entity-type":"item","numeric-id":2204271,"id":"Q2204271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82100897da7d13fd331c689060b740c34733f67c","datavalue":{"value":{"amount":"+0.7940081357955933","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":"Q2627304$88B62579-D80B-484E-9409-ED009F0EAE46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a884eb1614a630c55a756c2740b82bc49c3872c","datavalue":{"value":{"entity-type":"item","numeric-id":1327223,"id":"Q1327223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41962956d1f57f9b4840a39f176eb935ff8f252d","datavalue":{"value":{"amount":"+0.7899379730224609","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":"Q2627304$050A5267-837D-44E3-BE15-4F5806E55AEF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2627304","badges":[]}}}}}