Browsing by Author "Liu, Wan-Yu"

Now showing 1 - 20 of 27

A Cultural Algorithm for Spatial Forest Harvest Scheduling
(2014-01-01)
Liu, Wan-Yu
;
Lin, Chun-Cheng
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
This paper proposes a cultural algorithm for the spatial forest harvest scheduling for maximizing the total harvested timber volume, under the constraints of minimum harvest age, minimum adjacency green-up age, and approximately even volume flow for each period of the schedule. In order to increase the solution-search ability, the cultural algorithm extracts problem-specific information during the evolutionary solution search to update the belief space of a generation, which has cultural influences and guidance on the next generation. The key design of our cultural algorithm is to propose the cultural and evolutionary operators specifically for the problem. Experimental analysis shows that our cultural algorithm performs better than the previous approaches.
A Genetic Algorithm Approach for Detecting Hierarchical and Overlapping Community Structure in Dynamic Social Networks
(2013)
Lin, Chun-Cheng
;
Liu, Wan-Yu
;
Deng, Der-Jiunn
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
Social networks are merely a reflection of certain realities among people that have been identified. But in order for people or even computer systems (such as expert systems) to make sense of the social network, it needs to be analyzed with various methods so that the characteristics of the social network can be understood in a meaningful context. This is challenging not only due to the number of people that can be on social networks, but the changes in relationships between people on the social network over time. In this paper, we develop a method to help make sense of dynamic social networks. This is achieved by establishing a hierarchical community structure where each level represents a community partition at a specific granularity level. By organizing each level of the hierarchical community structure by granularity level, a person can essentially "zoom in" to view more detailed (smaller) communities and "zoom out" to view less detailed (larger) communities. Communities consisting of one or more subsets of people having relatively extensive links with other communities are identified and represented as overlapping community structures. Mechanisms are also in place to enable modifications to the social network to be dynamically updated on the hierarchical and overlapping community structure without recreating it in real time for every modification. The experimental results show that the genetic algorithm approach can effectively detect hierarchical and overlapping community structures.
A novel centrality-based method for visual analytics of small-world networks
(2019-10-01)
Lin, Chun-Cheng
;
Huang, Weidong
;
Liu, Wan-Yu
;
Wu, Sheng-Feng
;
工業工程與管理學系
Nowadays, the network data that we need to deal with and make sense of are becoming increasingly large and complex. Small-world networks are a type of complex networks whose underling graphs have small diameter, shorter average path length between nodes, and a high degree of clustering structures and can be found in a wide range of scientific fields, including social networks, sociology, computer science, business intelligence, and biology. However, conventional visualization algorithms for small-work networks lead to a uniform clump of nodes or are restricted to a tree structure, making the network structure difficult to identify and analyze. This work provides a new visual analytical method to improve the situation. Different from previous methods based on spanning trees, this method first generates a weighted planar sub-network based on the measurement of network centrality metrics. A force-directed algorithm based on node-edge repulsion is then applied to visualize this sub-network into a proper layout for better understanding of the data. Finally, the remaining links are placed back to maintain the original network's integrity. The experimental results show that compared to previous methods, the proposed method can be more effective in differentiating clusters and revealing relationship patterns among individual nodes and clusters in the network. Furthermore, the proposed method is applied to a data of the semiconductor wafer manufacturing industry as a case study. The work shows that this new approach allows users to gain useful insights into the data.
A Novel Joint Problem of Routing, Scheduling, and Variable-Width Channel Allocation in WMNs
(2014)
Lin, Chun-Cheng
;
Liu, Wan-Yu
;
Chou, Chun-Hung
;
Deng, Der-Jiunn
;
工業工程與管理學系
This paper investigates a novel joint problem of routing, scheduling, and channel allocation for single-radio multichannel wireless mesh networks in which multiple channel widths can be adjusted dynamically through a new software technology so that more concurrent transmissions and suppressed overlapping channel interference can be achieved. Although the previous works have studied this joint problem, their linear programming models for the problem were not incorporated with some delicate constraints. As a result, this paper first constructs a linear programming model with more practical concerns and then proposes a simulated annealing approach with a novel encoding mechanism, in which the configurations of multiple time slots are devised to characterize the dynamic transmission process. Experimental results show that our approach can find the same or similar solutions as the optimal solutions for smaller-scale problems and can efficiently find good-quality solutions for a variety of larger-scale problems.
An Approximate Dynamic Programming Model for Link Scheduling in WMNs with Gateway Design Constraint
(2014)
Chen, Chien-Liang
;
Liu, Wan-Yu
;
Chang, Shu-Huai
;
Lin, Chun-Cheng
;
工業工程與管理學系
The design objective of wireless mesh networks is generally focused on transmitting data packets as many as possible in a given time. Wireless mesh network models may be categorized into many different types according to different programming objectives, wherein the link scheduling model achieves the purpose of effective transmission of packets by certain transmission constraints and the programming of the open status of packet transmission links in each stage. In this paper, the approximate dynamic programming approach for a new wireless mesh network scheduling model having node programming information saving locations and network link gateway designs is orchestrated. The experiment results show that, in addition to maintaining many wireless network characteristics, the scheduling algorithm is effectively executed and approximate dynamic programming effectively simulates dynamic programming and has performances superior to genetic algorithm.
Applying Simulated Annealing to Joint Routing, Scheduling and Variable-Width Channel Allocation for Multi-hop WMNs
(2013)
Lin, Chun-Cheng
;
Liu, Wan-Yu
;
Chou, Chun-Hung
;
Deng, Der-Jiunn
;
工業工程與管理學系
This pager studies the joint routing, scheduling, and channel assignment problem in single-radio multi-channel WMNs. All the three subproblems are related to the packet transmission rate: the routing problem is to find the transmission paths for packets; the scheduling problem is to plan the transmission order of packets; the channel assignment problem is related to signal interference and synchronization. The joint problem has been studied in the past, but they can only solve small-scale problems and did not consider the effect of signal interference, so that their methods are not efficient and do not meet the practical scenario. With regards to this, we propose a simulated annealing approach with a new coding scheme that divides time into a number of time slots to model the dynamic process of packets. In addition, this paper demonstrates a variable-bandwidth channel allocation method that achieves a good balance between higher synchronization and better control of interference. Experimental results show that our proposed simulated annealing approach can find the same or similar solutions with the exact methods for the cases with a small number of nodes and low traffic load.
Considering Multiple Factors to Forecast CO2 Emissions: A Hybrid Multivariable Grey Forecasting and Genetic Programming Approach
(2018-12-01)
Lin, Chun-Cheng
;
He, Rou-Xuan
;
Liu, Wan-Yu
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
Development of technology and economy is often accompanied by surging usage of fossil fuels. Global warming could speed up air pollution and cause floods and droughts, not only affecting the safety of human beings, but also causing drastic economic changes. Therefore, the trend of carbon dioxide emissions and the factors affecting growth of emissions have drawn a lot of attention in all countries in the world. Related studies have investigated many factors that affect carbon emissions such as fuel consumption, transport emissions, and national population. However, most of previous studies on forecasting carbon emissions hardly considered more than two factors. In addition, conventional statistical methods of forecasting carbon emissions usually require some assumptions and limitations such as normal distribution and large dataset. Consequently, this study proposes a two-stage forecasting approach consisting of multivariable grey forecasting model and genetic programming. The multivariable grey forecasting model at the first stage enjoys the advantage of introducing multiple factors into the forecasting model, and can accurately make prediction with only four or more samples. However, grey forecasting may perform worse when the data is nonlinear. To overcome this problem, the second stage is to adopt genetic programming to establish the error correction model to reduce the prediction error. To evaluating performance of the proposed approach, the carbon dioxide emissions in Taiwan from 2000 to 2015 are forecasted and analyzed. Experimental comparison on various combinations of multiple factors shows that the proposed forecasting approach has higher accuracy than previous approaches.
Considering stockers in reentrant hybrid flow shop scheduling with limited buffer capacity
(2020-01-01)
Lin, Chun-Cheng
;
Liu, Wan-Yu
;
Chen, Yu-Hsiang
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
Diversification of products has increased the involvement of reentrant manufacturing processes, in which a job returns multiple times to a machine at the preceding workflow stage to continue the manufacturing process. Reentrant flow shop manufacturing can substantially improve manufacturing efficiency when scheduled properly. In practice, advanced manufacturing companies (e.g., semiconductor foundries) have introduced automated material handling system (AMHS), including stockers that serve as centralized inventory buffer space for temporarily storing the inventories owing to limited buffer capacity of each machine. However, no previous studies on reentrant flow shop scheduling have considered the impact of limited buffer capacity or stockers on scheduling efficiency. Consequently, this study investigated the application of stockers in solving the reentrant hybrid flow shop scheduling problem with limited buffer capacity. With the objective of optimizing the makespan and mean flowtime of a schedule, this problem is NP-hard because it generalizes the flow shop problem. Therefore, this study developed a hybrid harmony search and genetic algorithm (HHSGA) for the problem, in which limited buffer capacity and stockers cause solution decoding to be non-trivial. Experimental comparison on scheduling problems with different numbers of jobs showed that the HHSGA performed better than conventional algorithms. Moreover, among three manufacturing conditions (i.e., with buffers and stockers, with buffers only, and with stockers only), the results indicated that the condition using inventory buffers and stockers was more beneficial.
Evaluating aesthetics for user-sketched layouts of symmetric graphs
(2018-10-01)
Lin, Chun-Cheng
;
Huang, Weidong
;
Liu, Wan-Yu
;
Chen, Wen-Lin
;
工業工程與管理學系
In evaluating aesthetics of graph drawings, recent works have provided participants with an adjacency list of a graph and asked them to sketch a pleasing layout of the graph. However, this line of research has not considered aesthetics for user-sketched layouts of graphs with symmetries, which are an important property of a given graph drawing. Therefore, the work reported in this paper focuses on empirically evaluating aesthetics for user-sketched layouts of symmetric graphs. We provided participants adjacency lists of two symmetric graphs and asked them to sketch the two graphs. We analyzed whether symmetries were shown in user-sketched drawings, and further analyzed the aesthetics based on their drawing processes and drawing preferences. In addition, our experiment includes multiple stages to analyze whether the participants had the potential learning ability to draw symmetric structures of graphs. We found that in drawing symmetrical graphs, showing symmetry was likely considered more important than minimizing edge crossings, and that most participants made substantial progress in their ability to create symmetric drawings after going through the experimental stages.
Evaluating esthetics for user-sketched layouts of clustered graphs with known clustering information
(2016-12)
Lin, Chun-Cheng
;
Huang, Weidong
;
Liu, Wan-Yu
;
Tanizar, Shierly
;
Jhong, Shun-Yu
This paper aims to empirically analyze the esthetics for user-sketched layouts of clustered graphs with known clustering information. In our experiments, given not only the adjacency list of a clustered graph but also its predefined clustering information, each participant was asked to manually sketch clustered graphs "nicely" from scratch on a tablet system using a stylus. Different from previous works, the main concern in this paper is on which graph drawing esthetics people favor when sketching their own drawings of clustered graphs with known clustering information. Another concern of this paper is on the esthetics of clustered graph layouts employed by participants which include not only characteristics and structures of the final graph layouts but also the behavior of user\'s sketching process (including layout creation and adjustment). By observing all layouts and drawing processes, the drawing strategies which participants applied and the drawing esthetics are analyzed. Results show that most participants were unsurprisingly able to draw graphs with clear presence of bridge edges and clustering cohesiveness; more importantly, to distinguish clusters within the restricted-size tablet screen during the drawing process, some of the participants were still able to make each cluster with fewer edge crossings, more symmetries, and more alignment of grid in a smaller drawing area where the cluster spreads. Our results support that to alleviate user\'s complex drawing tasks, aside from the grid-based editing function suggested by the previous work, graph drawing systems should also provide the clustering information if the structure of the graph to be drawn is known.
Forecasting value of agricultural imports using a novel two-stage hybrid model
(2014-06-01)
Lee, Yi-Shian
;
Liu, Wan-Yu
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
Agricultural imports are becoming increasingly important in terms of their impact on economic development. An accurate model must be developed for forecasting the value of agricultural imports since rapid changes in industry and economic policy affect the value of agricultural imports. Conventionally, the ARIMA model has been utilized to forecast the value of agricultural imports, but it generally requires a large sample size and several statistical assumptions. Some studies have applied nonlinear methods such as the GM(1,1) and improved GM(1,1) models, yet neglected the importance of enhancing the accuracy of residual signs and residual series. Therefore, this study develops a novel two-stage forecasting model that combines the GM(1,1) model with genetic programming to accurately forecast the value of agricultural imports. Moreover, accuracy of the proposed model is demonstrated based on two agricultural imports data sets from the Taiwan and USA. (C) 2014 Elsevier B.V. All rights reserved.
Forest biomass-to-biofuel factory location problem with multiple objectives considering environmental uncertainties and social enterprises
(2020-07-20)
Lin, Chun-Cheng
;
Kang, Jia-Rong
;
Huang, Guan-Lin
;
Liu, Wan-Yu
;
工業工程與管理學系
Forest biomass energy enjoys merit of large production, renewability, and clean combustion. However, most related works focused on only the objective of minimization of cost or pollution, but seldom on the social aspect. Social enterprise provides business models that cope with social or environmental problems, e.g., offering employment opportunities in disadvantaged areas. Therefore, this work considers social enterprises and environmental uncertainties in a forest biomass-to-biofuel factory location problem with multiple objectives, which determines whether to open forest biomass-to-biofuel factories at their potential locations to meet the energy demand and other practical constraints. Aside from minimization of cost and carbon emissions, the concerned problem additionally considers the objective of maximizing the job offers provided by opening factories from the social enterprise aspect. Additionally, based on the fuzzy theory, this problem includes the following environmental uncertainties: uncertain number of inventory days, uncertain job offers per unit of surplus factory scale, uncertain biomass production amount, and uncertain biofuel demand due to the price fluctuation of fossil fuels. This work employs the GIS to determine candidate locations of acquiring forest biomass and opening factories, and then solves the problem by fuzzy multi-objective linear programming. Through simulation, we observe the conflict among objectives, compare the differences between the proposed method and previous methods, and analyze the key factors that affect practical implementation. Simulation results show that when the total biofuel demand exceeds 200 million liters per year, the proposed method provides 16% more job offers than the previous method that focused on only cost minimization. (c) 2020 Elsevier Ltd. All rights reserved.
Fuzzy Multi-objective Forest Biomass-to-biofuel Facility Location Problem with Social Consideration
(2019-01-01)
Lin, Chun-Cheng
;
Liu, Wan-Yu
;
Huang, Guan-Lin
;
交大名義發表
;
工業工程與管理學系
This study proposes a novel multiple-objective forest biomass-to-biofuel facility location problem with social consideration and uncertainties, which determines locations of forest biomass-to-biofuel facilities so as to satisfy the energy demand, while the scale of facilities is limited. Aside from the two objectives (i e, minimizing cost and pollution) that were often discussed in previous problems, the problem in this study additionally considers an objective from the social aspect, i.e., maximizing the job opportunity by opening facilities. Furthermore, many uncertain factors may affect the number of days of operating biomass energy facilities as well as biomass production; the demand of biomass energy is uncertain with the unstable price of fossil fuels; and the number of job offers is uncertain. Therefore, we adopt fuzzy theory to add environmental uncertainties in the problem. To solve this problem, we employ the geographic information system to obtain candidate locations of facilities and biomass, and then use fuzzy multiple objective linear programming to solve the problem. From experimental results, the conflict between objectives can be observed. (C) 2019 The Authors. Published by Elsevier Ltd.
Jointly rostering, routing, and rerostering for home health care services: A harmony search approach with genetic, saturation, inheritance, and immigrant schemes
(2018-01-01)
Lin, Chun-Cheng
;
Hung, Lun-Ping
;
Liu, Wan-Yu
;
Tsai, Ming-Chun
;
工業工程與管理學系
In home health care (HHC) services, nurses or professional caregivers are dispatched to patients' homes to provide medical care services, such that each patient can stay at home to be treated periodically. The HHC problem consists of the nurse rostering problem (NRP) and the vehicle routing problem with time windows (VRPTW), both of which are NP-hard problems, which are harder or equal to the hardest problem in the NP (nondeterministic polynomial time) problem class and generally cannot be solved efficiently. To the best of our knowledge, the previous algorithmic approaches were designed to separately address NRP and VRPTW of the HHC problem. However, NRP and VRPTW of the HHC problem are intercorrelated, and their respective optimal objectives may be in conflict with each other in many cases. Additionally, the problem generally involves too many constraints to be solved, and most previous works did not address occurrence of sudden incidents in HHC services (e.g., a nurse or a patient suddenly requests for a leave, and a patient suddenly changes the time slot to be treated) such that the original nurse roster could become infeasible. Under constraints of nurse qualifications, working laws, nurse preferences, and vehicle routing, the first model considers nurse rostering and vehicle routing concurrently to minimize total costs of nurse overtime and vehicle routing. The second model extends the first model with rerostering caused by occurrence of sudden incidents. Harmony search algorithm (HSA) has been shown to perform better in solving NRPs than conventional metaheuristics, and hence this work proposes an improved HSA with genetic and saturation schemes, in which the solution representation is designed to concurrently determine nurse rostering and vehicle routing. For the second rerostering model, inheritance and immigrant schemes are added to the HSA to adapt to the change caused by occurrence of sudden incidents. Experimental results show that the proposed HSA performs well and can adapt to the change caused by sudden incidents.
Minimizing the Carbon Footprint for the Time-Dependent Heterogeneous-Fleet Vehicle Routing Problem with Alternative Paths
(2014-07-01)
Liu, Wan-Yu
;
Lin, Chun-Cheng
;
Chiu, Ching-Ren
;
Tsao, You-Song
;
Wang, Qunwei
Torespondto the reduction of greenhouse gas emissions and global warming, this paper investigates the minimal-carbon-footprint time-dependent heterogeneous-fleet vehicle routing problem with alternative paths (MTHVRPP). This finds a route with the smallestcarbon footprint, instead of the shortestroute distance, which is the conventional approach, to serve a number of customers with a heterogeneous fleet of vehicles in cases wherethere may not be only one path between each pair of customers, and the vehicle speed differs at different times of the day. Inheriting from the NP-hardness of the vehicle routing problem, the MTHVRPP is also NP-hard. This paper further proposes a genetic algorithm (GA) to solve this problem. The solution representedbyour GA determines the customer serving ordering of each vehicle type. Then, the capacity check is used to classify multiple routes of each vehicle type, and the path selection determines the detailed paths of each route. Additionally, this paper improves the energy consumption model used for calculating the carbon footprint amount more precisely. Compared with the results without alternative paths, our experimental results show that the alternative path in this experimenthas a significant impact on the experimental results in terms of carbon footprint.
Minimizing the Carbon Footprint for the Time-Dependent Heterogeneous-Fleet Vehicle Routing Problem with Alternative Paths
(2014-07-01)
Liu, Wan-Yu
;
Lin, Chun-Cheng
;
Chiu, Ching-Ren
;
Tsao, You-Song
;
Wang, Qunwei
Torespondto the reduction of greenhouse gas emissions and global warming, this paper investigates the minimal-carbon-footprint time-dependent heterogeneous-fleet vehicle routing problem with alternative paths (MTHVRPP). This finds a route with the smallestcarbon footprint, instead of the shortestroute distance, which is the conventional approach, to serve a number of customers with a heterogeneous fleet of vehicles in cases wherethere may not be only one path between each pair of customers, and the vehicle speed differs at different times of the day. Inheriting from the NP-hardness of the vehicle routing problem, the MTHVRPP is also NP-hard. This paper further proposes a genetic algorithm (GA) to solve this problem. The solution representedbyour GA determines the customer serving ordering of each vehicle type. Then, the capacity check is used to classify multiple routes of each vehicle type, and the path selection determines the detailed paths of each route. Additionally, this paper improves the energy consumption model used for calculating the carbon footprint amount more precisely. Compared with the results without alternative paths, our experimental results show that the alternative path in this experimenthas a significant impact on the experimental results in terms of carbon footprint.
Modeling the Master Production Scheduling System with Downgraded Products for a TFT-LCD Module Factory
(2012-01-01)
Lin, Chun-Cheng
;
Kang, Jia-Rong
;
Liu, Wan-Yu
;
Chung, Shu-Hsing
;
Chou, Kai-Shin
At the end processes of TFT-LCD supply chain, the LCM module factory takes charge of the process of assembling products, and its production planning needs to consider various products with different graded TFT-LCD panels while meeting customers\' specific qualifications, including lowest acceptance rates for quality and zero-bad-defect quantity. Since the machine setup time of the bottleneck workstation in the factory is very long, it is of practical importance to design an appropriate production scheduling with concerns about times of machine setups and different grades of TFT-LCD products. This paper proposes a production scheduling system that comprises the material planning with downgraded products as well as the bottleneck scheduling for a LCM module factory using make-to-stock production, and solves the system based on integer programming. Experimental results show that the system not only is capable of reducing the number of setup times, but also performs well in efficiency of preparing critical materials. From a practical aspect, such a system can support production managers to plan their production scheduling effectively.
Modelling a Nurse Shift Schedule with Multiple Preference Ranks for Shifts and Days-Off
(2014)
Lin, Chun-Cheng
;
Kang, Jia-Rong
;
Liu, Wan-Yu
;
Deng, Der-Jiunn
;
工業工程與管理學系
When it comes to nurse shift schedules, it is found that the nursing staff have diverse preferences about shift rotations and days-off. The previous studies only focused on the most preferred work shift and the number of satisfactory days-off of the schedule at the current schedule period but had few discussions on the previous schedule periods and other preference levels for shifts and days-off, which may affect fairness of shift schedules. As a result, this paper proposes a nurse scheduling model based upon integer programming that takes into account constraints of the schedule, different preference ranks towards each shift, and the historical data of previous schedule periods to maximize the satisfaction of all the nursing staff's preferences about the shift schedule. The main contribution of the proposed model is that we consider that the nursing staff's satisfaction level is affected by multiple preference ranks and their priority ordering to be scheduled, so that the quality of the generated shift schedule is more reasonable. Numerical results show that the planned shifts and days-off are fair and successfully meet the preferences of all the nursing staff.
Modelling the spatial forest-thinning planning problem considering carbon sequestration and emissions
(2017-05-01)
Liu, Wan-Yu
;
Lin, Chun-Cheng
;
Su, Ke-Hong
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
Appropriate forest thinning is beneficial for growing forests and protecting ecological environments. To determine a beneficial approach in both economic and environmental aspects, carbon sequestration and emissions caused by forest-thinning activities can be traded. However, previous research on forest planning has not considered a detailed and sophisticated calculation for forest thinning and carbon sequestration. Hence, this study proposes a spatial forest-thinning planning problem involving carbon sequestration and emissions, which determine forest-thinning schedules over a planning period so that the total thinned timber volume over the period and the revenue from carbon sequestration and emissions can be maximized under certain spatial constraints. For this research, we first created a novel mathematical programming model, which can generally solve only small-scale problems. Therefore, this study also proposes an improved simulated annealing heuristic approach (ISA), which iteratively searches for a near optimal solution with two improved designs: a spatial local search operator and a neighborhood search scheme. The simulation results obtained using 300 forestland instances revealed that the proposed ISA can achieve better results through the proposed spatial local search operator, and run more efficiently through the proposed neighborhood search scheme. In addition, the decision regarding carbon sequestration and emissions was verified to be clearly advantageous for the cycling and sustainability of forest resources. (C) 2017 Elsevier B.V. All rights reserved.
On Clustered Graph Layouts Sketched by Users Based on Predefined Clusters
(2015)
Lin, Chun-Cheng
;
Huang, Weidong
;
Liu, Wan-Yu
;
Tanizar, Shierly
;
工業工程與管理學系
The aesthetics for user-sketched layouts of clustered graphs with known clustering information is analyzed empirically. In our experiments, given the adjacency list of a clustered graph and its predefined clustering information, each participant was asked to manually sketch clustered graphs "nicely" from scratch on a tablet system using a stylus. The main feature of this work different from the previous work is to investigate if the user\'s complex task of sketching clustered graphs "nicely" can be alleviated by providing the cluster partition information. Results show that most participants can draw graphs with clear presence of bridge edges and clustering cohesiveness.