Simultaneous job input sequencing and vehicle dispatching in a single-vehicle automated guided vehicle system: a heuristic branch-and-bound approach coupled with a discrete events simulation model

This paper addresses the scheduling problem in automated manufacturing environments, whose problem encompasses all the decisions related to the allocation of resources over the time horizon in order to best satisfy a set of objectives. It concentrates in particular on the job-input sequencing and vehicle-dispatching problems in a manufacturing environment using a single-vehicle automated guided vehicle system. The problem is solved using a branch-and-bound coupled with a discrete event simulation model. The branch-and-bound focuses on the job-input sequencing problem to determine the order in which the jobs enter the manufacturing system. The discrete event simulation model evaluates this job sequence under given vehicle and machine dispatching rules. The discrete event simulation model permits one to take into account all the working constraints: the maximal number of jobs simultaneously allowed in the system, the input/output buffers with finite capacities, the dynamic behaviour of the system under study and, thus, the impact of vehicle blocking and congestion as well as the impact of the machine blocking. A benchmark test is performed to investigate the system performances and the makespan depending on the job input sequencing, the vehicle and machine dispatching. The framework is benchmarked on 20 instances under different vehicle dispatching rules.