Linear partition heuristics for a generalized delivery workload balancing problem with an allocation of cargoes to interim storage lanes

DOI Web Site 2 References
  • KARUNO Yoshiyuki
    Faculty of Mechanical Engineering, Kyoto Institute of Technology
  • UOTANI Yutaro
    Graduate School of Science and Technology, Kyoto Institute of Technology

Abstract

<p>Given m periodic deliveries performed by a single tractor and a finite set N of cargoes with their arrival times and processing times, we are asked to find a feasible partition of the cargo set N into m disjoint subsets. The workload of a delivery is defined to be the sum of processing times of cargoes assigned to the delivery. The m periodic deliveries are required to be balanced on their workloads. We treat the maximum distance of a workload from a prescribed guiding mark as a balancing criterion. The maximum distance is equivalent to the ordinary maximum workload over the m periodic deliveries when the guiding mark is given to be zero. In the actual assembly plant motivating this study, allocating each cargo to one of interim storage lanes determines a partition of the cargo set N, and the feasibility of a partition of the N depends on the practical fact. In this paper, we propose a dynamic programming based heuristic algorithm which runs in polynomial time and returns a linear partition of a cargo list. Since the maximum distance criterion contains the ordinary maximum workload as a special case, the proposed heuristic can be regarded as a generalization of an existing linear partition procedure of minimizing the maximum sum of processing times for a subsequence of cargoes. We also conduct numerical experiments to demonstrate the performance of the proposed heuristic with a meaningful guiding mark.</p>

Journal

References(2)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top