Two Parallel-Machine Scheduling Problems with Function Constraint
The objective of this paper is to minimize both the makespan and the total completion time. Since parallel-machine scheduling which contains the function constraint problem has been a new issue, this paper explored two parallel-machine scheduling problems with function constraint, which refers to th...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2020/2717095 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849397617536008192 |
|---|---|
| author | Chia-Lun Hsu Jan-Ray Liao |
| author_facet | Chia-Lun Hsu Jan-Ray Liao |
| author_sort | Chia-Lun Hsu |
| collection | DOAJ |
| description | The objective of this paper is to minimize both the makespan and the total completion time. Since parallel-machine scheduling which contains the function constraint problem has been a new issue, this paper explored two parallel-machine scheduling problems with function constraint, which refers to the situation that the two machines have a same function but one of the machines has another. We pointed out that the function constraint occurs not only in the manufacturing system but also in the service system. For the makespan problem, we demonstrated that it is NP-hard in the ordinary sense. In addition, we presented a polynomial time heuristic for this problem and have proved its worst-case ratio is not greater than 5/4. Furthermore, we simulated the performance of the algorithm through computational testing. The overall mean percent error of the heuristic is 0.0565%. The results revealed that the proposed algorithm is quite efficient. For the total completion time problem, we have proved that it can be solved in On4 time. |
| format | Article |
| id | doaj-art-ad30cc5533904dcea08defcebf6347fd |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-ad30cc5533904dcea08defcebf6347fd2025-08-20T03:38:55ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2020-01-01202010.1155/2020/27170952717095Two Parallel-Machine Scheduling Problems with Function ConstraintChia-Lun Hsu0Jan-Ray Liao1Department of Electrical Engineering, National Chung-Hsing University, Tai-Chung 402, TaiwanDepartment of Electrical Engineering, National Chung-Hsing University, Tai-Chung 402, TaiwanThe objective of this paper is to minimize both the makespan and the total completion time. Since parallel-machine scheduling which contains the function constraint problem has been a new issue, this paper explored two parallel-machine scheduling problems with function constraint, which refers to the situation that the two machines have a same function but one of the machines has another. We pointed out that the function constraint occurs not only in the manufacturing system but also in the service system. For the makespan problem, we demonstrated that it is NP-hard in the ordinary sense. In addition, we presented a polynomial time heuristic for this problem and have proved its worst-case ratio is not greater than 5/4. Furthermore, we simulated the performance of the algorithm through computational testing. The overall mean percent error of the heuristic is 0.0565%. The results revealed that the proposed algorithm is quite efficient. For the total completion time problem, we have proved that it can be solved in On4 time.http://dx.doi.org/10.1155/2020/2717095 |
| spellingShingle | Chia-Lun Hsu Jan-Ray Liao Two Parallel-Machine Scheduling Problems with Function Constraint Discrete Dynamics in Nature and Society |
| title | Two Parallel-Machine Scheduling Problems with Function Constraint |
| title_full | Two Parallel-Machine Scheduling Problems with Function Constraint |
| title_fullStr | Two Parallel-Machine Scheduling Problems with Function Constraint |
| title_full_unstemmed | Two Parallel-Machine Scheduling Problems with Function Constraint |
| title_short | Two Parallel-Machine Scheduling Problems with Function Constraint |
| title_sort | two parallel machine scheduling problems with function constraint |
| url | http://dx.doi.org/10.1155/2020/2717095 |
| work_keys_str_mv | AT chialunhsu twoparallelmachineschedulingproblemswithfunctionconstraint AT janrayliao twoparallelmachineschedulingproblemswithfunctionconstraint |