New Efficient Lower Bound for the Hybrid Flow Shop Scheduling Problem With Multiprocessor Tasks
In this paper, we address the hybrid flow shop scheduling problem with multiprocessor tasks. The objective is to minimize the maximum completion time. This problem is encountered in manufacturing, parallel and distributed computing, and real-time machine vision systems. This problem is strongly NP-h...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2017-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/7907262/ |
| _version_ | 1828963033979813888 |
|---|---|
| author | Lotfi Hidri Anis Gharbi |
| author_facet | Lotfi Hidri Anis Gharbi |
| author_sort | Lotfi Hidri |
| collection | DOAJ |
| description | In this paper, we address the hybrid flow shop scheduling problem with multiprocessor tasks. The objective is to minimize the maximum completion time. This problem is encountered in manufacturing, parallel and distributed computing, and real-time machine vision systems. This problem is strongly NP-hard, and consequently, several heuristics and meta heuristics were proposed in the literature in order to provide a near optimal solution. Assessing the performance of these heuristics requires efficient lower bounds. Surprisingly, few lower bounds with moderate performance were proposed. Because of this reason, we propose in this paper a new efficient destructive lower bound. This lower bound is based on the concept of revisited energetic reasoning, which is basically a feasible test with window time adjustments. The efficiency of the proposed lower bound is assessed throughout an extensive computational experiments conducted on a benchmark of 2,100 instances with up to ten centers. The numerical results provide evidence that the proposed lower bound consistently improves the best existing ones. |
| first_indexed | 2024-12-14T10:17:17Z |
| format | Article |
| id | doaj.art-580bbf68cfab4ebe95c9bd82c1534bca |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-14T10:17:17Z |
| publishDate | 2017-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-580bbf68cfab4ebe95c9bd82c1534bca2022-12-21T23:06:44ZengIEEEIEEE Access2169-35362017-01-0156121613310.1109/ACCESS.2017.26961187907262New Efficient Lower Bound for the Hybrid Flow Shop Scheduling Problem With Multiprocessor TasksLotfi Hidri0https://orcid.org/0000-0001-6868-7353Anis Gharbi1Industrial Engineering Department, King Saud University, Riyadh, Saudi ArabiaIndustrial Engineering Department, King Saud University, Riyadh, Saudi ArabiaIn this paper, we address the hybrid flow shop scheduling problem with multiprocessor tasks. The objective is to minimize the maximum completion time. This problem is encountered in manufacturing, parallel and distributed computing, and real-time machine vision systems. This problem is strongly NP-hard, and consequently, several heuristics and meta heuristics were proposed in the literature in order to provide a near optimal solution. Assessing the performance of these heuristics requires efficient lower bounds. Surprisingly, few lower bounds with moderate performance were proposed. Because of this reason, we propose in this paper a new efficient destructive lower bound. This lower bound is based on the concept of revisited energetic reasoning, which is basically a feasible test with window time adjustments. The efficiency of the proposed lower bound is assessed throughout an extensive computational experiments conducted on a benchmark of 2,100 instances with up to ten centers. The numerical results provide evidence that the proposed lower bound consistently improves the best existing ones.https://ieeexplore.ieee.org/document/7907262/Hybrid flow shopmultiprocessor taskrevisited energetic reasoninglower bound |
| spellingShingle | Lotfi Hidri Anis Gharbi New Efficient Lower Bound for the Hybrid Flow Shop Scheduling Problem With Multiprocessor Tasks IEEE Access Hybrid flow shop multiprocessor task revisited energetic reasoning lower bound |
| title | New Efficient Lower Bound for the Hybrid Flow Shop Scheduling Problem With Multiprocessor Tasks |
| title_full | New Efficient Lower Bound for the Hybrid Flow Shop Scheduling Problem With Multiprocessor Tasks |
| title_fullStr | New Efficient Lower Bound for the Hybrid Flow Shop Scheduling Problem With Multiprocessor Tasks |
| title_full_unstemmed | New Efficient Lower Bound for the Hybrid Flow Shop Scheduling Problem With Multiprocessor Tasks |
| title_short | New Efficient Lower Bound for the Hybrid Flow Shop Scheduling Problem With Multiprocessor Tasks |
| title_sort | new efficient lower bound for the hybrid flow shop scheduling problem with multiprocessor tasks |
| topic | Hybrid flow shop multiprocessor task revisited energetic reasoning lower bound |
| url | https://ieeexplore.ieee.org/document/7907262/ |
| work_keys_str_mv | AT lotfihidri newefficientlowerboundforthehybridflowshopschedulingproblemwithmultiprocessortasks AT anisgharbi newefficientlowerboundforthehybridflowshopschedulingproblemwithmultiprocessortasks |