No-wait job-shop scheduling (NWJSS) problem is one of the classical scheduling problems that exist on many kinds of industry with no-wait constraint, such as metal working, plastic, chemical, and food industries. Seve...No-wait job-shop scheduling (NWJSS) problem is one of the classical scheduling problems that exist on many kinds of industry with no-wait constraint, such as metal working, plastic, chemical, and food industries. Several methods have been proposed to solve this problem, both exact (i.e. integer programming) and metaheuristic methods. Cross entropy (CE), as a new metaheuristic, can be an alternative method to solve NWJSS problem. This method has been used in combinatorial optimization, as well as multi-external optimization and rare-event simulation. On these problems, CE implementation results an optimal value with less computational time in average. However, using original CE to solve large scale NWJSS requires high computational time. Considering this shortcoming, this paper proposed a hybrid of cross entropy with genetic algorithm (GA), called CEGA, on m-machines NWJSS. The results are compared with other metaheuritics: Genetic Algorithm-Simulated Annealing (GASA) and hybrid tabu search. The results showed that CEGA providing better or at least equal makespans in comparison with the other two methods.展开更多
Airline crew rostering is the assignment problem of crew members to planned rotations/pairings for certain month. Airline companies have the monthly task of constructing personalized monthly schedules (roster) for cre...Airline crew rostering is the assignment problem of crew members to planned rotations/pairings for certain month. Airline companies have the monthly task of constructing personalized monthly schedules (roster) for crew members. This problem became more complex and difficult while the aspirations/criterias to assess the quality of roster grew and the constraints increased excessively. This paper proposed the differential evolution (DE) method to solve the airline rostering problem. Different from the common DE, this paper presented random swap as mutation operator. The DE algorithm is proven to be able to find the near optimal solution accurately for the optimization problem. Through numerical experiments with some real datasets, DE showed more competitive results than two other methods, column generation and MOSI (the one used by the Airline). DE produced good results for small and medium datasets, but it still showed reasonable results for large dataset. For large crew rostering problem, we proposed decomposition procedure to solve it in more efficient manner using DE.展开更多
文摘No-wait job-shop scheduling (NWJSS) problem is one of the classical scheduling problems that exist on many kinds of industry with no-wait constraint, such as metal working, plastic, chemical, and food industries. Several methods have been proposed to solve this problem, both exact (i.e. integer programming) and metaheuristic methods. Cross entropy (CE), as a new metaheuristic, can be an alternative method to solve NWJSS problem. This method has been used in combinatorial optimization, as well as multi-external optimization and rare-event simulation. On these problems, CE implementation results an optimal value with less computational time in average. However, using original CE to solve large scale NWJSS requires high computational time. Considering this shortcoming, this paper proposed a hybrid of cross entropy with genetic algorithm (GA), called CEGA, on m-machines NWJSS. The results are compared with other metaheuritics: Genetic Algorithm-Simulated Annealing (GASA) and hybrid tabu search. The results showed that CEGA providing better or at least equal makespans in comparison with the other two methods.
文摘Airline crew rostering is the assignment problem of crew members to planned rotations/pairings for certain month. Airline companies have the monthly task of constructing personalized monthly schedules (roster) for crew members. This problem became more complex and difficult while the aspirations/criterias to assess the quality of roster grew and the constraints increased excessively. This paper proposed the differential evolution (DE) method to solve the airline rostering problem. Different from the common DE, this paper presented random swap as mutation operator. The DE algorithm is proven to be able to find the near optimal solution accurately for the optimization problem. Through numerical experiments with some real datasets, DE showed more competitive results than two other methods, column generation and MOSI (the one used by the Airline). DE produced good results for small and medium datasets, but it still showed reasonable results for large dataset. For large crew rostering problem, we proposed decomposition procedure to solve it in more efficient manner using DE.
