Share Email Print

Proceedings Paper

A best on-line algorithm for single machine scheduling the equal length jobs with the special chain precedence and delivery time
Author(s): Cunchang Gu; Yundong Mu
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

In this paper, we consider a single machine on-line scheduling problem with the special chains precedence and delivery time. All jobs arrive over time. The chains chainsi arrive at time ri , it is known that the processing and delivery time of each job on the chain satisfy one special condition CD a forehand: if the job J(i)j is the predecessor of the job J(i)k on the chain chaini, then they satisfy p(i)j = p(i)k = pqjqk , i = 1,2, ---,n , where pj and qj denote the processing time and the delivery time of the job Jj respectively. Obviously, if the arrival jobs have no chains precedence, it shows that the length of the corresponding chain is 1. The objective is to minimize the time by which all jobs have been delivered. We provide an on-line algorithm with a competitive ratio of √2 , and the result is the best possible.

Paper Details

Date Published: 4 March 2013
PDF: 6 pages
Proc. SPIE 8768, International Conference on Graphic and Image Processing (ICGIP 2012), 87684Z (4 March 2013); doi: 10.1117/12.2011862
Show Author Affiliations
Cunchang Gu, Henan Univ. of Technology (China)
Yundong Mu, Henan Univ. of Technology (China)

Published in SPIE Proceedings Vol. 8768:
International Conference on Graphic and Image Processing (ICGIP 2012)
Zeng Zhu, Editor(s)

© SPIE. Terms of Use
Back to Top