An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints
This study considers order acceptance and scheduling problems in unrelated parallel machines with several practical constraints, including order release times, sequence-dependent setup times, machines’ unequal ready times, and preventive maintenance. In a make-to-order production environment, issues...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/6/1433 |
| _version_ | 1797610311594803200 |
|---|---|
| author | Chun-Lung Chen |
| author_facet | Chun-Lung Chen |
| author_sort | Chun-Lung Chen |
| collection | DOAJ |
| description | This study considers order acceptance and scheduling problems in unrelated parallel machines with several practical constraints, including order release times, sequence-dependent setup times, machines’ unequal ready times, and preventive maintenance. In a make-to-order production environment, issues with order acceptance and scheduling are mainly caused by the limited production capacity of a factory, which makes it impossible to accept all orders. Consequently, some orders must be rejected in order to maximize profits and the accepted orders must be completed by the due date or no later than the deadline. An iterated population-based metaheuristic is proposed to solve the problems. The algorithm begins with an efficient initial solution generator to generate an initial solution, and then uses the destruction and construction procedure to generate a population with multiple solutions. Then, a solution is selected from the population, and a variable neighborhood descent search algorithm with several new reduced-size neighborhood structures is applied to improve the selected solution. Following the completion of the local search, a method for updating the members of the population was devised to enhance its diversity. Finally, the metaheuristic allows the populations to evolve for several generations until the termination condition is satisfied. To evaluate the performance of the proposed metaheuristic, a heuristic rule and an iterated local search algorithm are examined and compared. The computational experimental results indicate that the presented metaheuristic outperforms the other heuristics. |
| first_indexed | 2024-03-11T06:13:45Z |
| format | Article |
| id | doaj.art-cf8804fb4cff4e9eb0a113af67af64eb |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T06:13:45Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-cf8804fb4cff4e9eb0a113af67af64eb2023-11-17T12:28:32ZengMDPI AGMathematics2227-73902023-03-01116143310.3390/math11061433An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical ConstraintsChun-Lung Chen0Department of Accounting Information, Takming University of Science and Technology, Taipei 11451, TaiwanThis study considers order acceptance and scheduling problems in unrelated parallel machines with several practical constraints, including order release times, sequence-dependent setup times, machines’ unequal ready times, and preventive maintenance. In a make-to-order production environment, issues with order acceptance and scheduling are mainly caused by the limited production capacity of a factory, which makes it impossible to accept all orders. Consequently, some orders must be rejected in order to maximize profits and the accepted orders must be completed by the due date or no later than the deadline. An iterated population-based metaheuristic is proposed to solve the problems. The algorithm begins with an efficient initial solution generator to generate an initial solution, and then uses the destruction and construction procedure to generate a population with multiple solutions. Then, a solution is selected from the population, and a variable neighborhood descent search algorithm with several new reduced-size neighborhood structures is applied to improve the selected solution. Following the completion of the local search, a method for updating the members of the population was devised to enhance its diversity. Finally, the metaheuristic allows the populations to evolve for several generations until the termination condition is satisfied. To evaluate the performance of the proposed metaheuristic, a heuristic rule and an iterated local search algorithm are examined and compared. The computational experimental results indicate that the presented metaheuristic outperforms the other heuristics.https://www.mdpi.com/2227-7390/11/6/1433order acceptance and schedulingiterated population-based metaheuristicunrelated parallel machines |
| spellingShingle | Chun-Lung Chen An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints Mathematics order acceptance and scheduling iterated population-based metaheuristic unrelated parallel machines |
| title | An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints |
| title_full | An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints |
| title_fullStr | An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints |
| title_full_unstemmed | An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints |
| title_short | An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints |
| title_sort | iterated population based metaheuristic for order acceptance and scheduling in unrelated parallel machines with several practical constraints |
| topic | order acceptance and scheduling iterated population-based metaheuristic unrelated parallel machines |
| url | https://www.mdpi.com/2227-7390/11/6/1433 |
| work_keys_str_mv | AT chunlungchen aniteratedpopulationbasedmetaheuristicfororderacceptanceandschedulinginunrelatedparallelmachineswithseveralpracticalconstraints AT chunlungchen iteratedpopulationbasedmetaheuristicfororderacceptanceandschedulinginunrelatedparallelmachineswithseveralpracticalconstraints |