Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates

We address the scheduling problem for a no-wait flow shop to optimize total completion time with release dates. With the tool of asymptotic analysis, we prove that the objective values of two SPTA-based algorithms converge to the optimal value for sufficiently large-sized problems. To further enhanc...

Descripción completa

Detalles Bibliográficos
Autores principales: Ren, Tao, Zhang, Chuan, Lin, Lin, Guo, Meiting, Xie, Xionghang
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Hindawi Publishing Corporation 2014
Materias:
Research Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3934092/
https://www.ncbi.nlm.nih.gov/pubmed/24764774
http://dx.doi.org/10.1155/2014/979238
_version_ 1782305032850374656
author Ren, Tao
Zhang, Chuan
Lin, Lin
Guo, Meiting
Xie, Xionghang
author_facet Ren, Tao
Zhang, Chuan
Lin, Lin
Guo, Meiting
Xie, Xionghang
author_sort Ren, Tao
collection PubMed
description We address the scheduling problem for a no-wait flow shop to optimize total completion time with release dates. With the tool of asymptotic analysis, we prove that the objective values of two SPTA-based algorithms converge to the optimal value for sufficiently large-sized problems. To further enhance the performance of the SPTA-based algorithms, an improvement scheme based on local search is provided for moderate scale problems. New lower bound is presented for evaluating the asymptotic optimality of the algorithms. Numerical simulations demonstrate the effectiveness of the proposed algorithms.
format Online
Article
Text
id pubmed-3934092
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher Hindawi Publishing Corporation
record_format MEDLINE/PubMed
spelling pubmed-39340922014-04-24 Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates Ren, Tao Zhang, Chuan Lin, Lin Guo, Meiting Xie, Xionghang ScientificWorldJournal Research Article We address the scheduling problem for a no-wait flow shop to optimize total completion time with release dates. With the tool of asymptotic analysis, we prove that the objective values of two SPTA-based algorithms converge to the optimal value for sufficiently large-sized problems. To further enhance the performance of the SPTA-based algorithms, an improvement scheme based on local search is provided for moderate scale problems. New lower bound is presented for evaluating the asymptotic optimality of the algorithms. Numerical simulations demonstrate the effectiveness of the proposed algorithms. Hindawi Publishing Corporation 2014-02-09 /pmc/articles/PMC3934092/ /pubmed/24764774 http://dx.doi.org/10.1155/2014/979238 Text en Copyright © 2014 Tao Ren et al. https://creativecommons.org/licenses/by/3.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research Article
Ren, Tao
Zhang, Chuan
Lin, Lin
Guo, Meiting
Xie, Xionghang
Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates
title Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates
title_full Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates
title_fullStr Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates
title_full_unstemmed Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates
title_short Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates
title_sort asymptotic analysis of spta-based algorithms for no-wait flow shop scheduling problem with release dates
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3934092/
https://www.ncbi.nlm.nih.gov/pubmed/24764774
http://dx.doi.org/10.1155/2014/979238
work_keys_str_mv AT rentao asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates
AT zhangchuan asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates
AT linlin asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates
AT guomeiting asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates
AT xiexionghang asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates

Ejemplares similares