Crane scheduling problem with non-interference constraints in a steel coil distribution centre

Abstract

This article deals with a parallel machine scheduling problem subject to non-interference constraints. This situation often appears at logistic centres, such as depots, warehouses and stockyards. The analyzed scenario is based on a real case at a distribution centre of steel coils, where two cranes using the same rail must load dispatching trucks. We analyze this case by modelling the situation through a parallel machine perspective and considering two mechanisms to deal with the machine interference, . In the first approach, the machine interference is dealt by scheduling whole trucks. In the second one, we schedule the trucks and the coils within. The proposed mathematical models are able to solve small and medium instances, thus, we develop two genetic algorithms to solve real size instances, allowing the analysis of different storage policies. Results show that the genetic approach is able to find near-optimal solutions independently of the policy, with solutions gap ranging from 10 to 2.1%.

Keywords:

• scheduling
• mathematical programming
• genetic algorithms
• warehousing systems
• non-interference constraints

Notes

No potential conflict of interest was reported by the authors.

1 If we consider the same optimally solved 50 coils instances, is equal to 574, 481 and 482 for the scenarios R, C and GC, respectively. C and GC find, respectively, an average of 1823 and 1811 for the same group of optimally solved instances of 100 coils.

2 If we consider the same optimally solved 20 coils instances, is equal to 138, 132 and 130 for the scenarios R, C and GC, respectively.

3 In the case each truck j represents a sequence of its coils randomly arranged.

4 If we consider the same optimally solved 50 coils instances for the problem, is equal to 574, 481 and 482 for the scenarios R, C and GC, respectively. C and GC find, respectively, an average of 1823 and 1811 for the same group of optimally solved instances of 100 coils.

Additional information

Funding

This work has been partially supported by FAPEMIG - Brazil, CNPq - Brazil and by LOSI Laboratory of UTT - France.