DocumentCode
2668950
Title
A time-indexed formulation of earliness tardiness scheduling via DC programming and DCA
Author
Thi, Hoai An Le ; Thuan, Nguyen Quang ; Tuong, Nguyen Huynh ; Dinh, Tao Pham
Author_Institution
Lab. of Theor. & Appl. Comput. Sci., Paul Verlaine Univ. - Metz, Metz, France
fYear
2009
fDate
12-14 Oct. 2009
Firstpage
779
Lastpage
784
Abstract
Time-index formulation for the earliness tardiness scheduling problem has received a great attention from many researchers because lower bound obtained by linear relaxation is rather good. Much work is devoted to tackle its upper bound. In this paper, we consider this formulation by additionally proposing a deadline for each job. We also propose an approach based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) to find upper bound efficiently for this problem. The results obtained are promising.
Keywords
algorithm theory; convex programming; relaxation theory; scheduling; DC programming; DCA programing; earliness tardiness scheduling; linear relaxation; time indexed formulation; upper bound efficiently; Computer science; Informatics; Information technology; Laboratories; Linear programming; Operations research; Processor scheduling; Single machine scheduling; Testing; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Science and Information Technology, 2009. IMCSIT '09. International Multiconference on
Conference_Location
Mragowo
Print_ISBN
978-1-4244-5314-6
Type
conf
DOI
10.1109/IMCSIT.2009.5352753
Filename
5352753
Link To Document