当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
2022
Shun Ito, Kazuho Kanahara, Tetsuya Oda, Kengo Katayama
An extended NEH based method for permutation flowshop scheduling problem Proceedings Article
In: ICCCM 2022: Proceedings of the 10th International Conference on Computer and Communications Management, pp. 252-256, 2022.
Abstract | BibTeX | タグ: Heuristic, NEH, Permutation flowshop scheduling problem | Links:
@inproceedings{ITO-ICCCM-2022,
title = {An extended NEH based method for permutation flowshop scheduling problem},
author = {Shun Ito and Kazuho Kanahara and Tetsuya Oda and Kengo Katayama},
doi = {https://doi.org/10.1145/3556223.3556261},
year = {2022},
date = {2022-10-16},
urldate = {2022-10-16},
booktitle = {ICCCM 2022: Proceedings of the 10th International Conference on Computer and Communications Management},
pages = {252-256},
abstract = {The Permutation Flowshop Scheduling Problem (PFSP) is an important manufacturing scheduling problem where jobs have to be processed on machines, with each job following the same order at the machines. Since the problem to minimize makespan has been proven NP-hard when the number of machines is larger than three, a number of heuristic methods have been developed for finding high quality solutions in a reasonable computation time. NEH heuristic is one of the most efficient and effective constructive heuristic methods for PFSP. NEH algorithm consists of two key steps 1) order jobs based on priority rule (the original one is the sum (average) processing times of each job); 2) insert jobs one by one according to the initial job order to construct a sequence (solution) of jobs by testing all possible inserting positions for unscheduled jobs. Since the first step is crucial for the resulting solution quality, many different priority rules have been investigated. It is well known that the priority rule based on two moments of the average and standard deviation of processing times to order jobs is effective. Furthermore, a more effective priority rule including a third moment called skewness has been developed recently. In this paper, we present an extended NEH based method called Extended NEH (E-NEH) for PFSP in which the appropriate combination of moments is selected from the three moments step by step, depending on the search situation. Computational results on benchmark problem set showed that E-NEH obtained better results, or at least the competitive ones, than the original NEH and other NEH based methods including the rules based on the three moments although more computation times are required.},
keywords = {Heuristic, NEH, Permutation flowshop scheduling problem},
pubstate = {published},
tppubtype = {inproceedings}
}
The Permutation Flowshop Scheduling Problem (PFSP) is an important manufacturing scheduling problem where jobs have to be processed on machines, with each job following the same order at the machines. Since the problem to minimize makespan has been proven NP-hard when the number of machines is larger than three, a number of heuristic methods have been developed for finding high quality solutions in a reasonable computation time. NEH heuristic is one of the most efficient and effective constructive heuristic methods for PFSP. NEH algorithm consists of two key steps 1) order jobs based on priority rule (the original one is the sum (average) processing times of each job); 2) insert jobs one by one according to the initial job order to construct a sequence (solution) of jobs by testing all possible inserting positions for unscheduled jobs. Since the first step is crucial for the resulting solution quality, many different priority rules have been investigated. It is well known that the priority rule based on two moments of the average and standard deviation of processing times to order jobs is effective. Furthermore, a more effective priority rule including a third moment called skewness has been developed recently. In this paper, we present an extended NEH based method called Extended NEH (E-NEH) for PFSP in which the appropriate combination of moments is selected from the three moments step by step, depending on the search situation. Computational results on benchmark problem set showed that E-NEH obtained better results, or at least the competitive ones, than the original NEH and other NEH based methods including the rules based on the three moments although more computation times are required.