File(s) under permanent embargo
A multi-agent system for the weighted earliness tardiness parallel machine problem
journal contribution
posted on 2014-04-01, 00:00 authored by Sergey PolyakovskiySergey Polyakovskiy, R M'HallahThis 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 MAS H , a deterministic heuristic based on multi-agent systems. MAS H 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 MAS H 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 MAS H , whose performance on benchmark instances from the literature is superior to that of existing approaches. The success of MAS H 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.
History
Journal
Computers and operations researchVolume
44Pagination
115 - 136Publisher
ElsevierLocation
Amsterdam, The NetherlandsPublisher DOI
ISSN
0305-0548Language
engPublication classification
C Journal article; C1.1 Refereed article in a scholarly journalCopyright notice
2013, Elsevier Ltd.Usage metrics
Categories
No categories selectedKeywords
parallel machine schedulingmulti-agent systemsartificial intelligenceearlinesstardinesslocal searchScience & TechnologyTechnologyComputer Science, Interdisciplinary ApplicationsEngineering, IndustrialOperations Research & Management ScienceComputer ScienceEngineeringCOMMON DUE-DATEOF-THE-ARTSCHEDULING PROBLEMASSIGNMENT
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC