{"entities":{"Q1104846":{"pageid":1115595,"ns":120,"title":"Item:Q1104846","lastrevid":70098873,"modified":"2026-04-13T12:25:48Z","type":"item","id":"Q1104846","labels":{"en":{"language":"en","value":"A two-machine flow shop scheduling problem with controllable job processing times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4057265"}},"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":"Q1104846$15C0D6CA-C92C-4E01-97C8-821B47AFBCC0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4b6d63f8f96f1515427e61b00213b55d2784afd6","datavalue":{"value":{"text":"A two-machine flow shop scheduling problem with controllable job processing times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104846$4F0106AB-BBFC-45DD-92F7-1468E8F516F1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9dd7dad7e17bf2495242d9b2b7aeebfd752edace","datavalue":{"value":"0647.90041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104846$B4CA2E95-B648-485C-9293-70C1A2EBD740","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bdeccdcf0633f574f2ea6f64a779b48fb2df6025","datavalue":{"value":"10.1016/0377-2217(88)90355-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104846$CFD39C5E-F6CC-4B3B-BF0B-716862542C71","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7542e378203ce39231c5f7b719109e246636e043","datavalue":{"value":{"entity-type":"item","numeric-id":689948,"id":"Q689948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$404D4FB5-8220-47C6-99C2-B77B6069CD4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac05114ba19da03d2c5d80abdf4db552bc715014","datavalue":{"value":{"entity-type":"item","numeric-id":1065704,"id":"Q1065704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$ED53B978-FE7A-4A11-B41A-82F5CCCC295B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$96DE3C76-D196-476F-8B05-20FE823980AF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1104846$D496BB6B-D4A0-401E-B82A-16A741780A8B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ff182c7ff70139f2185669ac5c35eb13205a18e","datavalue":{"value":"The two-machine flow-shop problem is considered in which processing times are decision variables. For each job, upper and lower limits on its processing time on the two machines are specified. The processing cost of each operation is a decreasing linear function of the selected processing time. The objective is to minimize the maximum completion time plus the total processing cost. The problem is shown to be NP-hard, thus justifying the use of two heuristics which are proposed. Both heuristics select a sequence of jobs and then use linear programming to find the processing times. The first heuristic uses an arbitrary sequence and is shown to have a worst-case performance ratio of 2. In the second heuristic, the sequence is obtained by solving a two-machine flow- shop problem with fixed processing times; this reduces the worst-case performance ratio to 3 / 2.   Further analysis for this second heuristic provides some additional worst-case performance bounds which are dependent on the data.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104846$CBB444C1-DEA4-4E5F-9F1A-FBD464F961F1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e7c71cb6db7e3f55150cd62e2bbcf6bbc70b9472","datavalue":{"value":{"entity-type":"item","numeric-id":761339,"id":"Q761339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$7AC4B282-3002-4F90-871F-196C16AB112D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104846$6083423B-E22C-4F49-B225-231601E477F1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"546465be48b66bd137548855d013b37dbb2977d5","datavalue":{"value":"4057265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104846$29299930-CCFD-4709-A5BA-D457E5300EBA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad93bd1c9e28c13f495ac3192cd5515214205444","datavalue":{"value":"controllable processing times","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104846$6E498698-030D-4032-A8CE-DAB31A39ABFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14f5692e185b1488dd97e357834d4b024a1d4fa4","datavalue":{"value":"worst-case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104846$D5AB9AC8-6C9A-4028-A66F-BAB08BAD7A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0c3711ef3f1f7114b30d7149bee99ad85f83dea","datavalue":{"value":"two-machine flow- shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104846$25BF1F09-ED82-4594-A50A-F591DBEDF4C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104846$9C4684C6-FF53-4F95-B1FE-64C76C574DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104846$F82DE4F9-2F07-4532-91F7-F22A317C2CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c22d33e567cf57c1d49c02a5e07c657275af56c","datavalue":{"value":"worst-case performance ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104846$EB7ED944-B335-4194-93D9-4A8C967CD83A","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":"Q1104846$CF312B3D-AC4A-4D64-BE49-4EA76262BE77","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b8e7d6f9ec795040b0c7032240ddb29cb7469d5e","datavalue":{"value":"https://doi.org/10.1016/0377-2217(88)90355-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104846$5559D438-554E-402A-80AF-5E29EC330494","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"504e458cfa1d017c773bc6092f2570da4699bd8c","datavalue":{"value":"W2019327330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104846$30E34FF9-6AD1-44AD-BDCC-782C501441BD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f69a74e308f73d0ad3e29bde22f0c7cd163d4f","datavalue":{"value":{"entity-type":"item","numeric-id":4658190,"id":"Q4658190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$B570CCC1-BE6A-457E-8DE9-600BD85E607A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8cf99833f26fdbf5ecd5bec73d5352af950d0db","datavalue":{"value":{"entity-type":"item","numeric-id":3941193,"id":"Q3941193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$C4077648-CF86-4A94-BC23-F34C6BE5AC3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f36232ae77f8c7dd3d32ca83e7370d4ed2a13cc7","datavalue":{"value":{"entity-type":"item","numeric-id":2834736,"id":"Q2834736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$B845F58F-274C-4ACD-8934-361DFA64614B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$3A22B3A1-96F0-4394-9B8A-5D47329C24AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d42877972cd851c0575110e288975ecfe9d3791","datavalue":{"value":{"entity-type":"item","numeric-id":1846330,"id":"Q1846330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$D0A38A4D-5F55-4108-9740-E4695640C402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32b93f988d8f2a266836f50fa98dad88e2a4fb01","datavalue":{"value":{"entity-type":"item","numeric-id":3896830,"id":"Q3896830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104846$A5DCECE2-DA5A-4593-A0AB-5E353E9FDDCF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5bdf9af60e3a4de5729183c71152c4524585152","datavalue":{"value":{"entity-type":"item","numeric-id":3760285,"id":"Q3760285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f349a116441765c42eafb9191c26eedd72539a1c","datavalue":{"value":{"amount":"+0.9385955333709716","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":"Q1104846$728E5FE9-CD9C-404B-AF54-D1E5DDDDB242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9202457142e7f6adc37112f58f52368da2057bd","datavalue":{"value":{"entity-type":"item","numeric-id":3806976,"id":"Q3806976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a2d0be633c508b8dcf16d060570a0ba9cecec12","datavalue":{"value":{"amount":"+0.9368372559547424","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":"Q1104846$EA35EA88-03D3-48AB-9E91-3D5E779D0484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed9e9a9645a2009a94d33882af4c12668914feb0","datavalue":{"value":{"entity-type":"item","numeric-id":2916936,"id":"Q2916936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29226fb9c4c0fee44c563bba3ca9af80acff385b","datavalue":{"value":{"amount":"+0.8856865763664246","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":"Q1104846$2F2612C6-1B74-495B-81C3-42D55619A9E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba5001b442682aa87378708abfbcdcae0e63a6ac","datavalue":{"value":{"entity-type":"item","numeric-id":3486356,"id":"Q3486356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c55388b0ecb7024fa0701ace32847161bc8ce06","datavalue":{"value":{"amount":"+0.8726905584335327","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":"Q1104846$330668DF-A1C6-41D1-BD65-7A725B71BD3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51b5888f91d118ea8d2ab9978f630bcb7cc1ecc2","datavalue":{"value":{"entity-type":"item","numeric-id":1310020,"id":"Q1310020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1062eaf2bf34cbc79387f9c3288eb80b2fbb2ec6","datavalue":{"value":{"amount":"+0.8700465559959412","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":"Q1104846$EDAD0D11-A9F9-4840-866C-7D7C1F5D57F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A two-machine flow shop scheduling problem with controllable job processing times","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_two-machine_flow_shop_scheduling_problem_with_controllable_job_processing_times"}}}}}