東華大學圖書館 |

Lot-Sizing Problem for a Multi-Item Multi-level Capacitated Batch Production System with Setup Carryover, Emission Control and Backlogging using a Dynamic Program and Decomposition Heuristic.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Lot-Sizing Problem for a Multi-Item Multi-level Capacitated Batch Production System with Setup Carryover, Emission Control and Backlogging using a Dynamic Program and Decomposition Heuristic./
Author:	Chowdhury, Nusrat Tarin.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2018,
Description:	167 p.
Notes:	Source: Dissertations Abstracts International, Volume: 80-04, Section: B.
Contained By:	Dissertations Abstracts International80-04B.
Subject:	Applied Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10931538
ISBN:	9780438470569

Lot-Sizing Problem for a Multi-Item Multi-level Capacitated Batch Production System with Setup Carryover, Emission Control and Backlogging using a Dynamic Program and Decomposition Heuristic.
Chowdhury, Nusrat Tarin.

Lot-Sizing Problem for a Multi-Item Multi-level Capacitated Batch Production System with Setup Carryover, Emission Control and Backlogging using a Dynamic Program and Decomposition Heuristic. - Ann Arbor : ProQuest Dissertations & Theses, 2018 - 167 p.

Source: Dissertations Abstracts International, Volume: 80-04, Section: B.

Thesis (Ph.D.)--University of Windsor (Canada), 2018.

This item must not be sold to any third party vendors.

Wagner and Whitin (1958) develop an algorithm to solve the dynamic Economic Lot-Sizing Problem (ELSP), which is widely applied in inventory control, production planning, and capacity planning. The original algorithm runs in O(T 2) time, where T is the number of periods of the problem instance. Afterward few linear-time algorithms have been developed to solve the Wagner-Whitin (WW) lot-sizing problem; examples include the ELSP and equivalent Single Machine Batch-Sizing Problem (SMBSP). This dissertation revisits the algorithms for ELSPs and SMBSPs under WW cost structure, presents a new efficient linear-time algorithm, and compares the developed algorithm against comparable ones in the literature. The developed algorithm employs both lists and stacks data structure, which is completely a different approach than the rest of the algorithms for ELSPs and SMBSPs. Analysis of the developed algorithm shows that it executes fewer number of basic actions throughout the algorithm and hence it improves the CPU time by a maximum of 51.40% for ELSPs and 29.03% for SMBSPs. It can be concluded that the new algorithm is faster than existing algorithms for both ELSPs and SMBSPs. Lot-sizing decisions are crucial because these decisions help the manufacturer determine the quantity and time to produce an item with a minimum cost. The efficiency and productivity of a system is completely dependent upon the right choice of lot-sizes. Therefore, developing and improving solution procedures for lot-sizing problems is key. This dissertation addresses the classical Multi-Level Capacitated Lot-Sizing Problem (MLCLSP) and an extension of the MLCLSP with a Setup Carryover, Backlogging and Emission control. An item Dantzig Wolfe (DW) decomposition technique with an embedded Column Generation (CG) procedure is used to solve the problem. The original problem is decomposed into a master problem and a number of subproblems, which are solved using dynamic programming approach. Since the subproblems are solved independently, the solution of the subproblems often becomes infeasible for the master problem. A multi-step iterative Capacity Allocation (CA) heuristic is used to tackle this infeasibility. A Linear Programming (LP) based improvement procedure is used to refine the solutions obtained from the heuristic method. A comparative study of the proposed heuristic for the first problem (MLCLSP) is conducted and the results demonstrate that the proposed heuristic provide less optimality gap in comparison with that obtained in the literature. The Setup Carryover Assignment Problem (SCAP), which consists of determining the setup carryover plan of multiple items for a given lot-size over a finite planning horizon is modelled as a problem of finding Maximum Weighted Independent Set (MWIS) in a chain of cliques. The SCAP is formulated using a clique constraint and it is proved that the incidence matrix of the SCAP has totally unimodular structure and the LP relaxation of the proposed SCAP formulation always provides integer optimum solution. Moreover, an alternative proof that the relaxed ILP guarantees integer solution is presented in this dissertation. Thus, the SCAP and the special case of the MWIS in a chain of cliques are solvable in polynomial time.

ISBN: 9780438470569Subjects--Topical Terms:

1669109
Applied Mathematics.
Subjects--Index Terms:

Computational complexity

