1,720,998 research outputs found
Fabrication and assembly scheduling in a two-machine flowshop
No full text[[abstract]]This paper considers a fabrication scheduling problem to minimize the makespan in a two-machine flowshop. Each job has a unique component and a common component to be processed on the first machine. On machine 1, the common components of the jobs are grouped into batches for processing with a setup cost incurred whenever a batch is formed. A job is ready for its assembly operation on the second machine if both its unique and common components are finished on machine 1. The problems with batch availability and item availability are known as NP-hard. In this paper, we give proofs for the strong NP-hardness of the two problems. The results suggest that it is very unlikely to develop polynomial- or pseudo-polynomial-time algorithm for finding exact solutions for the two problems.[[note]]SC
Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs
No full text[[abstract]]There is a set of jobs available to process in batches on a set of identical parallel machines. A sequence-independent setup time is incurred whenever a batch is formed on any machine. The jobs in the same batch are continuously processed after the setup. The processing length of a batch is the sum of the setup time and the processing times of the jobs it contains. Under the batch availability constraint, the completion time of a job is defined as the time when the batch it belongs to is totally completed. With each job, a due date is specified for its completion. In this paper, we first consider the problem to schedule as well as group the jobs so that the maximum lateness is minimized. The second problem is to minimize the number of tardy jobs. We first design dynamic programming algorithms for finding optimal solutions to the two problems. Then, we design several heuristics and conduct computational experiments to study their relative performance. (C) 2003 Elsevier B.V. All rights reserved.[[note]]SC
Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs
No full text[[abstract]]In this paper, we study a scheduling problem of minimizing the total completion time on a single machine where the processing time of a job is a step function of its starting time and a due date that is common to all jobs. This problem has been shown to be NP-hard in the literature. To derive optimal solutions from a practical aspect, we develop a lower bound and two elimination rules to design branch-and-bound algorithms. Through computational experiments, we show that the proposed properties are effective in curtailing unnecessary explorations during the solution-finding process, and that the synergy of these properties can solve problems with up to 100 jobs in a few seconds. (C) 2003 Elsevier Ltd. All rights reserved.[[note]]SC
A concise survey of scheduling with time-dependent processing times
No full text[[abstract]]We consider a class of machine scheduling problems in which the processing time of a task is dependent on its starting time in a schedule. On reviewing the literature on this topic, we provide a framework to illustrate how models for this class of problems have been generalized from the classical scheduling theory. A complexity boundary is presented for each model and related existing results are consolidated. We also introduce some enumerative solution algorithms and heuristics and analyze their performance. Finally, we suggest a few interesting areas for future research. (C) 2003 Elsevier B.V. All rights reserved.[[note]]SC
Minimization of maximum lateness under linear deterioration
No full text[[abstract]]This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be NP-hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within I min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases. (C) 2003 Elsevier Ltd. All rights reserved.[[note]]SC
Makespan minimization in single-machine scheduling with step-deterioration of processing times
No full text[[abstract]]This paper considers a single-machine scheduling problem of minimizing the maximum completion time for a set of independent jobs. The processing time of a job is a non-linear step function of its starting time and due date. The problem is already known to be N P-hard in the literature. In this paper, we first show this problem to be N P-hard in the ordinary sense by proposing a pseudo-polynomial time dynamic programming algorithm. Then, we develop two dominance rules and a lower bound to design a branch-and-bound algorithm for deriving optimal solutions. Numerical results indicate that the proposed properties can effectively reduce the time required for exploring the solution space.[[note]]SC
Ant-Tree: an ant colony optimization approach to the generalized minimum spanning tree problem
No full text[[abstract]]The ant colony optimization is a meta-heuristic inspired by knowledge sharing amongst ants using pheromone, which serves as a kind of collective memory. Since the past few years, there have been several successful applications of this new approach for finding approximate solutions for computationally difficult problems in reasonable times. In this paper, we study the generalized minimum spanning tree problem that involves the design of a minimum weight connected network spanning at least one node out of every disjoint subset of the nodes in a graph. This problem has a wealth of pertinence to a wide range of applications in different areas. As the problem is known as computationally challenging, we adopt the ant colony optimization strategy and present a new solution method, called Ant-Tree, to develop approximate solutions. As an initial attempt, our study aims to provide an investigation of the ant colony optimization approach for coping with tree optimization problems. Through computational experiments, we compare the performances of our approach and the method available in the literature. Numerical results indicate that the proposed method is effective in producing quality approximate solutions.[[note]]SC
Two-machine flowshop batching and scheduling
No full textAuthor name used in this publication: T. C. E. Cheng2004-2005 > Academic research: refereed > Publication in refereed journalAccepted ManuscriptPublishedGreen (AAM
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
