{"entities":{"Q1196724":{"pageid":1207473,"ns":120,"title":"Item:Q1196724","lastrevid":66840276,"modified":"2026-04-12T13:13:04Z","type":"item","id":"Q1196724","labels":{"en":{"language":"en","value":"A time indexed formulation of non-preemptive single machine scheduling problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 89478"}},"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":"Q1196724$669A5792-B787-4CB6-9BFE-789F6C7428B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f3c8a8906a78de8fe5189c0777782633cd21fecf","datavalue":{"value":{"text":"A time indexed formulation of non-preemptive single machine scheduling problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1196724$5EB19AB6-032D-4592-BE16-0AC229EDD22F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"95baee93340a3e320e57d69fbc1117512303f4ec","datavalue":{"value":"0768.90041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196724$EC029028-3097-4021-9FFB-8B72977CC6C1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cac4b0bff583045dde01028802124b89143b83f4","datavalue":{"value":"10.1007/BF01586059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196724$B8AA566A-1520-4E32-896F-D75B1AA77B98","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"128d1743c9f1fab637695be01647b39d33fe0d56","datavalue":{"value":{"entity-type":"item","numeric-id":173889,"id":"Q173889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$BE69A06E-B017-4679-B5C4-8F2CF051936D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"234a212ea43f03ff4cb3faead80835a69d913cf6","datavalue":{"value":{"entity-type":"item","numeric-id":596260,"id":"Q596260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$7988BB8B-1D1D-41C5-B03F-CD5C1D2E9B12","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$106B4D87-5306-4124-870D-251E8C09FF3F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1196724$02186825-82FF-434F-9003-C97EFF6DC999","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5aa12d08565ee029488e87bd70bb4215d8c58a65","datavalue":{"value":"The authors develop a time-indexed formulation for the general, non- preemptive, single machine scheduling problem. The advantage of this formulation is that restrictions like dead lines and release dates can easily be included and different objective functions, like weighted completion times and weighted tardiness, can be used. On the other hand, the model is quite large, the number of variables and constraints is pseudopolynomial in the number of jobs.   The authors provide valid inequalities for the formulation and present the computational results for a first implementation of a cutting plane algorithm based on these valid inequalities. Although only small problems of up to 30 jobs are used the results indicate that the solution method is efficient for this kind of single machine problems compared with a branch-and-bound solution method. It should be mentioned that due to the large model this method may only be used for very hard problems, i.e. for problems which are NP-hard in the strong sense.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$3D40B842-7C45-474D-9FF7-71A0F9BAAFD4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196724$33E4E395-D4A5-49BB-9F51-D2226C4DD08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196724$C7C8C3D7-3440-486A-BB9B-116F141F42DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196724$8D6014C4-55E3-4E46-8E35-A590095D72B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"85ac1487d03b7b93c43bea846d9ac28f4ef2ca47","datavalue":{"value":"89478","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196724$B4C06EB0-62F8-4456-B02E-E3E8AE49B39D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0facbdeb102213857d267508b6ad370d5d8fe80f","datavalue":{"value":"non-preemptive, single machine scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$8C2573F1-E502-4ED5-9998-CDF25FD6FF08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c10accf055a83291fdb4449761b77e6bd36d75df","datavalue":{"value":"dead lines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$D5835567-0D60-4A06-B942-D96E755F9FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fdadf78f35fb16296cd1dad4147bd52b7a36b85","datavalue":{"value":"release dates","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$4DB61E61-EC76-488B-ADFB-5470FC70504E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8bcd324162d52b18ad1c045ffe45af3e1328acc","datavalue":{"value":"weighted completion times","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$0FA6A762-A7B2-4EDD-BC86-A54D1BFC76C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4385ee8c3b382adc00d99b2a9393ea25e2f39709","datavalue":{"value":"weighted tardiness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$D6D0591E-5B67-4FBF-A1F7-CA28A02F1271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"716dac1111922ad89f28f3f7f9fca3441a4dfa26","datavalue":{"value":"valid inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$0720D55D-9AE8-4B5C-86A1-73F08BBE38EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5bbd8c55216bc58296fa2ade785c5de51a5a6c4","datavalue":{"value":"cutting plane algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$714FB6B5-1FF5-4305-9F0D-9CE7A4FE55AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196724$B0061A8F-679A-4858-A32E-7885291AAE5E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0fde83111797a0d59e7015849b12b6c917e7b4a1","datavalue":{"value":{"entity-type":"item","numeric-id":778892,"id":"Q778892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$8E1DC352-22B6-42A1-B137-A7E37BC8D8F5","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":"Q1196724$017209CA-C928-4C6B-94B5-CFAF5DC2B68C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"16babf709e218bed30c1c8efd5d2103ecf76ba53","datavalue":{"value":{"entity-type":"item","numeric-id":3802870,"id":"Q3802870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$2846D653-B9EE-459E-8B68-C69D9B75691E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"186e07849363b1ab990dafa5dd6fb5c40e9cf001","datavalue":{"value":{"entity-type":"item","numeric-id":3778528,"id":"Q3778528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$654A1532-B7B8-4704-9BAA-6352D49B6D12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e9ef3c6051a0049c2eeb79dfe89457927227bff","datavalue":{"value":{"entity-type":"item","numeric-id":4077731,"id":"Q4077731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$014E84DF-B735-4B18-94E8-E5A0DE9B3B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07e7fc9a229345ae31b665ce7bcb9fb2425c4f5c","datavalue":{"value":{"entity-type":"item","numeric-id":1145613,"id":"Q1145613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$4BA56E5D-BAC5-4FE9-B8B5-0C8A88D2C141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1a95678ebc5c91e79ed23a46e2e9f058ad57f3f","datavalue":{"value":{"entity-type":"item","numeric-id":4903786,"id":"Q4903786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$992AC2C9-A86E-4D0F-B1B7-F5DA38AE620A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f1d093b01eb63a522b353371a5cda71ab1c0889","datavalue":{"value":{"entity-type":"item","numeric-id":1162927,"id":"Q1162927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$5B12E772-98A0-4856-8F01-0B672842DDAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d32aa48da8b42b45cf38bfdbcd2e94564dbc31","datavalue":{"value":{"entity-type":"item","numeric-id":1820682,"id":"Q1820682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$CDFEF304-4261-4674-926D-3FF7C2FCDC65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1011cc634112defc2d3c1b58fb060cd48a77b9a","datavalue":{"value":{"entity-type":"item","numeric-id":4126042,"id":"Q4126042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$946EB994-F886-45B9-B536-7E8602006072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2db61ed3bd2daa5567129ab953c97e8021a15f2f","datavalue":{"value":{"entity-type":"item","numeric-id":909575,"id":"Q909575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$0CC47FF3-8F39-4BF7-897E-EF98104F4C1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0676cd840d957fefbd0f858acb78cb7f5fc4bcb6","datavalue":{"value":{"entity-type":"item","numeric-id":1171502,"id":"Q1171502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$0EDD3CCE-8FE9-4958-831E-DBFC7ED78604","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":"Q1196724$D4E9DB69-5CFA-4C81-96EF-DACECBAD8501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4ae368f5009736f85a97fcebaf4630774830353","datavalue":{"value":{"entity-type":"item","numeric-id":4124328,"id":"Q4124328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$A1A646FB-566D-4FDE-BCBE-FDD9BE0E63F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69cb8c6d9a5cca58273eebea90268f9de4f47dcf","datavalue":{"value":{"entity-type":"item","numeric-id":4147830,"id":"Q4147830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$081335AF-345B-4049-8CF2-09969E83AC7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9e5cb8b1133c4a0a5c82c65624bc1532a4a7162","datavalue":{"value":{"entity-type":"item","numeric-id":3694968,"id":"Q3694968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$38D9A71A-D040-4406-B52E-257EDD6C9363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9652ec329b4f19309eefba03ba215ca5c28ba3e","datavalue":{"value":{"entity-type":"item","numeric-id":1170111,"id":"Q1170111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$382E38D5-589E-4871-BE36-1A1CAEA4B054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0d66570d6859fb460463e2341fac6cb2a4fe959","datavalue":{"value":{"entity-type":"item","numeric-id":2563111,"id":"Q2563111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$83D3BA2B-AE47-4E4E-A8BF-A85955603CA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b98571bba49dd46b80d874562c4a255dd01ee1c","datavalue":{"value":{"entity-type":"item","numeric-id":4088561,"id":"Q4088561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$004C58B4-D614-49E8-BE91-8F70B2A2465A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84ceff3f2347f77904a1f78c08a0b721c448a7ed","datavalue":{"value":{"entity-type":"item","numeric-id":5639517,"id":"Q5639517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$F1087134-A91E-488E-B4C0-0AABC470AF07","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":"Q1196724$D61D1835-06A9-4BA6-8DFE-FED37208CDBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f76ce33d0ecc1667b526729d4ba758851c5da17b","datavalue":{"value":{"entity-type":"item","numeric-id":2639772,"id":"Q2639772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196724$F1C431CA-1F76-4546-9B78-42EDC6E46057","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"85b7113b83f2dfba74b6bfb107b92ca1f07e1190","datavalue":{"value":"https://doi.org/10.1007/bf01586059","type":"string"},"datatype":"url"},"type":"statement","id":"Q1196724$51F41983-52AC-4D14-9B62-F0F2170A1294","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0612c76e1a9079e22a3992427eeb5505618b1b3a","datavalue":{"value":"W2060552317","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196724$39676A6F-A0C8-449A-988C-93968063D818","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96b172346644b28a4b5bc55d9b50bf9b7dd58923","datavalue":{"value":{"entity-type":"item","numeric-id":1586211,"id":"Q1586211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8060afe34085f30e1a43e61193c05474cdce8665","datavalue":{"value":{"amount":"+0.8736348152160645","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":"Q1196724$A07D6E41-5E56-44C7-AA2B-6642FEA383B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f39493e52cfe5c25cedfbf4052994b0da060071","datavalue":{"value":{"entity-type":"item","numeric-id":4035632,"id":"Q4035632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7968c9c6e3bff5838af481f2bdfcdf8187cb18f5","datavalue":{"value":{"amount":"+0.8306659460067749","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":"Q1196724$E9CF2667-DA3A-4377-AE5D-6B3146D3B231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0bb055556d610c856de02bd6d5f5e293226faed","datavalue":{"value":{"entity-type":"item","numeric-id":5002323,"id":"Q5002323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7968c9c6e3bff5838af481f2bdfcdf8187cb18f5","datavalue":{"value":{"amount":"+0.8306659460067749","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":"Q1196724$E57C7426-9F37-4389-8896-46F19C71E2F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d132d96a015ecf562ef258bab9b9b9f76fd97ddf","datavalue":{"value":{"entity-type":"item","numeric-id":1785357,"id":"Q1785357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4156e61202f30a478458e086f96400c197ee8cba","datavalue":{"value":{"amount":"+0.8239297270774841","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":"Q1196724$BE89F4BF-9636-4BF7-9B0C-4CE0C35FA655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"760f82d556bbc33268e7707e5bc0cf729234ac53","datavalue":{"value":{"entity-type":"item","numeric-id":2806861,"id":"Q2806861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81772b1f69f7149d710dd7bb8b237e6d0232dd40","datavalue":{"value":{"amount":"+0.8233500719070435","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":"Q1196724$E268B04C-28C5-41FF-BABF-38A312DBC83B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A time indexed formulation of non-preemptive single machine scheduling problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_time_indexed_formulation_of_non-preemptive_single_machine_scheduling_problems"}}}}}