Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation Time
This paper investigates a two-machine group scheduling problem with sequence-independent setup times and round-trip transportation times, which is derived from the production management requirements of modern steel manufacturing enterprises. The objective is to minimize the makespan. Addressing limi...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/6/888 |
| _version_ | 1797240164464984064 |
|---|---|
| author | Yu Ni Shufen Dai Shuaipeng Yuan Bailin Wang Zhuolun Zhang |
| author_facet | Yu Ni Shufen Dai Shuaipeng Yuan Bailin Wang Zhuolun Zhang |
| author_sort | Yu Ni |
| collection | DOAJ |
| description | This paper investigates a two-machine group scheduling problem with sequence-independent setup times and round-trip transportation times, which is derived from the production management requirements of modern steel manufacturing enterprises. The objective is to minimize the makespan. Addressing limitations in prior studies, we consider a critical but largely ignored transportation method, namely round-trip transportation, and restricted transporter capacity between machines. To solve this problem, a mixed-integer programming model is first developed. Then, the problem complexity is analyzed for situations with both single and unlimited transporters. For the NP-hard case of a single transporter, we design an efficient two-stage heuristic algorithm with proven acceptable solution quality bounds. Extensive computational experiments based on steel plant data demonstrate the effectiveness of our approach in providing near-optimal solutions, and the maximum deviation between our algorithm and the optimal solution is 1.38%. This research can provide an operable optimization method that is valuable for group scheduling and transportation scheduling. |
| first_indexed | 2024-04-24T18:03:05Z |
| format | Article |
| id | doaj.art-d292598918ea404697d8a6ca2dc1ad71 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-04-24T18:03:05Z |
| publishDate | 2024-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-d292598918ea404697d8a6ca2dc1ad712024-03-27T13:53:14ZengMDPI AGMathematics2227-73902024-03-0112688810.3390/math12060888Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation TimeYu Ni0Shufen Dai1Shuaipeng Yuan2Bailin Wang3Zhuolun Zhang4School of Economics and Management, University of Science and Technology Beijing, No. 30, Xueyuan Road, Haidian District, Beijing 100083, ChinaSchool of Economics and Management, University of Science and Technology Beijing, No. 30, Xueyuan Road, Haidian District, Beijing 100083, ChinaSchool of Economics and Management, University of Science and Technology Beijing, No. 30, Xueyuan Road, Haidian District, Beijing 100083, ChinaSchool of Economics and Management, University of Science and Technology Beijing, No. 30, Xueyuan Road, Haidian District, Beijing 100083, ChinaSchool of Economics and Management, University of Science and Technology Beijing, No. 30, Xueyuan Road, Haidian District, Beijing 100083, ChinaThis paper investigates a two-machine group scheduling problem with sequence-independent setup times and round-trip transportation times, which is derived from the production management requirements of modern steel manufacturing enterprises. The objective is to minimize the makespan. Addressing limitations in prior studies, we consider a critical but largely ignored transportation method, namely round-trip transportation, and restricted transporter capacity between machines. To solve this problem, a mixed-integer programming model is first developed. Then, the problem complexity is analyzed for situations with both single and unlimited transporters. For the NP-hard case of a single transporter, we design an efficient two-stage heuristic algorithm with proven acceptable solution quality bounds. Extensive computational experiments based on steel plant data demonstrate the effectiveness of our approach in providing near-optimal solutions, and the maximum deviation between our algorithm and the optimal solution is 1.38%. This research can provide an operable optimization method that is valuable for group scheduling and transportation scheduling.https://www.mdpi.com/2227-7390/12/6/888group schedulingtransportation timemathematical modelheuristic algorithm |
| spellingShingle | Yu Ni Shufen Dai Shuaipeng Yuan Bailin Wang Zhuolun Zhang Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation Time Mathematics group scheduling transportation time mathematical model heuristic algorithm |
| title | Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation Time |
| title_full | Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation Time |
| title_fullStr | Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation Time |
| title_full_unstemmed | Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation Time |
| title_short | Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation Time |
| title_sort | model and algorithm for a two machine group scheduling problem with setup and transportation time |
| topic | group scheduling transportation time mathematical model heuristic algorithm |
| url | https://www.mdpi.com/2227-7390/12/6/888 |
| work_keys_str_mv | AT yuni modelandalgorithmforatwomachinegroupschedulingproblemwithsetupandtransportationtime AT shufendai modelandalgorithmforatwomachinegroupschedulingproblemwithsetupandtransportationtime AT shuaipengyuan modelandalgorithmforatwomachinegroupschedulingproblemwithsetupandtransportationtime AT bailinwang modelandalgorithmforatwomachinegroupschedulingproblemwithsetupandtransportationtime AT zhuolunzhang modelandalgorithmforatwomachinegroupschedulingproblemwithsetupandtransportationtime |