An application of the linear partition for scheduling identical jobs in a restricted cyclic production system
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The Japan Society of Mechanical Engineers
2014-10-01
|
| Series: | Journal of Advanced Mechanical Design, Systems, and Manufacturing |
| Subjects: | |
| Online Access: | https://www.jstage.jst.go.jp/article/jamdsm/8/5/8_2014jamdsm0070/_pdf/-char/en |
| _version_ | 1818521903581626368 |
|---|---|
| author | Rei HINO Yoshiyuki KARUNO |
| author_facet | Rei HINO Yoshiyuki KARUNO |
| author_sort | Rei HINO |
| collection | DOAJ |
| description | 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 τ > 0, the generated s widgets can be assigned on machines in a segment with length τ. 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. |
| first_indexed | 2024-12-11T01:57:32Z |
| format | Article |
| id | doaj.art-b14a1c24b565471c804fc663d5062349 |
| institution | Directory Open Access Journal |
| issn | 1881-3054 |
| language | English |
| last_indexed | 2024-12-11T01:57:32Z |
| publishDate | 2014-10-01 |
| publisher | The Japan Society of Mechanical Engineers |
| record_format | Article |
| series | Journal of Advanced Mechanical Design, Systems, and Manufacturing |
| spelling | doaj.art-b14a1c24b565471c804fc663d50623492022-12-22T01:24:35ZengThe Japan Society of Mechanical EngineersJournal of Advanced Mechanical Design, Systems, and Manufacturing1881-30542014-10-0185JAMDSM0070JAMDSM007010.1299/jamdsm.2014jamdsm0070jamdsmAn application of the linear partition for scheduling identical jobs in a restricted cyclic production systemRei HINO0Yoshiyuki KARUNO1Department of Mechanical Science and Engineering, Nagoya UniversityDepartment of Mechanical and System Engineering, Kyoto Institute of TechnologyIn 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 τ > 0, the generated s widgets can be assigned on machines in a segment with length τ. 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.https://www.jstage.jst.go.jp/article/jamdsm/8/5/8_2014jamdsm0070/_pdf/-char/enengineering optimizationschedulingcyclic productionheuristic algorithmslinear partitiondynamic programming |
| spellingShingle | Rei HINO Yoshiyuki KARUNO An application of the linear partition for scheduling identical jobs in a restricted cyclic production system Journal of Advanced Mechanical Design, Systems, and Manufacturing engineering optimization scheduling cyclic production heuristic algorithms linear partition dynamic programming |
| title | An application of the linear partition for scheduling identical jobs in a restricted cyclic production system |
| title_full | An application of the linear partition for scheduling identical jobs in a restricted cyclic production system |
| title_fullStr | An application of the linear partition for scheduling identical jobs in a restricted cyclic production system |
| title_full_unstemmed | An application of the linear partition for scheduling identical jobs in a restricted cyclic production system |
| title_short | An application of the linear partition for scheduling identical jobs in a restricted cyclic production system |
| title_sort | application of the linear partition for scheduling identical jobs in a restricted cyclic production system |
| topic | engineering optimization scheduling cyclic production heuristic algorithms linear partition dynamic programming |
| url | https://www.jstage.jst.go.jp/article/jamdsm/8/5/8_2014jamdsm0070/_pdf/-char/en |
| work_keys_str_mv | AT reihino anapplicationofthelinearpartitionforschedulingidenticaljobsinarestrictedcyclicproductionsystem AT yoshiyukikaruno anapplicationofthelinearpartitionforschedulingidenticaljobsinarestrictedcyclicproductionsystem AT reihino applicationofthelinearpartitionforschedulingidenticaljobsinarestrictedcyclicproductionsystem AT yoshiyukikaruno applicationofthelinearpartitionforschedulingidenticaljobsinarestrictedcyclicproductionsystem |