4 March 2013 A best on-line algorithm for single machine scheduling the equal length jobs with the special chain precedence and delivery time
Author Affiliations +
Proceedings Volume 8768, International Conference on Graphic and Image Processing (ICGIP 2012); 87684Z (2013) https://doi.org/10.1117/12.2011862
Event: 2012 International Conference on Graphic and Image Processing, 2012, Singapore, Singapore
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.
© (2013) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Cunchang Gu, Yundong Mu, "A best on-line algorithm for single machine scheduling the equal length jobs with the special chain precedence and delivery time", Proc. SPIE 8768, International Conference on Graphic and Image Processing (ICGIP 2012), 87684Z (4 March 2013); doi: 10.1117/12.2011862; https://doi.org/10.1117/12.2011862
PROCEEDINGS
6 PAGES


SHARE
RELATED CONTENT

Memory preservation made prestigious but easy
Proceedings of SPIE (January 25 2011)
Decryption-decompression of AES protected ZIP files on GPUs
Proceedings of SPIE (October 01 2011)
Dense OPC and verification for 45nm
Proceedings of SPIE (March 15 2006)

Back to Top