Browsing by Author "Hwang, F. J."

Now showing 1 - 10 of 10

Acquisition planning and scheduling of computing resources
(2016-12)
Yang, Chien-Nan
;
Lin, Bertrand M. T.
;
Hwang, F. J.
;
Wang, Meng-Chun
;
資訊管理與財務金融系註：原資管所+財金所
Cloud computing has been attracting considerable attention since the last decade. This study considers a decision problem formulated from the use of computing services over the Internet. An agent receives orders of computing tasks from his/her clients and on the other hand he/she acquires computing resources from computing service providers to fulfill the requirements of the clients. The processors are bundled as packages according to their speeds and the business strategies of the providers. The packages are rated at a certain pricing scheme to provide flexible purchasing options to the agent. The decision of the agent is to select the packages which can be acquired from the service providers and then schedule the tasks of the clients onto the processors of the acquired packages such that the total cost, including acquisition cost and scheduling cost (total weighted tardiness), is minimized. In this study, we present an integer programming model to formulate the problem and propose several solution methods to produce acquisition and scheduling plans. Ten well-known heuristics of parallel-machine scheduling are adapted to fit into the studied problem so as to provide initial solutions. Tabu search and genetic algorithm are tailored to reflect the problem nature for improving upon the initial solutions. We conduct a series of computational experiments to evaluate the effectiveness and efficiency of all the proposed algorithms. The results of the numerical experiments reveal that the proposed tabu search and genetic algorithm can attain significant improvements. (C) 2016 Elsevier Ltd. All rights reserved.
Coupled-task scheduling on a single machine subject to a fixed-job-sequence
(2011-05-01)
Hwang, F. J.
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper investigates single-machine coupled-task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed-job-sequence problem under study. While the complexity status of the studied problem remains open, an O(n(2)) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed-job-sequence constraint. We investigate several polynomially solvable cases of the fixed-job-sequence problem and present a complexity graph of the problem. (C) 2011 Elsevier Ltd. All rights reserved.
Relocation scheduling subject to fixed processing sequences
(2016-04)
Lin, Bertrand M. T.
;
Hwang, F. J.
;
Kononov, Alexander V.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in time, where and are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in time. The studied problem for the minimization of number of tardy jobs is solvable in time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where .
Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence
(2014-06-01)
Hwang, F. J.
;
Kovalyov, M. Y.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O(n(7)) time.
Survey and extensions of manufacturing models in two-stage flexible flow shops with dedicated machines
(2018-10-01)
Hwang, F. J.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This study considers the manufacturing environments in which m + 1 machines are configured as two stage flexible flow shops with dedicated machines (F2DM). The F2DM scheduling problems arise naturally from practical production and fabrication systems, and they are classified into two categories, whose machine settings are antithetical to each other. In model 1, a single common bottleneck machine is installed at stage 1 and m parallel dedicated machines comprise stage 2. The second model has the m dedicated machines at stage 1 and the bottleneck machine at stage 2. Categorizing the literature according to the performance metrics, we survey the existing research results of the two models and propose several new solution procedures with improved computational complexity. The complexity results are summarized, and suggestions are made for future research. (C) 2018 Elsevier Ltd. All rights reserved.
Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type
(2011-02-01)
Lin, Bertrand M. T.
;
Hwang, F. J.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper addresses the total completion time minimization in a two-stage differentiation flowshop where the sequences of jobs per type are predetermined. The two-stage differentiation flowshop consists of a stage-1 common machine and m stage-2 parallel dedicated machines. The goal is to determine an optimal interleaved processing sequence of all jobs at the first stage. We propose an O(m(2)Pi(m)(k=1)n(k)(m+1)) dynamic programming algorithm, where n(k) is the number of type-k jobs. The running time is polynomial when m is constant. (C) 2010 Elsevier B.V. All rights reserved.
Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence
(2012-02-01)
Hwang, F. J.
;
Kovalyov, M. Y.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper addresses scheduling n jobs in a two-machine flow shop to minimize the total completion time, subject to the condition that the jobs are processed in the same given sequence on both machines. A new concept of optimal schedule block is introduced, and polynomial time dynamic programming algorithms employing this concept are derived for two specific problems. In the first problem, the machine-2 processing time of a job is a step increasing function of its waiting time between the machines, and a decision about machine-1 idle time insertion has to be made. This problem is solved in O(n(2)) time. In the second problem, the jobs are processed in batches and each batch is preceded by a machine-dependent setup time. An O(n(5)) algorithm is developed to find an optimal batching decision. (C) 2011 Elsevier B.V. All rights reserved.
Two-machine flowshop scheduling with three-operation jobs subject to a fixed job sequence
(2017-06-01)
Lin, Bertrand M. T.
;
Hwang, F. J.
;
Gupta, Jatinder N. D.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper studies the problem of scheduling three-operation jobs in a two-machine flowshop subject to a predetermined job processing sequence. Each job has two preassigned operations, which are to be performed on their respective dedicated machines, and a flexible operation, which may be processed on either of the two machines subject to the processing order as specified. Five standard objective functions, including the makespan, the maximum lateness, the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs are considered. We show that the studied problem for either of the five considered objective functions is ordinary NP-hard, even if the processing times of the preassigned operations are zero for all jobs. A pseudo-polynomial time dynamic programming framework, coupled with brief numerical experiments, is then developed for all the addressed performance metrics with different run times.
Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence
(2012-06-01)
Hwang, F. J.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper discusses a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The two-stage assembly flowshop consists of m stage-1 parallel dedicated machines and a stage-2 assembly machine which processes the jobs in batches. Four regular performance metrics, namely, the total completion time, maximum lateness, total tardiness, and number of tardy jobs, are considered. The goal is to obtain an optimal batching decision for the predetermined job sequence at stage 2. This study presents a two-phase algorithm, which is developed by coupling a problem-transformation procedure with a dynamic program. The running time of the proposed algorithm is O(mn + n(5)), where n is the number of jobs. Journal of the Operational Research Society (2012) 63, 839-845. doi:10.1057/jors.2011.90 Published online 21 September 2011
Two-stage flexible flow shop scheduling subject to fixed job sequences
(2016-03)
Hwang, F. J.
;
Lin, Bertrand M. T.
;
交大名義發表
;
National Chiao Tung University
This paper investigates the scheduling problem in a two-stage flexible flow shop, which consists of m stage-1 parallel dedicated machines and a stage-2 bottleneck machine, subject to the condition that n(l) jobs per type l is an element of {1, ..., m} are processed in a fixed sequence. Four regular performance metrics, including the total completion time, the maximum lateness, the total tardiness, and the number of tardy jobs, are considered. For each considered objective function, we aim to determine an optimal interleaving processing sequence of all jobs coupled with their starting times on the stage-2 bottleneck machine. The problem under study is proved to be strongly NP-hard. An O(m(2)Pi(m)(l=1)n(l)(2)) dynamic programming algorithm coupled with numerical experiments is presented.