Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2002, Vol. 3 Issue (1): 60-64    DOI: 10.1631/jzus.2002.0060
Computer & Industrial Engineering     
Algorithms for semi on-line multiprocessor scheduling problems
HE Yong, YANG Qi-fan, TAN Zhi-yi, YAO En-yu
Department of Mathematics, Zhejiang University, Hangzhou 310027, China; Department of System Science & Engeering, Zhejiang University, Hangzhou 310027, China
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

Abstract  In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off-line or on-line environment. But in practice, problems are often not really off-line or on-line but somehow in between. This means that, with respect to the on-line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on-line ones. The authors studied two semi on-line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.

Key words： analysis of algorithm      on-line scheduling      worst-case ratio     
Received: 18 December 2000     
CLC:  TP393  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
HE Yong
YANG Qi-fan
TAN Zhi-yi
YAO En-yu
Cite this article:

HE Yong, YANG Qi-fan, TAN Zhi-yi, YAO En-yu. Algorithms for semi on-line multiprocessor scheduling problems. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2002, 3(1): 60-64.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2002.0060     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2002/V3/I1/60

[1] Xiao-fan Wu, Chun Chen, Jia-jun Bu, Gang Chen. Sensor network architecture for intelligent high-speed train on-board monitoring[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2011, 12(12): 921-925.
[2] Pablo García Ansola, Andrés García, Javier de las Morenas, Javier García Escribano, Francisco Javier Otamendi. ZigID: Improving visibility in industrial environments by combining WSN and RFID[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2011, 12(11): 849-859.
[3] Mucheol KIM, Sunhong KIM, Hyungjin BYUN, Sangyong HAN. Optimized algorithm for balancing clusters in wireless sensor networks[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(10): 1404-1412.
[4] Yin ZHANG, Jiang-qin WU, Yue-ting ZHUANG. Random walk models for top-N recommendation task[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(7): 927-936.
[5] Fan-rui KONG, Chun-wen LI, Qing-qing DING, Guang-zhao CUI, Bing-yi CUI. WAPN: a distributed wormhole attack detection approach for wireless sensor networks[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(2): 279-289.
[6] Xin-yu WANG, Xiao-hu YANG, Jian-ling SUN, Wei LI, Wei SHI, Shan-ping LI. An effective connected dominating set based mobility management algorithm in MANETs[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(10): 1318-1325.
[7] Zhe-jing BAO, Yi-jia CAO. Cascading failures in local-world evolving networks[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(10): 1336-1340.
[8] Jian WANG, Yan-heng LIU, Jian-qi ZHU, Yu JIAO. Model for cascading failures in congested Internet[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(10): 1331-1335.
[9] Tamara PAZYNYUK, Jian-zhong LI, George S. OREKU. Improved Feistel-based ciphers for wireless sensor network security[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(8): 1111-1117.
[10] R. VIDHYAPRIYA, P. T. VANATHI. Reliable energy-efficient routing with novel route update in wireless sensor networks[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(8): 1099-1110.
[11] Li ZHU, Zhi-shu LI, Liang-yin CHEN, Yan-hong CHENG. Two-stage evolutionary algorithm for dynamic multicast routing in mesh network[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(6): 791-798.
[12] Yao-feng WEN, Yu-quan CHEN, Min PAN. Adaptive ant-based routing in wireless sensor networks using Energy*Delay metrics[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(4): 531-538.
[13] Yi-xiao LI, Xiao-gang JIN, Fan-sheng KONG, Hui-lan LUO. Strategic games on a hierarchical network model[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(2): 271-278.
[14] HUANG Wen-liang, LI Shi-jian, LIU Duo. Designing reduced beacon trajectory for sensor localization[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(12): 1971-1982.
[15] GUO Tong-qiang, WENG Jian-guang, ZHUANG Yue-ting. Content subscribing mechanism in P2P streaming based on gamma distribution prediction[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(12): 1983-1989.