A Novel Computational Model for Non-Linear Divisible Loads on a Linear Network

作者：Chen Chi Yeh^*; Chu Chih Ping

来源：IEEE Transactions on Computers, 2016, 65(1): 53-65.

DOI：10.1109/TC.2015.2419654

• Divisible load theory
• non-linear computational loads
• linear network
• load distribution
• multi-installment

This work investigates the problem of a non-linear divisible load distribution on a homogeneous linear network. A novel computational model of non-linear loads that includes complete steps for processing them, is proposed. This model solves the problem of the classical model, whose performance degrades by separating the load. This work also presents an algorithm S (Single-installment) that uses single-installment processing to distribute a non-linear divisible load on a homogeneous linear network. An algorithm M (Multi-installment) that applies multi-installment processing to reduce the initial distribution time for load is also proposed. Closed-form expressions for the parallel processing time and speed-up of the proposed algorithms are derived. The speed-up of algorithm S is much better than that of the classical algorithm that is based on the classical model. Algorithm M outperforms algorithm S in terms of speed-up when the load to be processed is very large or when the start-up costs are small.

• 出版日期2016-1