{"entities":{"Q908846":{"pageid":910694,"ns":120,"title":"Item:Q908846","lastrevid":65270955,"modified":"2026-04-12T01:26:45Z","type":"item","id":"Q908846","labels":{"en":{"language":"en","value":"A survey of results for sequencing problems with controllable processing times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4135701"}},"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":"Q908846$4E2E908A-37B1-4FF3-B2EE-23C45ACD4613","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"05bbaa3932155e720e48109c74648ed0be4badce","datavalue":{"value":{"text":"A survey of results for sequencing problems with controllable processing times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q908846$D067E4EF-7272-4393-9F41-C72024C7B68B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a178fe5868888be5e2294da5c99b5486cbbba168","datavalue":{"value":"0693.90056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908846$E0D875D4-03AF-4DF9-8029-34917278D56D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c3630525e46cceb164616a7ed102a4db8f474926","datavalue":{"value":"10.1016/0166-218X(90)90105-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908846$2DCB1800-325C-4072-8632-E52024B4118E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$46A3EB38-1C87-4A73-A698-A392DDA71334","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q908846$3B0FDADB-D4FA-4E06-AD0A-DB36CF40970D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"83f98bf3dd3b44b87de97cd91396710b73440031","datavalue":{"value":"This paper reviews algorithms and complexity results for scheduling problems in which the processing time of a job is a decision variable. For each job, an upper and lower bound on its processing time is specified and a processing cost, which is a linear decreasing function of processing time, is given. In addition to the processing cost, a schedule cost (maximum completion time, maximum lateness or total weighted completion time, for example) is associate with completion times of the jobs. Most results relate to the problem of scheduling a single machine to minimize the processing plus schedule cost. Throughout the paper, a typical algorithm first selects a processing order of the jobs and then solves a linear program to fix the processing times; this linear program can often be solved very efficiently. For some problems, this type of algorithm provides an exact solution; for others, it is a heuristic and worst-case performance bounds are available.","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$FB727845-1EB4-4E91-90A0-80B44B50F34F","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":"Q908846$467B39A9-1E13-4638-97A7-7BEC9CAA6BEC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908846$8A2E5F9A-04A7-4928-86A2-98F8841A7A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908846$D5144E04-D6D2-4A28-BB5F-3A929921DB60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908846$4E2DA454-66C9-4933-BE71-4F8C4573382D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d6400467fda46614eb58b4085a94e8fe6d5c4d3d","datavalue":{"value":"4135701","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908846$44ADD501-24CE-4BBD-A07F-9660B1F77402","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f9dabdb5415b4d0c74b0865a533c2994a0aea38","datavalue":{"value":"controllable processing time","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$70CC94DD-29B7-475F-A255-97F1F2A72C4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$B5030E6B-90F8-4256-A47D-7514DB448064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e2c88cf105fe5835137ad2fa3a42c08ea633895","datavalue":{"value":"complexity results","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$7F9A9BFC-7877-4698-B725-D5B66D9F38FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$1E4F02E0-F4C6-441E-A1F2-BBADB5AD7FA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edae7761f34acf97f2d43de39f62b25834213f9a","datavalue":{"value":"maximum completion time","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$C5FC4870-20A8-483A-A129-0CC158765DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d16cc5a85aeee9b68b2e66907bf512d1671f689","datavalue":{"value":"maximum lateness","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$FE1B1DB2-16C4-4087-9D71-EC9CA967EBAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"beba3f4683c103764a205d75b33eb4bbf8e74aa9","datavalue":{"value":"total weighted completion time","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$5C3B1CD7-7969-4619-9EF8-3CB1E4D4C9D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1ca53a04f8c624238a62137bcb0acb8058cd7ee","datavalue":{"value":"single machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$BE4E9103-1F47-4227-8D37-C671EA9BDB4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$4E6D294D-71EF-457D-9582-72ABE3E9E4C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f484efaec285509ff945e4480ef36479c3fed36a","datavalue":{"value":"worst-case performance","type":"string"},"datatype":"string"},"type":"statement","id":"Q908846$3D8C280B-7CD6-49B3-A433-59277F46C198","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":"Q908846$5A29EC24-85E2-4476-A3A4-4F8E3B5CA000","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":"Q908846$FEE7A757-E6A0-40BC-B957-DF229B52392A","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":"Q908846$A30A9C54-785A-4DC1-AD72-DB20F3353BB5","rank":"normal"}],"P223":[{"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":"Q908846$DE2714D5-E4E0-4F4F-8A8F-458EA34C7F5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98bcae446081e9f29447fc3d35c911dd1b90a71b","datavalue":{"value":{"entity-type":"item","numeric-id":5603740,"id":"Q5603740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$3F26F0B7-510E-476F-A36D-CF066CE308E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b635f06f6c39b03ca513d0a3eb06ec0cc20b065","datavalue":{"value":{"entity-type":"item","numeric-id":1820680,"id":"Q1820680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$E3F1B8CB-7762-4631-B923-85486C88642F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"206aac1fed08722358479159401448a8a87bf332","datavalue":{"value":{"entity-type":"item","numeric-id":4198327,"id":"Q4198327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$3E084AA5-5001-4255-A6FD-E9127EB89AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f3ea8bcb92a4f37d2ed0c6b49c6c88ccfc8d17d","datavalue":{"value":{"entity-type":"item","numeric-id":3714887,"id":"Q3714887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$0F973E54-DFE2-47EF-8D96-3EEB1D71A731","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":"Q908846$2317D55D-2D50-4377-B0D5-7E7A1C632AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72530a1c80ee955b2ed33b7a53414bb24ae60e0c","datavalue":{"value":{"entity-type":"item","numeric-id":4103320,"id":"Q4103320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$8652B5D5-840C-43CF-B865-49702E5A37BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$2B58F7A1-68B3-429A-B344-3F71C75E5AD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565dd9f994f9ad40804f24534c6e2ebb318c8a1d","datavalue":{"value":{"entity-type":"item","numeric-id":5576138,"id":"Q5576138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$2189970B-C26C-4E79-97ED-0920E9EE81BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a54363cab19ddaa83ba50c46c8127b159b14d03","datavalue":{"value":{"entity-type":"item","numeric-id":4055377,"id":"Q4055377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$830F9B48-B238-43A0-A1C8-18316C897CF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7ac8e2c5ae9a5037a50820a004eee629907d451","datavalue":{"value":{"entity-type":"item","numeric-id":1104846,"id":"Q1104846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$8D3D509F-9AAC-4C11-870A-2D367B21C14B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696d2c12656116930cbe8540683b849a20624320","datavalue":{"value":{"entity-type":"item","numeric-id":3893644,"id":"Q3893644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$01BCDDDC-510A-4C42-9759-D8363C1E8F42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f853eb538c1496c7c69cfc60affcd340a219cf90","datavalue":{"value":{"entity-type":"item","numeric-id":3329208,"id":"Q3329208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$18C514C0-2971-46FF-BDC8-599F1B9891CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a4a3fe88bba5d3a5c8a0fd8473f6aa057c64525","datavalue":{"value":{"entity-type":"item","numeric-id":1150305,"id":"Q1150305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$845C8B5B-FB65-4C06-94C6-1260B0805372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed1f6461430557cea195f2713f044d9dc3a672da","datavalue":{"value":{"entity-type":"item","numeric-id":3956727,"id":"Q3956727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$6346393C-8E64-47EA-9C33-83ADC635FE45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c29a4e6e136c12003832d356dbf7f51ae7d722d","datavalue":{"value":{"entity-type":"item","numeric-id":3690568,"id":"Q3690568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$A7CFB6B3-56DF-49F7-A97A-8553986DB678","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":"Q908846$A336D26E-5BD4-487C-9E6D-55FE3BB1645C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43db55498f087131aba80db602336c37534874f6","datavalue":{"value":{"entity-type":"item","numeric-id":1162923,"id":"Q1162923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908846$D5E76583-5FF3-4358-892B-B250C3600827","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"306f4d3f22bd6587c121fd8c80fd25fac735b754","datavalue":{"value":"https://doi.org/10.1016/0166-218x(90)90105-l","type":"string"},"datatype":"url"},"type":"statement","id":"Q908846$711B81C5-0319-40D7-B59A-4F61CA3D922B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c5fa5ac7686125e9a13caec2f82969eae46afafd","datavalue":{"value":"W2020909460","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908846$CCDA98EA-B217-4628-BCC5-C3F10584C9A1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9103443d6bd816dd05967eb48b888ce944f754d","datavalue":{"value":{"entity-type":"item","numeric-id":1599819,"id":"Q1599819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58def36774955f52698ce7178d312cbea0422a89","datavalue":{"value":{"amount":"+0.8929656147956848","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":"Q908846$0A766FA2-CF86-4D3C-9053-EDA7B3CBFE9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81a0aa81b4927280a53ac5040fecb1647e18a90b","datavalue":{"value":{"entity-type":"item","numeric-id":2381529,"id":"Q2381529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3f9ad542047534f0d4e9fb896c109430eb0ed2f","datavalue":{"value":{"amount":"+0.8897872567176819","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":"Q908846$40EE4FDD-B38E-4F22-957C-905F7DF57BFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28198f24c0f505e856370b18bfc5bd909acfb9cf","datavalue":{"value":{"entity-type":"item","numeric-id":3809574,"id":"Q3809574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68e4c68b233ae4dc063c33f5406b1947b6bc30cb","datavalue":{"value":{"amount":"+0.8893947005271912","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":"Q908846$C3D47795-DDFE-43E1-88A1-6A6FA8818684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a0e192d86eec4aacd609d4042378c784282eeb8","datavalue":{"value":{"entity-type":"item","numeric-id":1288216,"id":"Q1288216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32c60f4615bf33cea107f976f2ceca7950d78926","datavalue":{"value":{"amount":"+0.8775010108947754","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":"Q908846$D70EDE58-F90C-41B5-8C13-2A43BB708E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1000ea824b7c20547f7aecaffe8f2a5f57f01e75","datavalue":{"value":{"entity-type":"item","numeric-id":1310019,"id":"Q1310019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7003104a2d58827fd4c7b4d720fc8f5ac1ea990","datavalue":{"value":{"amount":"+0.869337260723114","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":"Q908846$E99CA3B6-61AF-47CC-9972-FEE4879F5CBA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A survey of results for sequencing problems with controllable processing times","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_survey_of_results_for_sequencing_problems_with_controllable_processing_times"}}}}}