{"entities":{"Q1818565":{"pageid":1829307,"ns":120,"title":"Item:Q1818565","lastrevid":71357100,"modified":"2026-04-13T21:42:17Z","type":"item","id":"Q1818565","labels":{"en":{"language":"en","value":"Open shop scheduling with makespan and total completion time criteria"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1384035"}},"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":"Q1818565$B3DB5B73-03E5-4229-9905-1C33103E161B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8e1d8a48ed4f6e5f8a99e63af73945b2364ad6a1","datavalue":{"value":{"text":"Open shop scheduling with makespan and total completion time criteria","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1818565$9C0FB6DC-0E1B-4128-B8D1-D97A7AD526F9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b544792362eb2db27168c1d45d395d1e174008c2","datavalue":{"value":"0959.90022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818565$BDB065B0-84B7-44F3-8DC3-87FEEC0F12D3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ad15c06ba146bf776409a6013ae29047db029a23","datavalue":{"value":"10.1016/S0305-0548(99)00005-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818565$AEC79CE6-F730-4F65-9CC1-7902686E1F71","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e630590c5ca6e787c3c7b5e291898405495fea2b","datavalue":{"value":{"entity-type":"item","numeric-id":162215,"id":"Q162215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818565$48F4305A-2BB1-42ED-B76C-AF93F3D32656","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8b5bfa12347d4716af416e8493dcfe0d9b94cba5","datavalue":{"value":{"time":"+2000-02-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1818565$EDB591BA-C9C6-4726-AD03-5210C3629188","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"38359be8b224066e6137b401479e0dc94ec7a03f","datavalue":{"value":"In this paper we study the two machine open shop scheduling problem with a hierarchical objective: minimize the total completion time subject to minimum makespan. We show that this problem is distinct from the closely related problem of minimizing the total completion time. We develop polynomial-time algorithms for three special cases and an asymptotically optimal polynomial-time heuristic when a machine is dominant. We also extend some of our results to the three machine open shop case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818565$F80E62A7-8E07-4846-AA6E-59D0F3B27061","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818565$88CF7FB2-6667-4924-8048-1759117C5AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818565$45DEF9DF-AB0A-4700-8148-B1475767B46B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1c2bfc60446bca79a69a40380690af224e0631a3","datavalue":{"value":"1384035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818565$8C9D0044-7434-4F6D-97A6-091352A32F52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd28c5f4d15e2cd6cde7e307b0bb5505f106eb90","datavalue":{"value":"open shop scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818565$57065AC1-E1F8-41BF-988B-DD6FAF0CA0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818565$E28F4A72-9F21-4113-BE56-79B60203B5C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f484efaec285509ff945e4480ef36479c3fed36a","datavalue":{"value":"worst-case performance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818565$553BB5DD-C81F-421E-A4CF-1CF57D697E3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb1eb5e3854e1c0f4b6dec34495648abaf0f012b","datavalue":{"value":{"entity-type":"item","numeric-id":161997,"id":"Q161997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818565$8213B4E4-31DC-4845-B382-C147D9A88F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f426ede6864e26e94b239b82a16147b21286a1bd","datavalue":{"value":{"entity-type":"item","numeric-id":596458,"id":"Q596458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818565$667EE187-FDCF-470E-B683-B86055B604A2","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":"Q1818565$3B7875A3-E223-4047-A131-FCC0EED9F04B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"204e979ffcfbc3d832ce8b6da2da0eaaa289f2b2","datavalue":{"value":"https://doi.org/10.1016/s0305-0548(99)00005-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1818565$7DA242C9-C488-49B4-BAEB-5CB230D5600A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"68d32ff11a0ab559d72b4efa53b5735a0b8e2aa3","datavalue":{"value":"W2045363538","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818565$BC17A071-A739-42E2-B2B5-104F6815DF1B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15cd741d2b99ac860be7a536f34edfc66ca23bef","datavalue":{"value":{"entity-type":"item","numeric-id":1911243,"id":"Q1911243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8de1c3ac5a5a9ca8ef914647713c2b37dbd3df3e","datavalue":{"value":{"amount":"+0.8988508","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$63CC8968-90CB-4304-B3FF-D0DF0E948F10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75a42e697ada700cb98f7996db1d91b63cfafb4f","datavalue":{"value":{"entity-type":"item","numeric-id":1201806,"id":"Q1201806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3eab176c80ea382233557852758a051c518bd93","datavalue":{"value":{"amount":"+0.8981508","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$72367DAE-A87B-42D5-A40B-1BC8DCD98AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ff42b1a13ade9ec6270db92ae162d43f43ac6dd","datavalue":{"value":{"entity-type":"item","numeric-id":346082,"id":"Q346082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3be8149e3638ba7324b5bebb5ed69a0eb42057dc","datavalue":{"value":{"amount":"+0.89472866","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$E6A7DF96-7D17-4C1E-BD97-1274DD99AD22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"304d23e38a6492ffdea7e189ae7017e60a5d8728","datavalue":{"value":{"entity-type":"item","numeric-id":609214,"id":"Q609214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d54199d8a48eb2416e2465bd53b64b8b0787c326","datavalue":{"value":{"amount":"+0.8908229","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$2188E5B7-AF1F-4360-B518-9B322EEB54E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b9546feba26381cb35c207386c8b4423d2071d8","datavalue":{"value":{"entity-type":"item","numeric-id":4287611,"id":"Q4287611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72535174bfcf7a9d1bbe1d02c1ce141fa44f66ae","datavalue":{"value":{"amount":"+0.88993317","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$5BE72657-48A6-419C-91DA-78936F31F33E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f1a3aa217dc98100d4d74d6f91031e94c723023","datavalue":{"value":{"entity-type":"item","numeric-id":3304098,"id":"Q3304098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8df3cde0df68cf6f44b7df4eb223bd8c18fa0c4e","datavalue":{"value":{"amount":"+0.88447607","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$F9D95F6E-0F15-41B1-8495-690603CEE89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cef9682de79288f14de97ceb3a89629905eec94","datavalue":{"value":{"entity-type":"item","numeric-id":1702656,"id":"Q1702656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7f9e6f95a25402589239dde8d27f87762909d09","datavalue":{"value":{"amount":"+0.8839321","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$6D2EFBEE-99D8-4CE4-A304-AA8F3849E44A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f1f0056b2f2ba41c06a3eb51688ac044db2ed1a","datavalue":{"value":{"entity-type":"item","numeric-id":4020512,"id":"Q4020512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34fda0546421587c867a06435ca8e1f964eebb8a","datavalue":{"value":{"amount":"+0.8834985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$88D5D1B0-41C7-4109-B686-037DC31F19F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0308e896b5d7490b6aefa89ebd41d6075ea5c92e","datavalue":{"value":{"entity-type":"item","numeric-id":342284,"id":"Q342284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3482458f21a10870685f8b0212d8cf323c845af","datavalue":{"value":{"amount":"+0.881803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$05A292BA-E13A-4567-AF39-ADB245F17890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edc6f92f7530a58d77fce9b2457728da0d88d3ac","datavalue":{"value":{"entity-type":"item","numeric-id":1086145,"id":"Q1086145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f6c2c52bc61438f987ed58765f81f00f2d4a64e","datavalue":{"value":{"amount":"+0.88001865","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1818565$FC80F8A5-FFE3-48FF-8CFF-7FEF11DA8919","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Open shop scheduling with makespan and total completion time criteria","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Open_shop_scheduling_with_makespan_and_total_completion_time_criteria"}}}}}