Learning dispatching rules for single machine scheduling with dynamic arrivals based on decision trees and feature construction

Sungbum Jun and Seokcheon Lee

International Journal of Production Research, 2021, vol. 59, issue 9, 2838-2856

Abstract: In this paper, we address the dynamic single-machine scheduling problem for minimisation of total weighted tardiness by learning of dispatching rules (DRs) from schedules. We propose a decision-tree-based approach called Generation of Rules Automatically with Feature construction and Tree-based learning (GRAFT) in order to extract dispatching rules from existing or good schedules. GRAFT consists of two phases: learning a DR from schedules, and improving the DR with feature-construction-based genetic programming. With respect to the process of learning DRs from schedules, we present an approach for transforming schedules into training data containing underlying scheduling decisions and generating a decision-tree-based DR. Thereafter, the second phase improves the learned DR by feature-construction-based genetic programming so as to minimise the average total weighted tardiness. We conducted experiments to verify the performance of the proposed approach, and the results showed that it outperforms the existing dispatching rules. Moreover, the proposed algorithm is effective in terms of extracting scheduling insights in such understandable formats as IF–THEN rules from existing schedules and improving DRs by grafting a new branch with a discovered attribute into a decision tree.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2020.1741716 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:59:y:2021:i:9:p:2838-2856

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2020.1741716

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().