Bi-Variate Artificial Chromosomes with Genetic Algorithm for Single Machine Scheduling Problems with Sequence-Dependent Setup Times   [GA] [SMS] [SP]

by

Chen, S.-H. and Chen, M.-C.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: Proceedings of the 2011 IEEE Congress on Evolutionary Computation (Conference proceedings), 2011, p. 45-53
Keywords:Estimation of distribution algorithms, Genetic algorithms, Heuristics, metaheuristics, hyper-heuristics
Abstract:
Artificial chromosomes with genetic algorithm [GA] (ACGA) is one of the latest Estimation of Distribution Algorithms (EDAs). [DA] This algorithm has been used to solve different kinds of scheduling problems successfully. [SP] However, due to its probabilistic model [PM] does not consider the variable interactions, ACGA may not perform well in some scheduling problems, [SP] particularly the sequence-dependent setup times are considered because a former job influences the processing time of next job. It is not sufficient that probabilistic model just [PM] captures the ordinal information from parental distribution. As a result, this paper proposes a bi-variate probabilistic model added into [PM] the ACGA. The new algorithm is named extended artificial chromosomes with genetic algorithm [GA] (eACGA) and it is used to solve single machine scheduling problem [SMS] [SP] with sequence-dependent setup times in a common due-date environment. Some heuristics are also employed with eACGA. The results indicate that the average error ratio of eACGA is one-half of the ACGA. In addition, when eACGA works with other heuristics, the hybrid algorithm [HA] achieves the best solution quality when it is compared with other algorithms in literature. Thus, the proposed algorithms are effective for solving this scheduling problem [SP] with setup consideration.
Notes:
CEC2011 sponsored by the IEEE Computational Intelligence Society, and previously sponsored by the EPS and the IET.
Internet search:Search Google
Search Google Scholar
Search Citeseer using Google
Search Google for PDF
Search Google Scholar for PDF
Search Citeseer for PDF using Google

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{Chen:2011:BACwGAfSMSPwSST,
  title     = {Bi-Variate Artificial Chromosomes with Genetic Algorithm for Single Machine Scheduling Problems with Sequence-Dependent Setup Times},
  author    = {Shih-Hsin Chen and Min-Chih Chen},
  pages     = {45--53},
  booktitle = {Proceedings of the 2011 IEEE Congress on Evolutionary Computation},
  year      = {2011},
  editor = "Alice E. Smith",
  month     = {5-8 June},
  address   = {New Orleans, USA},
  organization ="IEEE Computational Intelligence Society",
  publisher = "IEEE Press",
  ISBN      = {0-7803-8515-2},
  keywords  = {Estimation of distribution algorithms, Genetic algorithms, Heuristics, metaheuristics and hyper-heuristics},
  abstract  = {
Artificial chromosomes with genetic algorithm (ACGA) is one of the latest
Estimation of Distribution Algorithms (EDAs). This algorithm has been used to
solve different kinds of scheduling problems successfully. However, due to its
probabilistic model does not consider the variable interactions, ACGA may not
perform well in some scheduling problems, particularly the sequence-dependent
setup times are considered because a former job influences the processing time
of next job. It is not sufficient that probabilistic model just captures the
ordinal information from parental distribution. As a result, this paper
proposes a bi-variate probabilistic model added into the ACGA. The new
algorithm is named extended artificial chromosomes with genetic algorithm
(eACGA) and it is used to solve single machine scheduling problem with
sequence-dependent setup times in a common due-date environment. Some
heuristics are also employed with eACGA. The results indicate that the average
error ratio of eACGA is one-half of the ACGA. In addition, when eACGA works
with other heuristics, the hybrid algorithm achieves the best solution quality
when it is compared with other algorithms in literature. Thus, the proposed
algorithms are effective for solving this scheduling problem with setup
consideration.
},
  notes =	{CEC2011 sponsored by the IEEE Computational Intelligence Society, and previously sponsored by the EPS and the IET. },
}