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

作者：Hino Rei^*; Karuno Yoshiyuki

来源：Journal of Advanced Mechanical Design, Systems and Manufacturing, 2014, 8(5): 14-00038.

DOI：10.1299/jamdsm.2014jamdsm0070

• Engineering optimization
• Scheduling
• Cyclic production
• Heuristic algorithms
• Linear partition
• Dynamic programming

In this paper, we consider a combinatorial optimization problem in a cyclic production system treating identical jobs. The cyclic production system possesses m machines, and every job consists of n tasks. The n 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 s denote the number of jobs being in process during a segment, we also see that the sequence of n tasks of every job is split into s disjoint subsequences of tasks. We define a widget by such a subsequence of tasks. Given a job splitting with the splitting number s, we only have to assign the s 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 s = s* so that for a given tau %26gt; 0, the generated s widgets can be assigned on machines in a segment with length tau. 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.

• 出版日期2014