A best on-line algorithm for single machine scheduling the equal length jobs with the special chain precedence and delivery time

Cunchang Gu; Yundong Mu

doi:10.1117/12.2011862

4 March 2013 A best on-line algorithm for single machine scheduling the equal length jobs with the special chain precedence and delivery time

Cunchang Gu, Yundong Mu

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 chainsⁱ arrive at time rⁱ , 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⁽ⁱ⁾_j is the predecessor of the job J⁽ⁱ⁾_k on the chain chain_i, then they satisfy p⁽ⁱ⁾_j = p⁽ⁱ⁾_k = p ≥ q_j ≥ q_k , i = 1,2, ---,n , where p_j and q_j denote the processing time and the delivery time of the job J_j 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.

Citation Download Citation

Cunchang Gu and 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); https://doi.org/10.1117/12.2011862

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available