This paper presents a multi-level, multi-item, multi-period capacitated lot-sizing problem. The lot-sizing problem studies can obtain production quantities, setup decisions and inventory levels in each period fulfilli...
详细信息
This paper presents a multi-level, multi-item, multi-period capacitated lot-sizing problem. The lot-sizing problem studies can obtain production quantities, setup decisions and inventory levels in each period fulfilling the demand requirements with limited capacity resources, considering the Bill of Material (BOM) structure while simultaneously minimizing the production, inventory, and machine setup costs. The paper proposes an exact solution to Chowdhury et al. (2018)'s[1] developed model, which considers the backlogging cost, setup carryover & greenhouse gas emission control to its model complexity. The problem contemplates the Dantzig-Wolfe (D.W.) decomposition to decompose the multi-level capacitated problem into a single-item uncapacitated lot-sizing sub-problem. To avoid the infeasibilities of the weighted problem (WP), an artificial variable is introduced, and the Big-M method is employed in the D.W. decomposition to produce an always feasible master problem. In addition, Wagner & Whitin's[2] forward recursion algorithm is also incorporated in the solution approach for both end and component items to provide the minimum cost production plan. Introducing artificial variables in the D.W. decomposition method is a novel approach to solving the MLCLSP model. A better performance was achieved regarding reduced computational time (reduced by 50%) and optimality gap (reduced by 97.3%) in comparison to Chowdhury et al. (2018)'s[1] developed model.(c) 2023 The Authors. Published by ELSEVIER Ltd. This is an open access article under the CC BY-NC-ND license
We devise a projective algorithm which explicitly considers the constraint that an artificial variable be zero at the solution. Inclusion of such a constraint allows the algorithm to be applied to a (possibly infeasib...
详细信息
We devise a projective algorithm which explicitly considers the constraint that an artificial variable be zero at the solution. Inclusion of such a constraint allows the algorithm to be applied to a (possibly infeasible) standard form linear program, without the addition of any “bigM“ terms or conversion to a primal-dual problem.
An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex metho...
详细信息
An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does not introduce artificial variables. In the PBVA, a reduced linear program is formed by eliminating as many variables as there are equality constraints. A subproblem containing one 'less than or equal to' constraint is solved by executing the simplex method modified such that an upper bound is placed on an unbounded entering variable. The remaining constraints of the reduced problem are added to the optimal tableau of the subproblem to form an augmented tableau, which is solved by applying the dual simplex method for bounded variables. Lastly, the variables that were eliminated are restored by substitution. Differences between the PBVA and two other variants of the simplex method are identified. The PBVA is applied to solve an example problem with five decision variables, two equality constraints, and two inequality constraints. In addition, three other types of linear programming problems are solved to justify the advantages of the PBVA.
In the present paper, the job shop scheduling problem with no intermediate buffers, i.e. the blocking job shop scheduling problem, is investigated. Since there are no buffers between operating machines, the machines a...
详细信息
In the present paper, the job shop scheduling problem with no intermediate buffers, i.e. the blocking job shop scheduling problem, is investigated. Since there are no buffers between operating machines, the machines are blocked by the products that the machines operated until those products are passed to the products' downstream machines. Under the condition where blocking is considered, complicated calculations must be performed to evaluate semi-active schedules when a partial change of a schedule, or exchange of an operation order of jobs on a specific machine, is planned. Furthermore, because some or most of the partial changes result in infeasible schedules, it will be an advantage to know the feasibility of the changes before the time adjustments for the semi-active schedule. To deal with the feasibility problem, a new optimization problem using an artificial variable is proposed for the feasibility evaluation of a partial change of a schedule. The proposed method utilizes the mixed integer programming problem of the blocking job shop scheduling problem, with the integer variables given so that the problem becomes a simple linear programming problem solved by the simplex method. By using the information before the change of the schedule, namely the basic variables and the deformed constraints, the optimization is performed efficiently beginning at a close solution of the present evaluation. Moreover, the semi-active schedules are determined within a few steps after the evaluation, which eliminates the calculation of determining the schedule separately. To demonstrate the behavior of the proposed method, examples of calculation procedures are described in a precise manner. In addition, numerical examples are shown to verify the advantages of the proposed evaluation method.
The simplex algorithm requires artificial variables for solving linear programs which lack primal feasibility at the origin point. We present a new general purpose solution algorithm which obviates the use of artifici...
详细信息
The simplex algorithm requires artificial variables for solving linear programs which lack primal feasibility at the origin point. We present a new general purpose solution algorithm which obviates the use of artificial variables. The algorithm searches for a feasible segment of a boundary hyperplane (a face of feasible region or an intersection of several faces) by using rules similar to the ordinary simplex.
A method is provided for finding an initial regular solution of a linear programming in this paper. The key to this method is to solve an auxiliary linear programming instead of to introduce any artificial variable or...
详细信息
A method is provided for finding an initial regular solution of a linear programming in this paper. The key to this method is to solve an auxiliary linear programming instead of to introduce any artificial variable or constraint. Compared with the traditional method of achieving the regular solution by introducing an artificial constraint, it has advantages of saving the memories and little computational efforts.
暂无评论