Lot-Sizing Problem for a Multi-Item Multi-level Capacitated Batch Production System with Setup Carryover, Emission Control and Backlogging using a Dynamic Program and Decomposition Heuristic.
LDR:04668nmm a2200385 4500 001 2348500
005 20220912135555.5
008 241004s2018 ||||||||||||||||| ||eng d
020 $a 9780438470569
035 $a (MiAaPQ)AAI10931538
035 $a (MiAaPQ)uwindsor:11863
035 $a AAI10931538
040 $a MiAaPQ $c MiAaPQ
100 1 $a Chowdhury, Nusrat Tarin. $3 3687864
245 1 0 $a Lot-Sizing Problem for a Multi-Item Multi-level Capacitated Batch Production System with Setup Carryover, Emission Control and Backlogging using a Dynamic Program and Decomposition Heuristic.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2018
300 $a 167 p.
500 $a Source: Dissertations Abstracts International, Volume: 80-04, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Baki, Mohammed Fazle;Azab, Ahmed.
502 $a Thesis (Ph.D.)--University of Windsor (Canada), 2018.
506 $a This item must not be sold to any third party vendors.
520 $a Wagner and Whitin (1958) develop an algorithm to solve the dynamic Economic Lot-Sizing Problem (ELSP), which is widely applied in inventory control, production planning, and capacity planning. The original algorithm runs in O(T 2) time, where T is the number of periods of the problem instance. Afterward few linear-time algorithms have been developed to solve the Wagner-Whitin (WW) lot-sizing problem; examples include the ELSP and equivalent Single Machine Batch-Sizing Problem (SMBSP). This dissertation revisits the algorithms for ELSPs and SMBSPs under WW cost structure, presents a new efficient linear-time algorithm, and compares the developed algorithm against comparable ones in the literature. The developed algorithm employs both lists and stacks data structure, which is completely a different approach than the rest of the algorithms for ELSPs and SMBSPs. Analysis of the developed algorithm shows that it executes fewer number of basic actions throughout the algorithm and hence it improves the CPU time by a maximum of 51.40% for ELSPs and 29.03% for SMBSPs. It can be concluded that the new algorithm is faster than existing algorithms for both ELSPs and SMBSPs. Lot-sizing decisions are crucial because these decisions help the manufacturer determine the quantity and time to produce an item with a minimum cost. The efficiency and productivity of a system is completely dependent upon the right choice of lot-sizes. Therefore, developing and improving solution procedures for lot-sizing problems is key. This dissertation addresses the classical Multi-Level Capacitated Lot-Sizing Problem (MLCLSP) and an extension of the MLCLSP with a Setup Carryover, Backlogging and Emission control. An item Dantzig Wolfe (DW) decomposition technique with an embedded Column Generation (CG) procedure is used to solve the problem. The original problem is decomposed into a master problem and a number of subproblems, which are solved using dynamic programming approach. Since the subproblems are solved independently, the solution of the subproblems often becomes infeasible for the master problem. A multi-step iterative Capacity Allocation (CA) heuristic is used to tackle this infeasibility. A Linear Programming (LP) based improvement procedure is used to refine the solutions obtained from the heuristic method. A comparative study of the proposed heuristic for the first problem (MLCLSP) is conducted and the results demonstrate that the proposed heuristic provide less optimality gap in comparison with that obtained in the literature. The Setup Carryover Assignment Problem (SCAP), which consists of determining the setup carryover plan of multiple items for a given lot-size over a finite planning horizon is modelled as a problem of finding Maximum Weighted Independent Set (MWIS) in a chain of cliques. The SCAP is formulated using a clique constraint and it is proved that the incidence matrix of the SCAP has totally unimodular structure and the LP relaxation of the proposed SCAP formulation always provides integer optimum solution. Moreover, an alternative proof that the relaxed ILP guarantees integer solution is presented in this dissertation. Thus, the SCAP and the special case of the MWIS in a chain of cliques are solvable in polynomial time.
590 $a School code: 0115.
650 4 $a Applied Mathematics. $3 1669109
650 4 $a Management. $3 516664
650 4 $a Industrial engineering. $3 526216
650 4 $a Operations research. $3 547123
653 $a Computational complexity
653 $a Dantzig-wolfe decomposition
653 $a Maximum weighted independent set
690 $a 0364
690 $a 0454
690 $a 0546
690 $a 0796
710 2 $a University of Windsor (Canada). $b Industrial and Manufacturing Systems Engineering. $3 2095462
773 0 $t Dissertations Abstracts International $g 80-04B.
790 $a 0115
791 $a Ph.D.
792 $a 2018
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10931538