2026-09-20T01:05:03.598810800Zhttps://opus.uleth.ca/server/oai/request
oai:opus.uleth.ca:10133/47792017-02-21T21:07:14Zcom_10133_3346com_10133_1com_10133_296col_10133_3347col_10133_298
ULethbridge OPUS Repository supervisor Benkoczi, Robert author Nabi, Mahmudun author University of Lethbridge. Faculty of Arts and Science 2017-02-17T17:52:38Z 2017-02-17T17:52:38Z 2016 https://hdl.handle.net/10133/4779 In this thesis, we study the task scheduling problem in vehicular clouds. It falls in the category of unrelated parallel machine scheduling problems. Resource assignment in vehicular clouds must deal with the transient nature of the cloud resources and a relaxed definition of non-preemptive tasks. Despite a rich literature in machine scheduling and grid computing, the resource assignment problem in vehicular clouds has not been examined yet. We show that even the problem of finding a minimum cost schedule for a single task over unrelated machines is NP-hard. We then provide a fully polynomial time approximation scheme and a greedy approximation for scheduling a single task. We extend these algorithms to the case of scheduling n tasks. We validate our algorithms through extensive simulations that use synthetically generated data as well as real data extracted from vehicle mobility and grid computing workload traces. Our contributions are, to the best of our knowledge, the first quantitative analysis of the computational power of vehicular clouds. en_US availability constraint non-preemption smart vehicles task scheduling problems vehicular resource utilization Resource assignment algorithms for vehicular clouds Thesis PGI+VW5pdmVyc2l0eSBvZiBMZXRoYnJpZGdlIHwgTm9uLUV4Y2x1c2l2ZSBUaGVzaXMgTGljZW5zZSBBZ3JlZW1lbnQ8L2I+DQo8cD5JbiBjb25zaWRlcmF0aW9uIG9mIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgYWdyZWVpbmcgdG8gbWFrZSB5b3VyIHRoZXNpcy9kaXNzZXJ0YXRpb24gKHRoZSAiVGhlc2lzIikgYXZhaWxhYmxlIHRvIGludGVyZXN0ZWQgcGVyc29ucywgeW91IGFncmVlIGFzIGZvbGxvd3M6IDwvcD4NCjxvbD4NCjxsaT5Zb3UgaGVyZWJ5IGdyYW50IHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgYSBub24tZXhjbHVzaXZlLCB3b3JsZHdpZGUsIGlycmV2b2NhYmxlLCByb3lhbHR5LWZyZWUgbGljZW5zZSB0byBhcmNoaXZlLCBwcmVzZXJ2ZSwgcHJvZHVjZSwgcmVwcm9kdWNlLCBwdWJsaXNoLCBjb21tdW5pY2F0ZSwgY29udmVydCBpbnRvIGFueSBmb3JtYXQsIGNvbW11bmljYXRlIGFuZCBkaXN0cmlidXRlIHRoZSBUaGVzaXMsIGluY2x1ZGluZyB0aGUgVGhlc2lzIGFic3RyYWN0LCBpbiBhbnkgZm9ybWF0IGFuZCBpbiBhbnkgbWVkaXVtIGZvciBub24tY29tbWVyY2lhbCBwdXJwb3NlcyBmb3IgdGhlIGZ1bGwgdGVybSBvZiB0aGUgY29weXJpZ2h0LCBpbmNsdWRpbmcgYnV0IG5vdCBsaW1pdGVkIHRvIHRoZSByaWdodCB0bzoNCjxvbCB0eXBlPSJhIj48bGk+bWFrZSB0aGUgVGhlc2lzIGF2YWlsYWJsZSBpbiBwcmludCBvciBvbmxpbmUgYnkgdGVsZWNvbW11bmljYXRpb24gdG8gdGhlIHB1YmxpYywgaW5jbHVkaW5nIHZpYSB0aGUgaW50ZXJuZXQgYW5kIGZhY3NpbWlsZSB0cmFuc21pc3Npb24sIGZvciBub24tY29tbWVyY2lhbCBwdXJwb3Nlczs8L2xpPg0KPGxpPmRpc3RyaWJ1dGUgdGhlIFRoZXNpcyB0aHJvdWdoIHRoZSBsaWJyYXJ5LCBpbnRlcmxpYnJhcnkgYW5kIHB1YmxpYyBsb2FuOzwvbGk+DQo8bGk+ZGlnaXRpemUsIHBob3RvY29weSBhbmQgbWljcm9maWNoZSB0aGUgVGhlc2lzOyBhbmQgPC9saT4NCjxsaT5zdWItbGljZW5jZSB0byBMaWJyYXJ5IGFuZCBBcmNoaXZlcyBDYW5hZGEgYW55IG9mIHRoZSBhY3Rpb25zIG1lbnRpb25lZCBhYm92ZS4gPC9saT48L29sPjwvbGk+DQo8bGk+WW91IGNvbmZpcm0gdGhlIGZvbGxvd2luZyBzdGF0ZW1lbnRzIHRvIGJlIHRydWUgYW5kIGFjY3VyYXRlOg0KPG9sIHR5cGU9ImEiPjxsaT55b3UgaGF2ZSB0aGUgcmlnaHQgYW5kIGF1dGhvcml0eSB0byBncmFudCB0aGUgcmlnaHRzIHNldCBvdXQgaW4gdGhpcyBsaWNlbnNlOyA8L2xpPg0KPGxpPnRoZSBUaGVzaXMgaXMgeW91ciBvcmlnaW5hbCB3b3JrIGFuZCBpcyBhbiB1bi1hbWVuZGVkIGNvcHkgb2YgdGhlIGZpbmFsIHZlcnNpb24gYXBwcm92ZWQgYnkgdGhlIERlYW4gb2YgdGhlIFNjaG9vbCBvZiBHcmFkdWF0ZSBTdHVkaWVzOyA8L2xpPg0KPGxpPnRoZSBUaGVzaXMgZG9lcyBub3QgaW5mcmluZ2UgdGhlIGNvcHlyaWdodCBvciBpbnRlbGxlY3R1YWwgcHJvcGVydHkgcmlnaHRzIG9mIGFueSBvdGhlciBwZXJzb247IDwvbGk+DQo8bGk+aWYgdGhlIFRoZXNpcyBjb250YWlucyBtYXRlcmlhbCBmb3Igd2hpY2gsIHVuZGVyIHRoZSB0ZXJtcyBvZiB0aGUgQ29weXJpZ2h0IEFjdCwgd3JpdHRlbiBwZXJtaXNzaW9uIG9mIHRoZSBjb3B5cmlnaHQgb3duZXIocykgaXMgcmVxdWlyZWQgdG8gaW5jbHVkZSB0aGUgd29yayAob3IgcGFydCB0aGVyZW9mLCBhcyB0aGUgY2FzZSBtYXkgYmUpIGluIHRoZSBUaGVzaXMsIHRoZW4gYm90aCBvZiB0aGUgZm9sbG93aW5nIGFwcGx5Og0KPG9sIHR5cGU9ImkiPjxsaT50aGUgbWF0ZXJpYWwgaGFzIGJlZW4gY2xlYXJseSBhbmQgYXBwcm9wcmlhdGVseSBpZGVudGlmaWVkIGFuZCBhY2tub3dsZWRnZWQ7IGFuZCA8L2xpPg0KPGxpPnlvdSBoYXZlIG9idGFpbmVkIHdyaXR0ZW4gcGVybWlzc2lvbiBvZiB0aGUgY29weXJpZ2h0IG93bmVyKHMpLCBmb3IgdGhlIGZ1bGwgdGVybSBvZiBjb3B5cmlnaHQgcHJvdGVjdGlvbiwgdG8gaW5jbHVkZSB0aGUgd29yayAob3IgcGFydCB0aGVyZW9mLCBhcyB0aGUgY2FzZSBtYXkgYmUpIGluIHRoZSBUaGVzaXMgYW5kIHRvIGdyYW50IHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgdGhlIHJpZ2h0cyBzZXQgb3V0IGluIHRoaXMgbGljZW5zZTsgPC9saT48L29sPiA8L2xpPg0KPGxpPiB0aGUgVGhlc2lzIGRvZXMgbm90IGNvbnRhaW4gYW55IGNvbmZpZGVudGlhbCBvciBwcm9wcmlldGFyeSBpbmZvcm1hdGlvbiBiZWxvbmdpbmcgdG8gb3RoZXJzLCBvdGhlciB0aGFuIGluZm9ybWF0aW9uIGluY2x1ZGVkIHVuZGVyIFNlY3Rpb24gMiBkKSBhYm92ZTsgPC9saT4NCjxsaT50aGUgVGhlc2lzIGRvZXMgbm90IGNvbnRhaW4gYW55IGxpYmVsb3VzIG9yIG90aGVyIHVubGF3ZnVsIG1hdHRlciBhbmQgZG9lcyBub3QgaW52YWRlIHRoZSBwcml2YWN5IG9mIGFueSBwZXJzb25zOyBhbmQgPC9saT4NCjxsaT50aGVyZSBhcmUgbm8gdW5leHBpcmVkIHB1YmxpY2F0aW9uIGRlbGF5cyBvbiB0aGUgZGlzdHJpYnV0aW9uIG9mIHRoZSBUaGVzaXMuIDwvbGk+PC9vbD4gPC9saT4NCjxsaT5Zb3UgYXJlIGF3YXJlIHRoYXQgeW91IHJldGFpbiB5b3VyIGNvcHlyaWdodCBvd25lcnNoaXAgYW5kIG1vcmFsIHJpZ2h0cyBpbiB0aGUgVGhlc2lzIGFuZCBtYXkgZGVhbCB3aXRoIHRoZSBUaGVzaXMgaW4gYW55IHdheSBjb25zaXN0ZW50IHdpdGggdGhlIHJpZ2h0cyBncmFudGVkIHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgaW4gdGhpcyBsaWNlbnNlLiBZb3UgdW5kZXJ0YWtlIHRvIHN1Ym1pdCB5b3VyIFRoZXNpcywgaW5jbHVkaW5nIHRoZSBUaGVzaXMgYWJzdHJhY3QsIHRocm91Z2ggdGhlIFVuaXZlcnNpdHkgb2YgTGV0aGJyaWRnZSB0byBMaWJyYXJ5IGFuZCBBcmNoaXZlcyBDYW5hZGEuIFlvdSBwcm9taXNlIHRvIGluZm9ybSBhbnkgcGVyc29uIHRvIHdob20geW91IG1heSBoZXJlYWZ0ZXIgYXNzaWduIG9yIGxpY2Vuc2UgeW91ciBjb3B5cmlnaHQgaW4geW91ciBUaGVzaXMgb2YgdGhlIHJpZ2h0cyBncmFudGVkIHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWdyZWUgdGhhdCB0aGUgVW5pdmVyc2l0eSBvZiBMZXRoYnJpZGdlIGlzIG5vdCByZXNwb25zaWJsZSBmb3IgYW55IG1pc3VzZSBvZiB0aGUgVGhlc2lzIGJ5IHRoaXJkIHBhcnRpZXMgd2hvIGFjY2VzcyB0aGUgVGhlc2lzIHRocm91Z2ggdGhlIFVuaXZlcnNpdHkgb2YgTGV0aGJyaWRnZeKAmXMgZmFjaWxpdGllcy48L2xpPjwvb2w+ URL http://localhost:4000/bitstreams/8aea0c8d-8421-4b4c-9691-b9b805e57c4f/download File MD5 9dcdd54b53221ba06439cbc568f66a3a 896202 application/pdf NABI_MAHMUDUN_MSC_2016.pdf URL http://localhost:4000/bitstreams/31550d18-e8f1-4977-8aa0-177a1f1fc3e0/download File MD5 831c0fcc2f8c540db41afd6d4c8c02f8 133197 text/plain NABI_MAHMUDUN_MSC_2016.pdf.txt