A simulation-optimization framework for generating dynamic dispatching rules for stochastic job shop with earliness and tardiness penalties. (April 2022)

• Record Type: Journal Article
• Authors: Morady Gohareh, Mehdy; Mansouri, Ehsan
• Is Part Of: Computers & operations research. Volume 140(2022)
• Publication Date: 2022-04
• Subjects: Stochastic job shop scheduling -- Earliness-tardiness penalty -- Simulation-optimization -- Central limit theorem -- Ant colony -- Markov decision process; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105650
• Languages: English
• ISSNs: 0305-0548

Abstract

Graphical abstract: Highlights: Stochastic job shop scheduling is converted to a near-Markov decision process. Simulation is used to generate a structured database of states. Simulation is used to accumulate some memory measure in the form of pheromone trails. A solution method is devised using the accumulated memory and Central Limit Theorem. The method delivers instance specific, dynamic and global dispatching rules. Abstract: Most of real-world problems regarding production and manufacturing contain stochastic parameters. In this research, job shop scheduling problem with stochastic process times and weighted earliness-tardiness objective function is considered. When machines are freed in the course of manufacturing, a job has to be selected from the line and passed on the machine. In deterministic job shop scheduling, the selection process is static. In the stochastic variants however, dynamic or real-time dispatching rules may be used. The goal of this paper is to develop a solution method for stochastic job shop scheduling problem that delivers dynamic and global dispatching rules that use information pertaining to the entire shop floor. In order to achieve this, the problem is converted to a near-Markov decision process that comprises an alternate sequence of states (machines becoming free) and actions (selecting a job). Using simulation and ant colony, a database of states is generated and a meaningful pheromone trail for each state is formed gradually. The pheromones act as a memory mechanism and, in combination with a heuristic based on the Central Limit Theorem, comprise the dispatching rule. Efficiency of this approach is investigated through extensive simulation. Results show an average of 92% cost reduction in comparison with the random dispatching rule. Moreover, the approach yields better results in congested scheduling systems.