Decomposition-based Makespan Minimization in Job Shops

Katsumi Morikawa,Katsuhiko Takahashi 대한산업공학회 2006 Industrial Engineeering & Management Systems Vol.5 No.1

A Flexible Branch and Bound Method for the Job Shop Scheduling Problem

Katsumi Morikawa,Katsuhiko Takahashi 대한산업공학회 2009 Industrial Engineeering & Management Systems Vol.8 No.4

This paper deals with the makespan minimization problem of job shops. The problem is known as one of hard problems to optimize, and therefore, many heuristic methods have been proposed by many researchers. The aim of this study is also to propose a heuristic scheduling method for the problem. However, the difference between the proposed method and many other heuristics is that the proposed method is based on depth-first branch and bound, and thus it is possible to find an optimal solution at least in principle. To accelerate the search, when a node is judged hopeless in the search tree, the proposed flexible branch and bound method can indicate a higher backtracking node. The unexplored nodes are stored and may be explored later to realize the strict optimization. Two methods are proposed to generate the backtracking point based on the critical path of the current best feasible schedule, and the minimum lower bound for the makespan in the unexplored sub-problems. Schedules are generated based on Giffler and Thompson"s active schedule generation algorithm. Acceleration of the search by the flexible branch and bound is confirmed by numerical experiment.

Branch and Bound based Makespan Minimization using the Rescheduling

Katsumi Morikawa,Tsuyoshi Satake 대한산업공학회 2003 Industrial Engineeering & Management Systems Vol.2 No.2

Component Commonality and Order Matching Rules in Make-to-Forecast Production

Katsumi Morikawa,Yusuke Deguchi,Katsuhiko Takahashi,Daisuke Hirotani 대한산업공학회 2010 Industrial Engineeering & Management Systems Vol.9 No.3

Make-to-forecast production is a way to realize high customization and fast responsiveness. This study firstly investigates the effect of introducing a common component in a make-to-forecast production environment. The common component can eliminate a modification step, which is a major cost component in make-to-forecast production. It is illustrated, however, that introducing a versatile component that merely covers several variants is unattractive, and thus adding values to the common component is inevitable in this environment. Secondly, an order-matching rule under the condition that two partially overlapped delivery lead time intervals exist is proposed. The rule considers the effect of matching orders to units that can cover both intervals. An alternative re-matching rule is also developed and examined. Numerical experiments clarify that the proposed rule generally realizes higher contribution ratio and lower percentages of orphans and rejected orders. The proposed re-matching rule increases the average contribution ratio at the expense of increased orphans and order rejections.

A Flexible Branch and Bound Method for the Job Shop Scheduling Problem

Morikawa, Katsumi,Takahashi, Katsuhiko Korean Institute of Industrial Engineers 2009 Industrial Engineeering & Management Systems Vol.8 No.4

This paper deals with the makespan minimization problem of job shops. The problem is known as one of hard problems to optimize, and therefore, many heuristic methods have been proposed by many researchers. The aim of this study is also to propose a heuristic scheduling method for the problem. However, the difference between the proposed method and many other heuristics is that the proposed method is based on depth-first branch and bound, and thus it is possible to find an optimal solution at least in principle. To accelerate the search, when a node is judged hopeless in the search tree, the proposed flexible branch and bound method can indicate a higher backtracking node. The unexplored nodes are stored and may be explored later to realize the strict optimization. Two methods are proposed to generate the backtracking point based on the critical path of the current best feasible schedule, and the minimum lower bound for the makespan in the unexplored sub-problems. Schedules are generated based on Giffler and Thompson's active schedule generation algorithm. Acceleration of the search by the flexible branch and bound is confirmed by numerical experiment.

Component Commonality and Order Matching Rules in Make-to-Forecast Production

Morikawa, Katsumi,Deguchi, Yusuke,Takahashi, Katsuhiko,Hirotani, Daisuke Korean Institute of Industrial Engineers 2010 Industrial Engineeering & Management Systems Vol.9 No.3

Make-to-forecast production is a way to realize high customization and fast responsiveness. This study firstly investigates the effect of introducing a common component in a make-to-forecast production environment. The common component can eliminate a modification step, which is a major cost component in make-to-forecast production. It is illustrated, however, that introducing a versatile component that merely covers several variants is unattractive, and thus adding values to the common component is inevitable in this environment. Secondly, an order-matching rule under the condition that two partially overlapped delivery lead time intervals exist is proposed. The rule considers the effect of matching orders to units that can cover both intervals. An alternative re-matching rule is also developed and examined. Numerical experiments clarify that the proposed rule generally realizes higher contribution ratio and lower percentages of orphans and rejected orders. The proposed re-matching rule increases the average contribution ratio at the expense of increased orphans and order rejections.

