Browsing by Author "Lin, BMT"

Now showing 1 - 10 of 10

A simple lower bound for total completion time minimization in a two-machine flowshop
(2005-09-01)
Lin, BMT
;
Wu, JM
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
The purpose of this study is to present a simple lower bound to facilitate the development of branch-and-bound algorithms for the minimization of total completion time in a two-machine flowshop. The studied problem is known to be strongly NP-hard. In the literature, several lower bounds have been proposed. The bounding technique addressed in this paper is based upon a concept about rearrangement of the parameters of the input instance. The technique is intrinsically simple for computer implementations. We conduct computational experiments for problems with 10-65 jobs. Numerical results from our computational study indicate that the new scheme is very effective in reducing the execution time needed for composing optimal solutions.
An effective approach for test-sheet composition with large-scale item banks
(2006-02-01)
Hwang, GJ
;
Lin, BMT
;
Lin, TL
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
A well-constructed test sheet not only helps the instructor evaluate the learning status of the students, but also facilitates the diagnosis of the problems embedded in the students' learning process. This paper addresses the problem of selecting proper test items to compose a test sheet that conforms to such assessment requirements as average difficulty degree, average discrimination degree, length of test time, number of test items, and specified distribution of concept weights. A mixed integer programming model is proposed to formulate the problem of selecting a set of test items that best fit the multiple assessment requirements. As the problem is a generalization of the knapsack problem, which is known to be Xg-hard in the literature, computational challenge hinders the development of efficient solution methods. Seeking approximate solutions in an acceptable time is a viable alternative. In this paper, we propose two heuristic algorithms, based upon iterative adjustment, for finding quality approximate solutions. Extensive experiments are also conducted to assess the performances of different solution methods. Statistics from a series of computational experiments indicate that our proposed algorithms can produce near-optimum combinations of the test items subject to the specified requirements in a reasonable time. (c) 2004 Elsevier Ltd. All rights reserved.
Ant colony optimization for the cell assignment problem in PCS networks
(2006-06-01)
Shyu, SYJ
;
Lin, BMT
;
Hsiao, TS
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Even though significant improvement to communications infrastructure has been attained in the personal communication service industry, the issues concerning the assignment of cells to switches in order to minimize the cabling and handoff costs in a reasonable time remain challenging and need to be solved. In this paper, we propose an algorithm based upon the Ant Colony Optimization (ACO) approach to solve the cell assignment problem, which is known to be NP-hard. ACO is a metaheuristic inspired by the foraging behavior of ant colonies. We model the cell assignment problem as a form of matching problem in a weighted directed bipartite graph so that our artificial ants can construct paths that correspond to feasible solutions on the graph. We explore and analyze the behavior of the ants by examining the computational results of our ACO algorithm under different parameter settings. The performances of the ACO algorithm and several heuristics and metaheuristics known in the literature are also empirically studied. Experimental results demonstrate that the proposed ACO algorithm is an effective and competitive approach in composing fairly satisfactory results with respect to solution quality and execution time for the cell assignment problem as compared with most existing heuristics or metaheuristics. (c) 2005 Elsevier Ltd. All rights reserved.
Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time
(2004-11-01)
Shyu, SJ
;
Lin, BMT
;
Yin, PY
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Ant colony optimization (ACO) is a meta-heuristic proposed to derive approximate solutions for computationally hard problems by emulating the natural behaviors of ants. In the literature, several successful applications have been reported for graph-based optimization problems, such as vehicle routing problems and traveling salesman problems. In this paper, we propose an application of the ACO to a two-machine flowshop scheduling problem. In the flowshop, no intermediate storage is available between two machines and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time. We first present a transformation of the scheduling problem into a graph-based model. An ACO algorithm is then developed with several specific features incorporated. A series of computational experiments is conducted by comparing our algorithm with previous heuristic algorithms. Numerical results evince that the ACO algorithm exhibits impressive performances with small error ratios. The results in the meantime demonstrate the success of ACO's applications to the scheduling problem of interest. (C) 2004 Elsevier Ltd. All rights reserved.
Bicriteria scheduling in a two-machine permutation flowshop
(2006-06-15)
Lin, BMT
;
Wu, JM
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
In this paper we consider a production scheduling problem in a two-machine flowshop. The bicriteria objective is a linear combination or weighted sum of the makespan and total completion time. This problem is computationally hard because the special case concerning the minimization of the total completion time is already known to be strongly NP-hard. To find an optimal schedule, we deploy the Johnson algorithm and a lower bound scheme that was previously developed for total completion time scheduling. Computational experiments are presented to study the relative performance of different lower bounds. While the best known bound for the bicriteria problem can successfully solve test cases of 10 jobs within a time limit of 30 min, under the same setting our branch-and-bound algorithm solely equipped with the new scheme can produce optimal schedules for most instances with 30 or less jobs. The results demonstrate the convincing capability of the lower bound scheme in curtailing unnecessary branching during problem-solving sessions. The computational experience also suggests the practical significance and potential implications of this scheme.
Dynamic multicast routing under delay constraints in WDM networks with heterogeneous light splitting capabilities
(2006-05-31)
Chen, MT
;
Tseng, SS
;
Lin, BMT
;
資訊工程學系
;
資訊管理與財務金融系註：原資管所+財金所
Because optical WDM networks will be realized as network backbone in the near future, multicasting in WDM networks needs to be supported for various network applications. In this paper, we propose a new dynamic multicast routing problem under delay constraints (DMR-DC) for finding an optimal light-forest with the minimum multicast cost from these links with available wavelengths for routing a multicast request that arrives in random with a given delay bound in a WDM network with heterogeneous light splitting capabilities, where a light-forest is a set of light-trees used to set up switches to route the request. Multicast cost is defined by communication cost ratio and wavelength consumption ratio. The problem is to determine a light-forest with less wavelength consumption and less communication cost. This problem is NP-hard because it can be reduced from the minimum Steiner tree problem. In this paper, we propose an efficient three-phase (generation, refinement, and conversion) solution model to find approximate solutions in a reasonable time. (C) 2005 Elsevier B.V. All rights reserved.
On the development of a computer-assisted testing system with genetic test sheet-generating approach
(2005-11-01)
Hwang, GJ
;
Lin, BMT
;
Tseng, HH
;
Lin, TL
;
資訊管理與財務金融系註：原資管所+財金所
Since the last decade, computer-assisted testing has proven to be an efficient and effective way to evaluating students' learning status such that proper tutoring strategies can be adopted to improve-their learning performance. A good test will not only help the instructor evaluate the learning status of the students, but also facilitate the diagnosis of the problems embedded in the students' learning process. One of the most important and challenging issues in conducting a good test is the construction of test sheets that can meet various assessment requirements. A previous study has indicated that selecting test items to best fit multiple assessment requirements can be formulated as a mixed integer programming model. The problem is known to be NP-hard in the literature and, hence, computational challenges hinder the development of efficient solution methods. As a sequel, we instead seek quality approximate solutions in a reasonable time. Two approximation methods based upon a genetic approach are developed. Statistics from a series of computational experiments indicate that our approach is able to efficiently generate near-optimal combinations of test items that satisfy the specified requirements or constraints.
On the relocation problem with a second working crew for resource recycling
(2006-01-15)
Lin, BMT
;
Huang, HL
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
In this paper, we introduce a variant of the relocation problem, which was formulated from a public house redevelopment project in Boston. In the problem of interest, given some initial resources in a common pool there is a set of jobs to be processed on a two-machine flowshop. Each job acquires a specific number of resources to start its processing and will return a number of resources to the pool at its completion. The resource consumption and resource recycle processes are performed on machine one and machine two, respectively, in a two-machine flowshop style. Abiding by the resource constraints, the problem seeks to find a feasible schedule whose makespan is minimized. In this paper, we first present NP-hardness proofs for some special cases. Three heuristic algorithms are designed to compose approximate schedules. Two lower bounds are developed and then used to test the performance of our proposed heuristics. Numerical results from computational experiments suggest that the proposed heuristics can produce quality solutions in a reasonable time.
Two-machine flow-shop scheduling to minimize total late work
(2006-06-01)
Lin, BMT
;
Lin, FC
;
Lee, RCT
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This article considers a two-machine flow-shop scheduling problem of minimizing total late work. Unlike tardiness, which is based upon the difference between the job completion time and the due date, the late work of a job is defined as the amount of work not completed by its due date. This article first shows that the problem remains non-deterministic polynomial time (NP) hard even if all jobs share a common due date. A lower bound and a dominance property are developed to design branch-and-bound algorithms. Computational experiments are conducted to assess the performance of the proposed algorithms. Numerical results demonstrate that the lower bound and dominance rule can help to reduce the computational efforts required by exploring the enumeration tree. The average deviation between the solution found by tabu search and the proposed lower bound is less than 3%, suggesting that the proposed lower bound is close to the optimal solution.
Two-machine flowshop batching and scheduling
(2005-01-01)
Lin, BMT
;
Cheng, TCE
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution.