TY - JOUR
T1 - Applied column generation-based approach to solve supply chain scheduling problems
AU - Chang, Yung-Chia
AU - Chang, Kuei Hu
AU - Chang, Teng Kai
PY - 2013/7/1
Y1 - 2013/7/1
N2 - More and more enterprises have chosen to adopt a made-to-order business model in order to satisfy diverse and rapidly changing customer demand. In such a business model, enterprises are devoted to reducing inventory levels in order to upgrade the competitiveness of the products. However, reductions in inventory levels and short lead times force the operation between production and distribution to cooperate closely, thus increasing the practicability of integrating the production and distribution stages. The complexity of supply chain scheduling problems (integrated production and distribution scheduling) is known to be NP-hard. To address the issues above, an efficient algorithm to solve the supply chain scheduling problem is needed. This paper studies a supply chain scheduling problem in which the production stage is modelled by an identical parallel machine scheduling problem and the distribution stage is modelled by a capacitated vehicle routing problem. Given a set of customer orders (jobs), the problem is to find a supply chain schedule such that the weighted summation of total job weighted completion time and total job delivering cost are minimised. The studied problem was first formulated as an integer programme and then solved by using column generation techniques in conjunction with a branch-and-bound approach to optimality. The results of the computational experiments indicate that the proposed approach can solve the test problems to optimality. Moreover, the average gap between the optimal solutions and the lower bounds is no more than 1.32% for these test problems.
AB - More and more enterprises have chosen to adopt a made-to-order business model in order to satisfy diverse and rapidly changing customer demand. In such a business model, enterprises are devoted to reducing inventory levels in order to upgrade the competitiveness of the products. However, reductions in inventory levels and short lead times force the operation between production and distribution to cooperate closely, thus increasing the practicability of integrating the production and distribution stages. The complexity of supply chain scheduling problems (integrated production and distribution scheduling) is known to be NP-hard. To address the issues above, an efficient algorithm to solve the supply chain scheduling problem is needed. This paper studies a supply chain scheduling problem in which the production stage is modelled by an identical parallel machine scheduling problem and the distribution stage is modelled by a capacitated vehicle routing problem. Given a set of customer orders (jobs), the problem is to find a supply chain schedule such that the weighted summation of total job weighted completion time and total job delivering cost are minimised. The studied problem was first formulated as an integer programme and then solved by using column generation techniques in conjunction with a branch-and-bound approach to optimality. The results of the computational experiments indicate that the proposed approach can solve the test problems to optimality. Moreover, the average gap between the optimal solutions and the lower bounds is no more than 1.32% for these test problems.
KW - column generation approach
KW - dynamic programming
KW - identical parallel machine
KW - supply chain scheduling
UR - http://www.scopus.com/inward/record.url?scp=84880507064&partnerID=8YFLogxK
U2 - 10.1080/00207543.2013.774476
DO - 10.1080/00207543.2013.774476
M3 - Article
AN - SCOPUS:84880507064
SN - 0020-7543
VL - 51
SP - 4070
EP - 4086
JO - International Journal of Production Research
JF - International Journal of Production Research
IS - 13
ER -