Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2005, Vol. 6 Issue (1): 20-26    DOI: 10.1631/jzus.2005.A0020
Computer & Information Science     
Deterministic and randomized scheduling problems under the lp norm on two identical machines
LIN Ling, TAN Zhi-yi, HE Yong
Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, China
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

Abstract  Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online 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-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.

Key words： Semi-online      Scheduling      Randomization      Competitive ratio     
Received: 10 February 2004     
CLC:  TP393  
  O223  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
LIN Ling
HE Yong
TAN Zhi-yi
Cite this article:

LIN Ling, TAN Zhi-yi, HE Yong. Deterministic and randomized scheduling problems under the lp norm on two identical machines. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2005, 6(1): 20-26.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2005.A0020     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2005/V6/I1/20

[1] Yi-cong Gao, Yi-xiong Feng, Jian-rong Tan. Multi-principle preventive maintenance: a design-oriented scheduling study for mechanical systems[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2014, 15(11): 862-872.
[2] José Luís Ponz-Tienda, Eugenio Pellicer, Víctor Yepes. Complete fuzzy scheduling and fuzzy earned value management in construction projects[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2012, 13(1): 56-68.
[3] Hai-en Fang, Jie Zhang, Jin-liang Gao. Optimal operation of multi-storage tank multi-source system based on storage policy[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2010, 11(8): 571-579.
[4] Yu-dong Xue, Takashi Irohara. A time-space network based international transportation scheduling problem incorporating CO2 emission levels[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2010, 11(12): 927-932.
[5] Yu-chuan Liu, Shih-ming Yang, Yu-te Lin. Fuzzy finish time modeling for project scheduling[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2010, 11(12): 946-952.
[6] Azuma Okamoto, Mitsumasa Sugawara. Solving composite scheduling problems using the hybrid genetic algorithm[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2010, 11(12): 953-958.
[7] Shervin VAKILI, Sied Mehdi FAKHRAIE, Siamak MOHAMMADI, Ali AHMADI. Low-cost fault tolerance in evolvable multiprocessor systems: a graceful degradation approach[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(6): 922-926.
[8] Zhi-gang GAO, Zhao-hui WU. Schedulability analysis for linear transactions under fixed priority hybrid scheduling[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(6): 776-785.
[9] Feng SHE, Han-wen LUO, Lei CHEN, Hua XIA. Power duality for multi-antenna OFDM system in broadcast channel with user scheduling[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(2): 215-224.
[10] Ehsan Ullah MUNIR, Jian-zhong LI, Sheng-fei SHI, Zhao-nian ZOU, Qaisar RASOOL. A new heuristic for task scheduling in heterogeneous computing environment[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(12): 1715-1723.
[11] WANG Ji-min, PAN Xue-zeng, WANG Jie-bing, SUN Kang. Fast combination of scheduling chains under resource and time constraints[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(1 ): 17-.
[12] HAN Shu-guang, JIANG Yi-wei, HU Jue-liang. Online algorithms for scheduling with machine activation cost on two uniform machines[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(1 ): 18-.
[13] Ji Xin, Pollin Sofie, Lenoir Gregory, Lafruit Gauthier, Dejonghe Antoine, Catthoor Francky. Multi-user Motion JPEG2000 over wireless LAN: Run-time performance-energy optimization with application-aware cross-layer scheduling[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(Supplement 1): 151-158.
[14] Tu Wei, Chakareski Jacob, Steinbach Eckehard. Rate-distortion optimized frame dropping and scheduling for multi-user conversational and streaming video[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(5): 864-872.
[15] Cheng Ming-bao, Sun Shi-jie. The single-machine scheduling problems with deteriorating jobs and learning effect[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(4 ): 18-.