{"entities":{"Q1069848":{"pageid":1080600,"ns":120,"title":"Item:Q1069848","lastrevid":66080232,"modified":"2026-04-12T07:24:38Z","type":"item","id":"Q1069848","labels":{"en":{"language":"en","value":"An algorithm for minimizing setups in precedence constrained scheduling"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3936909"}},"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":"Q1069848$E38D036B-A8B8-4FB4-A001-06E175CE06A1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"26cb666f01aef6a7772a2c7ac43635bd45e05868","datavalue":{"value":{"text":"An algorithm for minimizing setups in precedence constrained scheduling","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069848$070240AC-0757-48DF-AA77-2D0E52C6B605","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ee4e54a2a25ba6ca9dda3b11bb6049b5816468ca","datavalue":{"value":"0584.90041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069848$09B4B3EC-6D73-4987-A8FB-0D7272B5E536","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f9143a1bce01344c8ccbe2ea619bf6d38d85fef1","datavalue":{"value":"10.1016/0377-0427(85)90050-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069848$6DF69D4D-2EC2-47EB-BDAB-73FB2C131AA9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1814572f6f5cc98a1bdac6b4fecbd84381c8ff3","datavalue":{"value":{"entity-type":"item","numeric-id":187128,"id":"Q187128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$A47B0C9C-A69F-418C-8A64-562AD678FFB3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9291c21615d62497aa2bb6404791ba4d7844695d","datavalue":{"value":{"entity-type":"item","numeric-id":61355,"id":"Q61355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$64A6A061-7E40-4C3A-A86A-8505BB45908A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1069848$FDA0180B-8FFA-4433-BEA9-8C67D8AD22E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"35c91d3e2c4574f88a31bdf840613235981bd865","datavalue":{"value":"Consider a set of tasks to be scheduled on a single processor subject to precedence constraints. A setup occurs when a task is performed immediately after another task which is not its predecessor. The general problem is to find a schedule minimizing the number of setups. We present a decomposition approach for this problem. This leads to new complexity results and the identification of new classes of precedence constraints for which the problem is efficiently solvable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069848$E20B3A20-7CAF-4F09-8404-D125D614F412","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069848$05DCF58D-B30E-4797-9CE5-B5DDB6C65298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069848$4F5F22DD-9837-4B79-9075-DF1A03FBCE93","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"31c527641c152f7577f923c2b81e968309d01164","datavalue":{"value":"3936909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069848$1BF6B5FC-4C80-4DDA-BC97-71B194B06C7C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29e4fef7c1e7ae15bf1e964c65fd5826e2802adf","datavalue":{"value":"minimizing setups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069848$9B208C0C-C282-4492-91E1-F04B87AC6247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbd4bc26baabcbae091630e4b9e44960328dad8a","datavalue":{"value":"single processor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069848$8469C3CC-3502-4A5D-A427-B2F2F107A333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbe4779b21482c6f7af163070358f952601735bf","datavalue":{"value":"precedence constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069848$678D6B88-8CA7-4ADB-B38E-E83144BAA89D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ef68a81b65c0d9cafc10149871a7a6fca34d2f1","datavalue":{"value":"decomposition approach","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069848$A612E980-03FE-453A-8B33-B1C2D76472F5","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":"Q1069848$7831B2A4-595B-4DF1-9551-15606E1634BD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c80b08013bb7fddc350a2cf368e99e89ee5aaca","datavalue":{"value":"https://doi.org/10.1016/0377-0427(85)90050-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069848$B5D58139-3A09-4EF6-9B8A-BDB786248FAD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"007b220e5b781303137c5f8b4b6e4d97fb6a97cb","datavalue":{"value":"W2050090155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069848$984D9EAC-9875-44CB-AE5A-DE3A1EF1E37D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"13a13bf5ea222488a462597a035d6c581000a87a","datavalue":{"value":{"entity-type":"item","numeric-id":3665151,"id":"Q3665151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$7AE40CFC-1D45-4BD9-BACD-ACDE5CEA5644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92c286ab8d4759a4b8b69c0d618f8b684c847186","datavalue":{"value":{"entity-type":"item","numeric-id":3889080,"id":"Q3889080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$6B1188E5-37DB-435C-80C0-1863F7E1D656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"433aacb3b753ddf861d4b3d2e5750f83f114a9ac","datavalue":{"value":{"entity-type":"item","numeric-id":4200070,"id":"Q4200070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$C58977B9-52F1-437D-8C80-D75CA4B17590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d4d8a1c3628c934e726723cf3f6edf3c81d6fd1","datavalue":{"value":{"entity-type":"item","numeric-id":3960725,"id":"Q3960725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$05B1EBC7-60D2-4DEF-AAD7-D94AAE37E0DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8553feea678bc899d05f5a147512f8d0b1b46f91","datavalue":{"value":{"entity-type":"item","numeric-id":3960747,"id":"Q3960747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$0977BD94-7756-4BF7-933B-689D3263FC2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f159aacfddbc201f6b79ecf804a940116897f8f","datavalue":{"value":{"entity-type":"item","numeric-id":1061150,"id":"Q1061150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$76CB81A1-F13C-4BCA-9576-FE7EA2E5DE79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7719de6c339bb9d4088f30d5f516e35f5c2b87f","datavalue":{"value":{"entity-type":"item","numeric-id":3694689,"id":"Q3694689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$B2E38C5D-55D8-47B8-9D73-10281A251C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9e52059a589250b5c3bf927a52af00cebfb990d","datavalue":{"value":{"entity-type":"item","numeric-id":3665161,"id":"Q3665161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$CCC829AF-DD44-4A0C-BA96-F8DA0E9524A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"befdb7fe1eaca43bc37060727dd405b397d1b5cc","datavalue":{"value":{"entity-type":"item","numeric-id":3940839,"id":"Q3940839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$E4D44423-A134-43C0-BF05-B0A80E808BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63d7deaf3e7bac9de0ff67356dbe46db811c5ca2","datavalue":{"value":{"entity-type":"item","numeric-id":1052820,"id":"Q1052820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$A255BA73-F360-43DC-A52A-0577E63D0AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0050e04cd523c25072c5f0f9c9964b473a93b40d","datavalue":{"value":{"entity-type":"item","numeric-id":4080661,"id":"Q4080661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$01E10A83-2B53-4B9F-BEB2-6B37B8CA3457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d4c3394fe33a803d44b9613be7e42b3f4c68ee4","datavalue":{"value":{"entity-type":"item","numeric-id":3674720,"id":"Q3674720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$1C3E14D4-7F91-4BEA-8A99-61E5E7E0C429","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565e1c631f28f5626e28b4b72f070c887ee0b094","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$B0151C81-C7C3-4027-9C44-1928377B2EBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9b4c2bc9c2f01a8608a2c200aa0923fb77f3748","datavalue":{"value":{"entity-type":"item","numeric-id":3929382,"id":"Q3929382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$4930FDE9-A1E4-46D2-ABA9-3ADCE68C0641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c2cfdcb3f43e41c76ef35cfb4432d7694d67bf8","datavalue":{"value":{"entity-type":"item","numeric-id":1163377,"id":"Q1163377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$72163AA5-F451-4298-A6C2-F7DEB71F0815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fcfe987d8cbbd43f7b7238b024d7a85de33a069","datavalue":{"value":{"entity-type":"item","numeric-id":3936212,"id":"Q3936212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069848$D1179A7B-57F5-44CA-8968-1ECD1E04DC6B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e920f8d0227f208eef88c747e8cfed7efc4a79e","datavalue":{"value":{"entity-type":"item","numeric-id":794156,"id":"Q794156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5212fe56f5afc58929ced4e8a2aa87766908897","datavalue":{"value":{"amount":"+0.8054060339927673","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":"Q1069848$E56194B3-F2DA-4FBB-9C37-E3B4CA2AD7A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff2ff8033995ab664776b1d315e0322cfe3d8cd5","datavalue":{"value":{"entity-type":"item","numeric-id":1421479,"id":"Q1421479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbb2c0aafac7b149211d7837904c0a1105a7c6fe","datavalue":{"value":{"amount":"+0.8012540936470032","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":"Q1069848$568B031B-5366-47AE-99CB-F05B55B74EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4924ecc431320a391d765cfe84eadba92b9aa682","datavalue":{"value":{"entity-type":"item","numeric-id":3929382,"id":"Q3929382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab70974906512488a12e5b024d97f2116efbda82","datavalue":{"value":{"amount":"+0.7906628847122192","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":"Q1069848$D2ADB39F-D95F-4FC3-95F5-BF1D8BBFF715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71ffe42b80c208c8ef7b4dad2313722be1d7e1fd","datavalue":{"value":{"entity-type":"item","numeric-id":3815123,"id":"Q3815123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3847140f870acbb1c7f7e19528736948467e14a1","datavalue":{"value":{"amount":"+0.7800180315971375","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":"Q1069848$07450644-DED5-4BB7-AF2C-D97DEC923660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a26cb75e0a306d295c2f5b0b2cdd3bbae2ad12eb","datavalue":{"value":{"entity-type":"item","numeric-id":4859027,"id":"Q4859027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5977f01d1cf4d5050cd08b569391f6d137c8470","datavalue":{"value":{"amount":"+0.771371066570282","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":"Q1069848$CD9C078B-4805-4913-B06F-7DE8694FB4EB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algorithm for minimizing setups in precedence constrained scheduling","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algorithm_for_minimizing_setups_in_precedence_constrained_scheduling"}}}}}