Browsing by Author "Lin, B. M. T."

Now showing 1 - 20 of 20

A note on parallel-machine scheduling with deteriorating jobs
(2007-06-01)
Jeng, A. A. K.
;
Lin, B. M. T.
;
資訊工程學系
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Computer Science
We consider a parallel-machine scheduling problem of minimizing the total completion time. The processing time of a job is a linear function of its starting time and deterioration rate. This problem is known to be NP-hard, even for the case with two machines. In this note, we generalize an existing lower bound for the two-machine case to the general case with an arbitrary number of machines. Despite the generalization concerning machine number, our bound has one extra term that makes our bound tighter than the existing one.
A scheduling model for the refurbishing process in recycling management
(2013-11-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
Tian, Y.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
We propose from the perspective of operations scheduling a novel model of the refurbishing process in recycling management. We model the refurbishing process as a two-stage flowshop that dismantles products into parts in stage one and refurbishes the parts on dedicated machines in stage two. The model also features that the performance measure of a schedule is defined by operation-based completion times, which is different from the job-based performance measures traditionally adopted in the scheduling literature. We analyse the optimality properties and computational complexity of some special cases of the problem. We derive lower bounds on the optimal solution based on a disaggregation technique and the assignment problem, and develop dominance rules incorporating estimates of the effects of partial schedules on unscheduled jobs. We present a heuristic approach, based on LP relaxation, and analyse its performance ratio. We also develop two metaheuristic algorithms, based on iterated local search and ant colony optimisation, to produce approximate solutions. The results of computational experiments show that the metaheuristics generate better solutions than the simple weighted shortest processing time dispatching rule, and the NEH-based and CDS-based algorithms, which are commonly deployed to treat the classical two-machine flowshop scheduling problem.
Complexity results for single-machine scheduling with positional learning effects
(2007-08-01)
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This note presents complexity results for a single-machine scheduling problem of minimizing the number of late jobs. In the studied problem, the processing times of the jobs are defined by positional learning effects. A recent paper proposed a polynomial time algorithm for the case with a common due date and conjectured the general problem to be NP-hard. We confirm that the general problem is strongly NP-hard and show that the studied problem remains NP-hard even if there are only two different due-date values.
Customer order scheduling to minimize the number of late jobs
(2007-12-01)
Lin, B. M. T.
;
Kononov, A. V.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date. (c) 2006 Elsevier B.V. All rights reserved.
Demonstrating Johnson's algorithm via resource-constrained scheduling
(2017-01-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
The celebrated Johnson's algorithm to solve the two-machine flowshop scheduling problem to minimise the makespan plays a prominent role in scheduling research. In using resource-constrained scheduling to interpret Johnson's algorithm in teaching scheduling theory and operations management, we have received positive student feedback on the perceived intuition. We demonstrate this idea and show that the resource-constrained scheduling concept also helps simplify the proofs of some classical scheduling results.
Development of new features of ant colony optimization for flowshop scheduling
(2008-04-01)
Lin, B. M. T.
;
Lu, C. Y.
;
Shyu, S. J.
;
Tsai, C. Y.
;
資訊管理與財務金融系註：原資管所+財金所
Ant colony optimization (ACO) is a meta-heuristic based on the indirect communication of a colony of artificial ants mediated by pheromone trails with the collaboration and knowledge-sharing mechanism during their food-seeking process. In this study, we introduce two new features that are inspired from real ant behavior to develop a new ACO algorithm to produce better solutions. The proposed ACO algorithm is applied to two NP-hard flowshop scheduling problems. The first problem is to minimize the total completion time and the second is to minimize a combination of makespan and total completion time. Numerical results indicate that the proposed new features of ACO are very effective and the synergy of combining all the new features for the proposed ACO algorithm can solve the two problems to a certain scale by producing schedules of better quality. (C) 2007 Elsevier B.V. All rights reserved.
Johnson's rule, composite jobs and the relocation problem
(2009-02-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Two-machine flowshop scheduling to minimize makespan is one of the most well-known classical scheduling problems. Johnson's rule for solving this problem has been widely cited in the literature. We introduce in this paper the concept of composite job, which is an artificially constructed job with processing times such that it will incur the same amount of idle time oil the second machine as that incurred by a chain of jobs in a given processing sequence. This concept due to Kurisu first appeared in 1976 to deal with the two-machine flowshop scheduling problem involving precedence constraints among the jobs. We show that this concept can be applied to reduce the computational time to solve some related scheduling problems. We also establish a link between solving the two-machine flowshop makespan minimization problem using Johnson's rule and the relocation problem introduced by Kaplan. We present an intuitive interpretation of Johnson's rule in the context of the relocation problem. (c) 2007 Elsevier B.V. All rights reserved.
Maximizing the reward in the relocation problem with generalized due dates
(2008-09-01)
Lin, B. M. T.
;
Liu, S. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
The relocation problem, based on a public housing project in Boston, USA, is a generalized resource-constrained scheduling problem in which the amount of resources (new housing units) returned by a completed job (building) is not necessarily the same as the amount of resources (original housing units) it started out with for processing. In this paper we consider a variant where several generalized due dates are specified to define the number of new housing units that should be built in the entire duration of the project. Generalized due dates are different from conventional due dates in that they are job independent and common to all jobs. In the present study each generalized due date is given to specify an expected percentage of completion of the project. Given an initial number of temporary housing units, the goal is to find a feasible reconstruction sequence that maximizes the total reward over all generalized due dates. This paper investigates the time complexity of the problem. Two upper bounds and a dominance property are proposed for the design of branch-and-bound algorithms. Computational experiments are carried out to assess the efficiency of the proposed properties. The results show that the proposed properties can significantly reduce the time required for producing an optimal schedule. (c) 2008 Elsevier B.V. All rights reserved.
Minimizing machine assignment costs over Delta-approximate solutions of the scheduling problem P parallel to C-max
(2019-11-12)
Kononov, A. V.
;
Kovalyov, M. Y.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Bi-criteria lexicographical minimization problems with the makespan as the primary objective and the total machine assignment costs as the secondary objective have been recently introduced to the scheduling research, and polynomial time (r + 1, 1)-approximation algorithms have been suggested for their solution, where 1 < r < 2 is the performance ratio of an approximation algorithm for P parallel to C-max. We improve these results by presenting a polynomial time (1.5r - 1, 1)-approximation algorithm for the additive cost type. Then, we introduce a problem of minimizing the total machine assignment cost over the Delta-approximate solutions of the makespan minimization problem. We prove that this new problem is strongly NP-hard and pseudo-polynomially non-approximable in general. A polynomial time approximation algorithm with a guaranteed approximation ratio is presented for the additive cost type and bounded ratio between the maximal and minimal machine costs. An O (mn(2k)) time dynamic programming algorithm is also presented, where k is the fixed number of distinct job processing times. (C) 2019 Elsevier B.V. All rights reserved.
Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities
(2008-01-01)
Chen, Ming-Tsung
;
Lin, B. M. T.
;
Tseng, Shian-Shyong
;
資訊工程學系
;
資訊管理與財務金融系註：原資管所+財金所
Because optical wavelength division multiplexing (WDM) networks are expected to be realized for building up backbone in the near future, multicasting in WDM networks needs to be addressed for various network applications. This paper studies an extended multicast routing and wavelength assignment (RWA) problem called multicast routing and wavelength assignment with delay constraint (MRWA-DC) that incorporates delay constraints in WDM networks having heterogeneous light splitting capabilities. The objective is to find a light-forest whose multicast cost, defined as a weighted combination of communication cost and wavelength consumption, is minimum. An integer linear programming (ILP) model is proposed to formulate and solve the problem. Experimental results show that using CPLEX to solve the ILP formulation can optimally deal with small-scale networks. Therefore, we develop a heuristic, near-k-shortest-path heuristic (NKSPH), to solve the problem in large-scale networks. Numerical results indicate that the proposed heuristic algorithm can produce approximate solutions of good quality in an acceptable time. (C) 2006 Elsevier Ltd. All rights reserved.
On relocation problems with multiple identical working crews
(2006-12-01)
Kononov, A. V.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
The relocation problem was formulated from a public housing project. In its basic form, a set of buildings needed to be torn down and erected by a single working crew. Given a fixed budget, the relocation problem seeks to determine a feasible reconstruction sequence of the old buildings. This problem has been shown to be mathematically equivalent to the classical two-machine flowshop of makespan minimization. In this paper, we consider a variant where multiple working crews are available for the redevelopment project. Most of our results center on the situations where all buildings require the same redevelopment time. We first present a strong NP-hardness proof for the case with two working crews. Then, we give a negative result about the approximability of the studied problem. Approximation algorithms and associated performance-ratio analysis are designed for the cases with unbounded as well as bounded numbers of machines. (c) 2006 Elsevier B.V. All rights reserved.
Resource-constrained flowshop scheduling with separate resource recycling operations
(2012-06-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
Huang, H. L.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper considers the relocation problem arising from public re-development projects cast as a two-machine flowshop scheduling problem. In such a project, some buildings need to be torn down and re-constructed. The two processes of tearing down and re-constructing each building are often viewed as a single operation. However, under certain circumstances, the re-construction process, i.e., the resource recycling process, can be viewed as a separate operation. In this paper we regard these two processes as separate on the assumption that they are handled by different working crews. We formulate the problem as a resource-constrained two-machine flowshop scheduling problem with the objective of finding a feasible re-development sequence that minimizes the makespan. We provide problem formulations, discuss the complexity results, and present polynomial algorithms for various special cases of the problem. (C) 2010 Elsevier Ltd. All rights reserved.
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.
Scheduling in an assembly-type production chain with batch transfer
(2007-04-01)
Lin, B. M. T.
;
Cheng, T. C. E.
;
Chou, A. S. C.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper addresses a three-machine assembly-type flowshop scheduling problem, which frequently arises from manufacturing process management as well as from supply chain management. Machines one and two are arranged in parallel for producing component parts individually, and machine three is an assembly line arranged as the second stage of a flowshop for processing the component parts in batches. Whenever a batch is formed on the second-stage machine, a constant setup time is required. The objective is to minimize the makespan. In this study we establish the strong NP-hardness of the problem for the case where all the jobs have the same processing time on the second-stage machine. We then explore a useful property, based upon which a special case can be optimally solved in polynomial time. We also study several heuristic algorithms to generate quality approximate solutions for the general problem. Computational experiments are conducted to evaluate the effectiveness of the algorithms. (c) 2005 Elsevier Ltd. All rights reserved.
Scheduling of a two-stage differentiation flowshop to minimize weighted sum of machine completion times
(2009-11-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
Tian, Y.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper considers the problem of scheduling a two-stage flowshop that consists of a common critical machine in stage one and two independent dedicated machines in stage two. All the jobs require processing first on the common critical machine. Each job after completing its critical operation in stage one will proceed to the dedicated machine of its type for further processing in stage two. The objective is to minimize the weighted sum of stage-two machine completion times. We show that the problem is strongly NP-hard, and develop an O(n(3)) polynomial time algorithm to solve the special case where the sequences of both types of jobs are given. We also design an approximation algorithm with a tight performance ratio of 4/3 for the general case. (C) 2009 Elsevier Ltd. All rights reserved.
Scheduling with Centralized and Decentralized Batching Policies in Concurrent Open Shops
(2011-02-01)
Lin, B. M. T.
;
Cheng, T. C. E.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This article considers batch scheduling with centralized and decentralized decisions. The context of our study is concurrent open shop scheduling where the jobs are to be processed on a set of independent dedicated machines, which process designated operations of the jobs in batches. The hatching policy across the machines can be centralized or decentralized. We study such scheduling problems with the objectives of minimizing the maximum lateness, weighted number of tardy jobs, and total weighted completion time, when the job sequence is determined in advance. We present polynomial time dynamic programming algorithms for some cases of these problems and pseudo-polynomial time algorithms for some problems that are NP-hard in the ordinary sense. (C) 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 17-27, 2011
Sequence-dependent scheduling with order deliveries
(2013-10-01)
Lin, B. M. T.
;
Yin, P. Y.
;
Liu, Y. S.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper studies a sequence-dependent scheduling problem incorporating order delivery, motivated by satellite imaging scheduling. A set of jobs is to be processed on a single machine and each job belongs to a specific group. The completion time of a group is the moment when all jobs belonging to this group are completed. The problem is to determine a processing sequence of the jobs such that the sum of weighted completion times over all groups is minimized. We present a binary integer program to formulate the studied problem and then develop an O(n(2)2(n)) dynamic programming algorithm for determining optimal solutions. To produce approximate solutions within an acceptable time, we design a tabu search algorithm, an iterated local search algorithm and a genetic algorithm. Computational experiments are conducted to study the performance of the integer program and the solution algorithms. Numerical statistics suggest that the binary integer program can reach optimal solutions faster than the integer program existing in the literature, and the iterated local search algorithm outperforms other approaches when the number of jobs increases. (C) 2013 Elsevier Inc. All rights reserved.
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 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-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