{"entities":{"Q633540":{"pageid":635388,"ns":120,"title":"Item:Q633540","lastrevid":51219947,"modified":"2026-01-17T07:34:51Z","type":"item","id":"Q633540","labels":{"en":{"language":"en","value":"A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5873379"}},"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":"Q633540$C8CB242B-9662-44B6-AE2D-874AC3419249","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10526101b7fc3928217d1530b70363ac911ef5b9","datavalue":{"value":{"text":"A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q633540$B7846431-6967-4E4C-80E6-33204BE13B7D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"352fedaf3ba1a3efd7305508c77ffd8bb61d17d3","datavalue":{"value":"1213.90125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q633540$9E1519F7-1599-49C6-97CB-C006318C61D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbf181820d677929ee577ca4f23e91cd6c25003c","datavalue":{"value":{"entity-type":"item","numeric-id":337139,"id":"Q337139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$0D0B9940-CE5B-4A4E-95D7-CBDC8674BC18","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39245fc27c04eb23fa7211454c51f34f7f46a9a0","datavalue":{"value":{"entity-type":"item","numeric-id":177699,"id":"Q177699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$F794C14C-6239-4E12-9976-50E17D477C06","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"362da250e53eddf9b6ee15ba6fcae9e11b48d936","datavalue":{"value":{"time":"+2011-04-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q633540$88B3583D-C746-482B-88B7-1252B8CB46F2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ccccf5aa045e5a9ab0517167965db0883365ace6","datavalue":{"value":"In this paper cyclic scheduling problems without resource constraints are studied. Given is a set of tasks \\(i=1,\\ldots,n\\) with processing times \\(p_i>0\\) which have to be processed infinitely often. The tasks are restricted by so-called uniform precedence relations \\((i,j)\\) with two integer parameters: a value \\(V_{ij}\\) and a height \\(H_{ij}\\). Respecting these relations means that \\(t(i,k)+V_{ij} \\leq t(j,k+H_{ij})\\) must hold for all \\(k\\), where \\(t(i,k)\\) denotes the starting time of the \\(k\\)-th execution of task \\(i\\).  After introducing the problem a necessary condition for the existence of a periodic schedule is given, which is not sufficient in general. Afterwards, the earliest start schedule is studied in more detail. It is shown that the minimum average cycle time is equal for the earliest start schedule and an optimal periodic schedule. Finally, an algorithm based on linear programming is presented which checks the existence of a schedule and computes the minimum average cycle time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q633540$7E0975DF-3198-407B-8D5B-EE4C07A8B1A3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e47c7ebb56a1f0496381a9a28be5aa2e34301ed2","datavalue":{"value":{"entity-type":"item","numeric-id":210525,"id":"Q210525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$79A96CEC-50FC-4280-9031-BB1DF6802FE9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q633540$95448067-9F15-451E-81A0-7CCCA6A7749B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3c3f975479d2768e4d8a80e366e9286a2219d85","datavalue":{"value":"5873379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q633540$924340F6-3C87-463D-9DD5-E06DCC5DA708","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b3ab8b8d08fb14c4089591941fcf81a081955a2","datavalue":{"value":"cyclic schedule","type":"string"},"datatype":"string"},"type":"statement","id":"Q633540$014BC1DA-BF12-4314-AECE-4B18B0308BF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09fa440f76bafd50a98244e1969f1a1f23259e19","datavalue":{"value":"earliest start schedule","type":"string"},"datatype":"string"},"type":"statement","id":"Q633540$A3C1352E-C572-459A-84CF-FF6BBF1141AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9cfd51d89d2882ea7938615fe0882659647e77ca","datavalue":{"value":"periodic schedule","type":"string"},"datatype":"string"},"type":"statement","id":"Q633540$80228B1A-3954-4771-A89D-1816A174C534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff0a4ef70f0610175bbefab335ba60727a1ef8a8","datavalue":{"value":"minimum average cycle time","type":"string"},"datatype":"string"},"type":"statement","id":"Q633540$27EAD82D-2F5C-4BA6-B14D-9AAF1CCE362E","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":"Q633540$6036DDA7-11B5-44B9-9397-A60EE12A4BD2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f25185c5024296b30faa2ade713fbea2c40b39ff","datavalue":{"value":"https://doi.org/10.1007/s10951-009-0159-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q633540$BF600B9E-4DDF-4C72-8952-A6389B422D5B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"44fe2aa0cdbc8e57cafe1c87fe913c347e14e16e","datavalue":{"value":"W2082269164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q633540$00C1FE56-8395-489F-87F3-208C6C3DDFDB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"345ebc65a5563d8683f859e18774661234fd51e4","datavalue":{"value":{"entity-type":"item","numeric-id":1341993,"id":"Q1341993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$C750A558-90F1-4CFF-BF22-01FCED9D3ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f091a2487faa4320a607c7fc5ddd1d40ffc78957","datavalue":{"value":{"entity-type":"item","numeric-id":5615282,"id":"Q5615282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$B699FD62-C283-4AB8-B3FB-CE0D30E65573","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeda763b1dfed1cfc8cfac7f73cba2b5da4b070e","datavalue":{"value":{"entity-type":"item","numeric-id":1887774,"id":"Q1887774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$3898DC40-0AC3-4C09-9CC2-CF6178A6DB4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d7feed83d4384b3a117567e36669d366e97440c","datavalue":{"value":{"entity-type":"item","numeric-id":3219770,"id":"Q3219770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$98A0B910-F1FB-48AC-917C-6F02216DF0A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$F28FAC78-13BD-45A8-A7E3-7C791DC573C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30633397d8df4bf9c403d00eac89b6675ca2a377","datavalue":{"value":{"entity-type":"item","numeric-id":1296576,"id":"Q1296576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$9C60F348-7DED-477D-8086-4299A5584A75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44dab1a51a1058e733254dbf41adc07b19383603","datavalue":{"value":{"entity-type":"item","numeric-id":1607980,"id":"Q1607980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$B2D6409F-9803-4BB2-8F6F-C24DB341543F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a18492a2c94c7f1f7f4004cdb2b8afb36ddb277","datavalue":{"value":{"entity-type":"item","numeric-id":1346694,"id":"Q1346694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$07B881C1-E7D5-4D93-94FE-B824356411BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8c9c5c7e642b8a633e436b1cd37369bed1a0fba","datavalue":{"value":{"entity-type":"item","numeric-id":3804437,"id":"Q3804437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$0D65DC35-BAFB-4320-9974-43CAEB2ED365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"139a173cc24e6a2efb63c97753d1922af84629f3","datavalue":{"value":{"entity-type":"item","numeric-id":1310046,"id":"Q1310046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$A01860C2-C304-4681-9458-F8FD381080A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ee473aa563c961c179e3c16c7419b241b2d89dd","datavalue":{"value":{"entity-type":"item","numeric-id":1270778,"id":"Q1270778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$7DA23B27-F66B-445A-951D-ACB02BF08AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6dec3d94a289dd3ad8ae85a7487dbf87bd06eee","datavalue":{"value":{"entity-type":"item","numeric-id":1341404,"id":"Q1341404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$73F74EBD-7426-4B7B-8977-EF45DE71296D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa3956c66780f01e8850b8c9864275b3e3b14442","datavalue":{"value":{"entity-type":"item","numeric-id":1600002,"id":"Q1600002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q633540$9D6BC63B-D3C0-47F7-A232-8F43A695E7F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"386c8382dc5ffeff37896af77d767a21ad5fe9b3","datavalue":{"value":"10.1007/S10951-009-0159-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q633540$E038F351-8027-4E4F-A9A1-79DDBE0BDB3C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcf3278c3996e2ff39876dbaf42cbf845b3c6b32","datavalue":{"value":{"entity-type":"item","numeric-id":1003670,"id":"Q1003670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3026d3b27f1992d68b0f3dccd0af2428d01b7576","datavalue":{"value":{"amount":"+0.8568422198295593","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":"Q633540$FD19463F-D2CE-44D7-8358-987F78D1C62E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa417d16108206128fc0d115f48458fa274e7e53","datavalue":{"value":{"entity-type":"item","numeric-id":1346694,"id":"Q1346694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15f1b484e7599db9a316fcfe7ae9402cb1edd090","datavalue":{"value":{"amount":"+0.8464727401733398","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":"Q633540$DC319C67-4B10-418B-9C09-AFDE1925FB42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78e43c876424cbe5d50dd18962667b7e4d1a5ada","datavalue":{"value":{"entity-type":"item","numeric-id":1917250,"id":"Q1917250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0e099df983ca6b61fbbf273f6bbc3e425bb35a7","datavalue":{"value":{"amount":"+0.8395200371742249","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":"Q633540$E8AE5E7B-620E-4472-A054-0E0A046A6636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c346691b43688839d9fd04e757f0bb10a1faba27","datavalue":{"value":{"entity-type":"item","numeric-id":1293196,"id":"Q1293196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f28d6bfbc039e922581674423017a68f2706bc4","datavalue":{"value":{"amount":"+0.8395199775695801","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":"Q633540$437C2D48-50E2-462D-9358-756A265B0954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b973a074b0b901d00f9a11a1086a4312c6d41a32","datavalue":{"value":{"entity-type":"item","numeric-id":4553436,"id":"Q4553436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78bb0ba89eed913ee4056fc3acaf899aaa7fa910","datavalue":{"value":{"amount":"+0.8310005068778992","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":"Q633540$0724498B-A3EF-496D-9CFD-E379F08F9ABB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:633540","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:633540"}}}}}