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
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;
Conference_Titel :
Computer Science and Information Technology, 2009. IMCSIT '09. International Multiconference on
Conference_Location :
Mragowo
Print_ISBN :
978-1-4244-5314-6
DOI :
10.1109/IMCSIT.2009.5352753
