An application of the linear partition for scheduling identical jobs in a restricted cyclic production system



    • HINO Rei
    • Department of Mechanical Science and Engineering, Nagoya University
    • KARUNO Yoshiyuki
    • Department of Mechanical and System Engineering, Kyoto Institute of Technology


In this paper, we consider a combinatorial optimization problem in a cyclic production system treating identical jobs. The cyclic production system possesses <i>m</i> machines, and every job consists of <i>n</i> tasks. The <i>n</i> tasks must be processed in a predetermined sequence, and each task must be processed on a predetermined machine. Each machine can process at most one task at a time, and no preemption for task processing is allowed. The job may visit a machine more than once to be completed, i.e., it is a re-entrant one. We focus on a restricted cyclic schedule, saying a periodically segmental schedule, where no task lies over consecutive segments. For a periodically segmental schedule, let <i>s</i> denote the number of jobs being in process during a segment, we also see that the sequence of <i>n</i> tasks of every job is split into <i>s</i> disjoint subsequences of tasks. We define a widget by such a subsequence of tasks. Given a job splitting with the splitting number <i>s</i>, we only have to assign the <i>s</i> widgets on machines in a segment to obtain a periodically segmental schedule. The problem to be discussed here asks to find a job splitting with the minimum splitting number <i>s</i> = <i>s</i><sup>∗</sup> so that for a given <i>τ</i> > 0, the generated <i>s</i> widgets can be assigned on machines in a segment with length <i>τ</i>. We propose a heuristic algorithm utilizing a dynamic programming based linear partition for finding a job splitting. Numerical examples demonstrate the behavior of the proposed heuristic algorithm.


  • Journal of Advanced Mechanical Design, Systems, and Manufacturing

    Journal of Advanced Mechanical Design, Systems, and Manufacturing 8(5), JAMDSM0070-JAMDSM0070, 2014

    一般社団法人 日本機械学会