Revisiting the development trajectory of parallel machine scheduling

Abstract

The research on the Parallel Machine Scheduling Problem (PMSP) has undergone significant development. The most recent comprehensive review of published studies dates back to early 2001. This article presents an algorithmic review of PMSPs, using Main Path Analysis (MPA) to identify seminal knowledge diffusion and development trajectories. This research also sheds light on the less tangible aspects of the PMSP's development by employing Cluster Analysis (CA). Our findings indicate that the scheduling of semiconductor production operations received recent and growing attention, which is mostly driven by the industry’s strategic nature. Specifically, the research cluster relevant to setups —material preparation, tool changes, machine settings, testing, and adjustments— requires investigation to address case-specific operational needs. From a theoretical perspective, further development of batch scheduling is needed, particularly when conflicting objectives are considered. Additionally, developing approximation algorithms for multi-objective optimization to integrate non-financial considerations into production scheduling is expected to continue as a growing research topic.