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...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/979238 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850237783656890368 |
|---|---|
| author | Tao Ren Chuan Zhang Lin Lin Meiting Guo Xionghang Xie |
| author_facet | Tao Ren Chuan Zhang Lin Lin Meiting Guo Xionghang Xie |
| author_sort | Tao Ren |
| collection | DOAJ |
| 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 | Article |
| id | doaj-art-13beceda454a4f8abf489949a8d413d0 |
| institution | OA Journals |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-13beceda454a4f8abf489949a8d413d02025-08-20T02:01:40ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/979238979238Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release DatesTao Ren0Chuan Zhang1Lin Lin2Meiting Guo3Xionghang Xie4Software College, Northeastern University, Shenyang 110819, ChinaSchool of Business Administration, Northeastern University, Shenyang 110819, ChinaSoftware College, Northeastern University, Shenyang 110819, ChinaSoftware College, Northeastern University, Shenyang 110819, ChinaSoftware College, Northeastern University, Shenyang 110819, ChinaWe 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.http://dx.doi.org/10.1155/2014/979238 |
| spellingShingle | Tao Ren Chuan Zhang Lin Lin Meiting Guo Xionghang Xie Asymptotic Analysis of SPTA-Based Algorithms for No-Wait Flow Shop Scheduling Problem with Release Dates The Scientific World Journal |
| 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 |
| url | http://dx.doi.org/10.1155/2014/979238 |
| work_keys_str_mv | AT taoren asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates AT chuanzhang asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates AT linlin asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates AT meitingguo asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates AT xionghangxie asymptoticanalysisofsptabasedalgorithmsfornowaitflowshopschedulingproblemwithreleasedates |