Hybrid Estimation of Distribution Algorithm for No-Wait Flow-Shop Scheduling Problem with Sequence-Dependent Setup Times
This paper proposes an innovative hybrid estimation of distribution algorithm (HEDA) for the no-wait flow-shop scheduling problem (NFSSP) with sequence dependent setup times (SDSTs) and release dates (RDs) to minimize the total completion time (TCT), whic
- PDF / 179,367 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 272 Views
Abstract. This paper proposes an innovative hybrid estimation of distribution algorithm (HEDA) for the no-wait flow-shop scheduling problem (NFSSP) with sequence dependent setup times (SDSTs) and release dates (RDs) to minimize the total completion time (TCT), which has been proved to be typically NP-hard combinatorial optimization problem with strong engineering background. Firstly, a speed-up evaluation method is developed according to the property of NFSSP with SDSTs and RDs. Secondly, the genetic information both order of jobs and the promising blocks of jobs are concerned to generate the guided probabilistic model. Thirdly, after the HEDA based global exploration, a problem dependent local search is developed to emphasize exploitation. Due to the reasonable balance between HEDA based global search and problemdependent local search as well as the comprehensive utilization of the speed-up evaluation, TCT-NFSSP with SDSTs and RDs can be solved effectively and efficiently. Computational results and comparisons demonstrate the superiority of HEDA in terms of searching quality, robustness, and efficiency. Keywords: Estimation of distribution algorithm scheduling problem Sequence-dependent setup times search Speed-up evaluation
No-wait flow-shop Release dates Local
1 Introduction Flow shop scheduling problems (FSSPs) have attracted much attention in the manufacturing systems of contemporary enterprises and wide research in both computer science and operation research fields. The no-wait flow shop problem (NFSSP) is a special case of FSSPs, in which there should be no waiting time between successive operations of jobs. That is, under the no-wait circumstances, each job is required to be processed continuously from start to end either on or between machines without any interruption. In addition, each machine can handle no more than one job at a time and each job has to visit each machine exactly once. In NFSSP, it is usually assuming the release time of all jobs is zero and the setup time on each machine is included in the job © Springer International Publishing Switzerland 2016 D.-S. Huang et al. (Eds.): ICIC 2016, Part I, LNCS 9771, pp. 505–516, 2016. DOI: 10.1007/978-3-319-42291-6_51
506
Z.-Q. Zhang et al.
processing time. However, the setup times are very important in some practical applications as noted in Allahverdi [1], which need to be explicitly treated and the release dates are usually nonzero. For the total completion time P criterion, the NFSSP with SDSTs and RDs is classified as Fm=no wait; STsd ; rj = Cj , which can also be identified as TCT-NFSSP with SDSTs and RDs. For the computational complexity of the NFSSP, Garey and Johnson proved that it was NP-hard. Because it turns P out that the P 1== P Cj is NP-hard and it also reduces to Fm=no wait, ST ; r = Cj (i.e., sd j P 1== Cj / Fm=no wait; ST ; r = C ), thus it can be undoubtedly concluded that sd j j P Fm=no wait; STsd ; rj = Cj is also NP-hard [2]. Bianco et al. [3] further indicated that the NFSSP with SDSTs and RDs was equivalent
Data Loading...
