Browsing by Author "Ying, Kuo-Ching"

Now showing 1 - 6 of 6

Effective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window
(2017)
Ying, Kuo-Ching
;
Linb, Shih-Wei
;
Lu, Chung-Cheng
;
運輸與物流管理系註：原交通所+運管所
;
Department of Transportation and Logistics Management
This study addresses the single-machine scheduling problem with a common due window (CDW) that has a constant size and position. The objective is to minimise the total weighted earliness-tardiness penalties for jobs completed out of the CDW. To determine a schedule as close to optimum as possible, this study develops a dynamic dispatching rule and an effective constructive heuristic. The better performance of the proposed heuristic is demonstrated by comparing the results of it with those of a state-of-the-art greedy heuristic on a well-known benchmark problem set. In addition, we incorporate the constructive heuristic into a best-so-far meta-heuristic to examine the benefit of the proposed heuristic. The results show that the best known solutions in 144 out of the 250 benchmark instances are improved.
Exact algorithms for single-machine scheduling problems with a variable maintenance
(2016-08)
Ying, Kuo-Ching
;
Lu, Chung-Cheng
;
Chen, Jhao-Cheng
;
運輸與物流管理系註：原交通所+運管所
;
Department of Transportation and Logistics Management
This paper deals with four single-machine scheduling problems (SMSPs) with a variable machine maintenance. The objectives of the four SMSPs are to minimize mean lateness, maximum tardiness, total flow time and mean tardiness, respectively. These four SMSPs are important in the literature and in practice. This study proposes an exact algorithm with the computational complexity O(n(2)) for each of the four SMSPs. In addition to the given jobs, the machine maintenance activity between two consecutive jobs is optimally scheduled. (C) 2016 Elsevier Ltd. All rights reserved.
Improved Exact Methods for Solving No-Wait Flowshop Scheduling Problems With Due Date Constraints
(2018-01-01)
Ying, Kuo-Ching
;
Lu, Chung-Cheng
;
Lin, Shih-Wei
;
運輸與物流管理系註：原交通所+運管所
;
Department of Transportation and Logistics Management
The no-wait flowshop scheduling problem with hard due date constraints is critical to operations in many industries, such as plastic, chemical, and pharmaceutical manufacturing. However, to date, there is a lack of effective optimization algorithms for this NP-hard problem. This paper develops a new mixed integer linear programming (MILP) model and a two-phase enumeration algorithm to improve the best-so-far exact methods for solving this problem with the objective of minimizing the makespan. A comprehensive computational experiment is performed to compare the performances of the discussed exact methods. The computational results demonstrate that the proposed MILP model and the two-phase enumeration algorithm significantly outperform the best-so-far optimization methods, and the (sub-) optimal solutions to several unsolved instances from the literature are reported.
Minimizing the Sum of Makespan and Total Weighted Tardiness in a No-Wait Flowshop
(2018-01-01)
Lin, Shih-Wei
;
Lu, Chung-Cheng
;
Ying, Kuo-Ching
;
運輸與物流管理系註：原交通所+運管所
;
Department of Transportation and Logistics Management
This paper presents a cloud theory-based iterated greedy (CTIG) algorithm for solving the no-wait flowshop scheduling problem (NWFSP) with the objective of minimizing the sum of makespan and total weighted tardiness. The performance of the proposed CTIG algorithm is evaluated by comparing its computational results to those of the best-to-date meta-heuristic algorithm, particle swarm optimization (PSO), as presented in this paper. The experimental results concerning two sets of benchmark problem instances in this paper demonstrate that the CTIG algorithm obtains more (near) optimal solution in less computational time than the PSO algorithm. The computational results in this paper fill the research gap in the development of a novel algorithm to improve the solution quality in the case of the NWFSP with the objective of minimizing the sum of makespan and total weighted tardiness.
Optimal Allocation of Cashiers and Pharmacists in Large Hospitals: A Point-Wise Fluid-Based Dynamic Queueing Network Approach
(2018-01-01)
Lu, Chung-Cheng
;
Lin, Shih-Wei
;
Chen, Hui-Ju
;
Ying, Kuo-Ching
;
運輸與物流管理系註：原交通所+運管所
This paper presents an optimization model for determining the optimal time-varying numbers of cashiers and pharmacists in a large hospital. The objective of this model is to minimize the weighted sum of the waiting cost incurred by patients and the operating costs incurred by the hospital. A point-wise fluid based approximation approach is adopted to construct a dynamic queuing network that takes into account time-varying (or non-stationary) arrivals of patients and describes time-varying queue lengths. The dynamic queuing network is then encapsulated in the optimization model that determines the optimal time-varying numbers of cashiers and pharmacists. A test problem instance is designed based on a large hospital in the city of Taipei, and the MINOS solver of GAMS is applied to solve the problem instance. Sensitivity analyses are also conducted to examine the impacts of customer arrival rates and service rates on the waiting cost and operational cost. Numerical results show that the optimization model can provide an optimal allocation of manpower that significantly reduces both waiting and operating costs.
Single-Machine Scheduling with Learning Effects and Maintenance: A Methodological Note on Some Polynomial-Time Solvable Cases
(2017-01-01)
Ying, Kuo-Ching
;
Lu, Chung-Cheng
;
Lin, Shih-Wei
;
Chen, Jie-Ning
;
運輸與物流管理系註：原交通所+運管所
This work addresses four single-machine scheduling problems (SMSPs) with learning effects and variable maintenance activity. The processing times of the jobs are simultaneously determined by a decreasing function of their corresponding scheduled positions and the sum of the processing times of the already processed jobs. Maintenance activity must start before a deadline and its duration increases with the starting time of the maintenance activity. This work proposes a polynomial-time algorithm for optimally solving two SMSPs to minimize the total completion time and the total tardiness with a common due date.