Analysis of Y-Shaped Self-Balancing Line with Walk-Back and Travel Time

Daisuke Hirotani,Katsumi Morikawa,Katsuhiko Takahashi,Keisuke Nagasawa 대한산업공학회 2018 Industrial Engineeering & Management Systems Vol.17 No.2

In traditional assembly lines, each worker is usually assigned a fixed work station. However, when an imbalance be-tween workers’ speeds exists, the production rate of the line decreases. To avoid this problem, the “self-balancing line” was introduced. Although typically assumed to be serial, recent studies have assumed a Y-shaped type line (with two sub-lines that then combine). However, as the workers take more time to travel in this arrangement, walk-back and travel time must be considered. Furthermore, when considering more than two workers, the condition that balanc-es the line changes according to the length of the sub-lines. In this paper, the authors first derive the condition that balances the line for three workers, and then analyze the characteristics of this type of line. Finally, the authors find the condition that balances the line for n workers

A New Worker Policy for Self-Balancing Production Line with Stations

Hirotani, Daisuke,Morikawa, Katsumi,Takahashi, Katsuhiko Korean Institute of Industrial Engineers 2011 Industrial Engineeering & Management Systems Vol.10 No.3

In traditional production lines, such as assembly lines, each worker is usually assigned to a particular fixed work, and decreasing the task to master the assigned work is valuated. However, when an imbalance exists between workers' speeds, if a worker delays the overall work in the production line, the production rate of the particular line will also decrease. To avoid this problem, the "Self-Balancing Production Line" was introduced. In this type of production line, each worker is assigned work dynamically, and when specific conditions are satisfied, production remains balanced. Characteristics of these lines that can be preempted at any place have already been analyzed by some researchers. A previous paper examined the situation in which only a single worker can process one machine and cannot preempt processing, and the improved policy of an ordinary selfbalancing production line, which specifies which stations workers can process and how workers can behave. This policy achieveda high production rate with only four stations and two workers (Buzacott, 2002). In that paper, worker processing stations and the behavior of a specific worker were limited, andthe paper focused only on specific stations and workers. Therefore, it is not applicable to any worker sequence. In this paper, we focus on other ways to decrease cycle time. In this kind of line, a worker processes at his or her speed. Therefore, if a worker is assigned stations according to his or her speed, the line can decrease cycle time. To do so, we relax the assumptions of this type of line and set a new condition. Under these conditions, we compare our results to the results of previous papers.

A New Worker Policy for Self-Balancing Production Line with Stations

Daisuke Hirotani,Katsumi Morikawa,Katsuhiko Takahashi 대한산업공학회 2011 Industrial Engineeering & Management Systems Vol.10 No.3

In traditional production lines, such as assembly lines, each worker is usually assigned to a particular fixed work, and decreasing the task to master the assigned work is valuated. However, when an imbalance exists between workers" speeds, if a worker delays the overall work in the production line, the production rate of the particular line will also decrease. To avoid this problem, the "Self-Balancing Production Line" was introduced. In this type of production line, each worker is assigned work dynamically, and when specific conditions are satisfied, production remains balanced. Characteristics of these lines that can be preempted at any place have already been analyzed by some researchers. A previous paper examined the situation in which only a single worker can process one machine and cannot preempt processing, and the improved policy of an ordinary self-balancing production line, which specifies which stations workers can process and how workers can behave.This policy achieveda high production rate with only four stations and two workers (Buzacott, 2002). In that paper, worker processing stations and the behavior of a specific worker were limited, andthe paper focused only on specific stations and workers. Therefore, it is not applicable to any worker sequence. In this paper, we focus on other ways to decrease cycle time. In this kind of line, a worker processes at his or her speed. Therefore, if a worker is assigned stations according to his or her speed, the line can decrease cycle time. To do so, we relax the assumptions of this type of line and set a new condition. Under these conditions, we compare our results to the results of previous papers.

Influence of Time to Walk Back and Comparing for the Self-balancing Production Line

Daisuke Hirotani,Myreshka,Katsumi Morikawa,Katsuhiko Takahashi 대한산업공학회 2005 Industrial Engineeering & Management Systems Vol.4 No.1