{"entities":{"Q3329201":{"pageid":3339909,"ns":120,"title":"Item:Q3329201","lastrevid":110418662,"modified":"2026-11-16T20:08:32Z","type":"item","id":"Q3329201","labels":{"en":{"language":"en","value":"Single Machine Scheduling with Precedence Constraints of Dimension 2"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3860869"}},"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":"Q3329201$238F7F54-6319-43FF-9F5C-7DE75BCCCA10","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"50d3b51a9a941c96d4e99f1931bdbeedaee48ac0","datavalue":{"value":{"text":"Single Machine Scheduling with Precedence Constraints of Dimension 2","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3329201$C553C82D-2EF9-4205-A16E-5F51F36C2A29","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"11ee96fd4345827ef08ca6e9892d1eb7584e9481","datavalue":{"value":"0541.90054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3329201$EA02AF6D-5F11-42A8-87D4-451D427E1147","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":"Q3329201$C92A37E4-10B9-4583-B8E6-80F03D631400","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cccce4a4205b51ff587d222bc7a07ed4bfa86d8f","datavalue":{"value":{"entity-type":"item","numeric-id":103831,"id":"Q103831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3329201$D91F29C5-9CAD-48CB-9831-BCDDD5B16AFB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q3329201$1C104B26-B4CF-4791-87F0-C0823F570213","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"89c9066df1d6d26e10fa6b983ece08231f02bb82","datavalue":{"value":"https://semanticscholar.org/paper/d9512c3fa3c6abac1da23e73583e85187ccf3619","type":"string"},"datatype":"url"},"type":"statement","id":"Q3329201$421848C1-D4E1-4990-8D42-50A647D0475E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4b630bc7e56c97ad7658b9032403d768ebdbb64e","datavalue":{"value":"http://hdl.handle.net/11375/5486","type":"string"},"datatype":"url"},"type":"statement","id":"Q3329201$3F29CBDB-0B14-447A-892D-E4CDA4641631","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3329201$ECCDE100-3EE0-46C8-B5AC-96C413BA2980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3329201$D30C2E11-C6B7-4E4D-9137-E0B9651F596F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3329201$316FC6E5-240B-498E-8062-B1CDE843C22D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1ce31046f42695e43e96162990284acef4e31cc5","datavalue":{"value":"3860869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3329201$C85B0E56-7BF9-45BC-801F-13C5CA188BF4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbe4779b21482c6f7af163070358f952601735bf","datavalue":{"value":"precedence constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q3329201$6CAF376A-CB11-4040-B183-2B2DFE8412A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8ec9aaccfbefca3a6796892d946098699de2fa2","datavalue":{"value":"acyclic directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q3329201$0591BAD3-1BCE-401E-8A38-23C2CA1D533A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"81a979d6eab5539d70209d3b3be80ba3c2d4f9ad","datavalue":{"value":"feasible sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q3329201$C0AC237E-4433-4097-ACA2-02C4E6DA5AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f8e5f0281835e972ada95d61f0a0aee99ca65d0","datavalue":{"value":"partial order dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q3329201$00E53B4C-12D2-4B15-98CD-8168A5E74051","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":"Q3329201$0EDAB638-FBEA-414B-9CC5-A4B853568AD6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"be53739fb807f4f38d9f1ac7ecb3273919b3b7c0","datavalue":{"value":"W2083199589","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3329201$B722AC72-9F46-475A-88BB-FC7067CC0DA8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2369a639e0e57fe8c81e12eb581f7295e9727c45","datavalue":{"value":"10.1287/MOOR.9.2.248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3329201$80B33C9F-8639-41AE-97DC-5594AD79BE85","rank":"normal"}],"P1643":[{"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":"57c8d55d193fd3195af2a33e3235582d9d76ea5b","datavalue":{"value":{"amount":"+0.875373363494873","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":"Q3329201$0273FF59-BCD2-4607-83E9-595A9E44E872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"188124f3cafabe1fd815b5d8c5268fe51ffb25fa","datavalue":{"value":{"entity-type":"item","numeric-id":3396634,"id":"Q3396634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca42103f2f7c2abcf15ab6f0e42b93724fa24d40","datavalue":{"value":{"amount":"+0.8531055450439453","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":"Q3329201$B78DD387-2313-4516-A22E-B0212F4BC0DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce4f73e44a8498c4c7edbff4ba3a69bc17fc7e94","datavalue":{"value":{"entity-type":"item","numeric-id":3595374,"id":"Q3595374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"872c69a7b6165a0f81e3ed0fd6b0242d7b3c854c","datavalue":{"value":{"amount":"+0.818822979927063","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":"Q3329201$130C76CD-81D6-4789-94A6-F277FEE308E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f888f831e9df45ed31c7044a237f065581e10ac","datavalue":{"value":{"entity-type":"item","numeric-id":5429263,"id":"Q5429263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c74cdf12fe84691c0a67782bf3b0a71df6aff86","datavalue":{"value":{"amount":"+0.8167842626571655","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":"Q3329201$DC9D5533-7AB7-4ACE-972D-A3B0BCA9FDEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f923fe3e95630e49db583802e187460d90f89deb","datavalue":{"value":{"entity-type":"item","numeric-id":528859,"id":"Q528859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b02fd0e8617c523d5c67446ee92e6ccdcb00bc6b","datavalue":{"value":{"amount":"+0.8006224036216736","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":"Q3329201$272E93E4-E3D7-4F3A-A6ED-604D989AFBAF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9d022d94f4f92334fcec6c243034a7f1075206ae","datavalue":{"value":"The set V of n tasks has to be processed by one machine. The possible processing sequences are restricted by precedence constraints represented by a given acyclic directed graph \\(G=(V,A)\\). In any feasible sequence a task i may not be processed until the processing of all its predecessors has been finished. Each task \\(i\\in V\\) has a given processing time c(i) and a (nondecreasing in t) cost function g(i,t)\\(\\geq 0\\) where t is the termination time of processing i. The objective is to find a feasible sequence for which the total cost is minimal. When the partial order represented by the graph G has dimension \\(\\leq 2\\), a dynamic programming algorithm requiring O(Kn) time and O(K) space is presented, where K is the number of feasible subsets of the graph G. A subset \\(S\\subseteq V\\) is called feasible if for every \\(i\\in S\\) all the predecessors of i are also in S. The dimension of a partial order P is the minimum of total orders such that their intersection (as binary relations) is P. The algorithm uses the Baker-Schrage labeling scheme and the ''compactness'' property of the labels. It is proved that the labeling scheme has the compactness property iff the partial order dimension is less or equal to two.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3329201$54240BEB-D4D9-4288-8F76-0510992D3B8B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Single Machine Scheduling with Precedence Constraints of Dimension 2","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Single_Machine_Scheduling_with_Precedence_Constraints_of_Dimension_2"}}}}}