A multi-agent system for the weighted earliness tardiness parallel machine problem

Abstract

This paper studies the weighted earliness tardiness parallel machine problem where jobs have different processing times and distinct due dates. This NP hard problem arises in most just-in-time production environments. It is herein modeled as a mixed integer program, and solved using MASH, a deterministic heuristic based on multi-agent systems. MASH has three types of agents: I, G, and M. The I-agents are free jobs that need to be scheduled, whereas the G-agents are groups of jobs already assigned to machines. The M-agent acts as the system's manager of the independent intelligent I- and G-agents, which are driven by their own goals, fitness assessments, and context-dependent decision rules. The I- and G-agents employ exact and approximate approaches as part of their decisional process while the M-agent uses local search mechanisms to improve their (partial) solutions. The design of MASH is innovative in the way its intelligent agents determine bottleneck clusters and resolve conflicts for time slots. The numerical results provide computational evidence of the efficiency of MASH, whose performance on benchmark instances from the literature is superior to that of existing approaches. The success of MASH and its modularity make it a viable alternative to more complex manufacturing problems. Most importantly, they demonstrate the benefits of the hybridization of artificial intelligence and operations research. © 2013 Elsevier Ltd.