Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Alex Saleh,Emsosfi Zaini
Jurnal Teknik Industri , 2009,
Abstract: This research discusses jobs scheduling model on flowshop-4-stage for fabrication and assembly processes. Each job consists of a unique component and a common component. Both the unique and common components are processed on the first three machines and assembled on the fourth machine. The unique components are processed individually, while common components are processed in batches for which respective constant setups are needed. The criteria used for the models are to minimize maximum lateness and number of tardy jobs. The development is executed to accommodate the possibility of tardy jobs. A proposed algorithm is initiated with jobs scheduling using the earliest due date (EDD) rule for the single machine, and batching process using the dynamic programming principle. Number of tardy jobs improved based on Hodgson Algorithm. The proposed algorithm is not an optimal algorithm as we can not guarantee optimal in scheduling process, nevertheless the batching method can bring out an optimal solution. This research also discusses numerical cases to show model behavior. Abstract in Bahasa Indonesia: Penelitian ini membahas model penjadwalan job pada flowshop-4-stage untuk proses fabrikasi dan perakitan. Setiap job terdiri dari 1 unique component dan 1 common component, yang keduanya diproses pada tiga mesin pertama secara serial dan dirakit pada mesin keempat. Unique component diproses satu per satu sedangkan common component diproses dalam batch dengan waktu setup yang konstan untuk setiap batch. Kriteria yang digunakan adalah minimisasi lateness maksimum dan jumlah tardy jobs. Pengembangan model dilakukan untuk mengakomodasi adanya job yang terlambat. Algoritma dimulai dengan proses penjadwalan job dengan menggunakan aturan earliest due date (EDD) untuk mesin tunggal, dan proses batching dengan menggunakan pemrograman dinamis. Jumlah tardy jobs diperbaiki dengan Algoritma Hodgson. Algoritma yang diusulkan bukan merupakan algoritma optimal karena proses penjadwalan yang tidak dijamin optimal, meskipun proses batching dapat menghasilkan solusi optimal. Penelitian ini dilengkapi dengan contoh numerik untuk menunjukkan perilaku model. Kata kunci: flowshop-4-stage, unique component, common component, penjadwalan batch, lateness maksimum , jumlah tardy jobs.
Variable Neighborhood Search for Parallel Machines Scheduling Problem with Step Deteriorating Jobs
Wenming Cheng,Peng Guo,Zeqiang Zhang,Ming Zeng,Jian Liang
Mathematical Problems in Engineering , 2012, DOI: 10.1155/2012/928312
Abstract: In many real scheduling environments, a job processed later needs longer time than the same job when it starts earlier. This phenomenon is known as scheduling with deteriorating jobs to many industrial applications. In this paper, we study a scheduling problem of minimizing the total completion time on identical parallel machines where the processing time of a job is a step function of its starting time and a deteriorating date that is individual to all jobs. Firstly, a mixed integer programming model is presented for the problem. And then, a modified weight-combination search algorithm and a variable neighborhood search are employed to yield optimal or near-optimal schedule. To evaluate the performance of the proposed algorithms, computational experiments are performed on randomly generated test instances. Finally, computational results show that the proposed approaches obtain near-optimal solutions in a reasonable computational time even for large-sized problems.
Single Machine Slack Due-Window Assignment and Scheduling of Linear Time-Dependent Deteriorating Jobs and a Deteriorating Maintenance Activity
Bo Cheng, Ling Cheng
Open Access Library Journal (OALib Journal) , 2018, DOI: 10.4236/oalib.1104907
Abstract: In this paper, we consider the slack due-window assignment model and study a single machine scheduling problem of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. The objective is to find the job schedule having an assigned maintenance activity and due-windows with the minimum total cost consisting of costs of earliness, tardiness, window location and window size. A polynomial-time algorithm is presented in this paper with time complexity for n jobs.
Single machine slack due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity  [PDF]
Bo Cheng,Ling Cheng
Computer Science , 2014,
Abstract: In this paper, we consider the slack due-window assignment model and study a single machine scheduling problem of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. The cost for each job consists of four components: earliness, tardiness, window location and window size. The objective is to schedule the jobs and to assign the maintenance activity and due-windows such that the total cost among all the jobs is minimized. A polynomial-time algorithm with the running time not exceeding $O(n^2logn)$ to give a solution to this problem is introduced, where $n$ is the number of jobs.
Scheduling Deteriorating Jobs with a Common Due Window on a Single Machine  [PDF]
Jintao Meng,Jun Yu,Xiaoxu Lu
Information Technology Journal , 2012,
Abstract: We consider the problem of scheduling deteriorating jobs and common due window location on a single machine. The actual processing time of a job is a linear increasing function of its starting time. The problem is to determine the optimal earliest due date, the due window size and the job schedule simultaneously to minimize costs for earliness, tardiness, earliest due date assignment and due window size penalties. A polynomial time optimal algorithm is presented to solve the problem.
A fuzzy modeling for single machine scheduling problem with deteriorating jobs
Mohammad Mahavi Mazdeh,Farzad Zaerpour,Farzad Firouzi Jahantigh
International Journal of Industrial Engineering Computations , 2010,
Abstract: This paper addresses a bi-criteria scheduling problem with deteriorating jobs on a single machine. We develop a model for a single machine bi-criteria scheduling problem (SMBSP) with the aim of minimizing total tardiness and work in process (WIP) costs. WIP cost increases as a job passes through a series of stages in the production process. Due to the uncertainty involved in real-world scheduling problems, it is sometimes unrealistic or even impossible to acquire exact input data. Hence, we consider the SMBSP under the hypothesis of fuzzy L-R processing time's knowledge and fuzzy L-R due date. The effectiveness of the proposed model and the denoted methodology is demonstrated through a test problem.
Scheduling step-deteriorating jobs to minimize the total weighted tardiness on a single machine  [PDF]
Peng Guo,Wenming Cheng,Yi Wang
Mathematics , 2014,
Abstract: This paper addresses the scheduling problem of minimizing the total weighted tardiness on a single machine with step-deteriorating jobs. With the assumption of deterioration, the job processing times are modeled by step functions of job starting times and pre-specified job deteriorating dates. The introduction of step-deteriorating jobs makes a single machine total weighted tardiness problem more intractable. The computational complexity of this problem under consideration was not determined. In this study, it is firstly proved to be strongly NP-hard. Then a mixed integer programming model is derived for solving the problem instances optimally. In order to tackle large-sized problems, seven dispatching heuristic procedures are developed for near-optimal solutions. Meanwhile, the solutions delivered by the proposed heuristic are further improved by a pair-wise swap movement. Computational results are presented to reveal the performance of all proposed approaches.
Solving Flow Shop Sequencing Problem for Deteriorating Jobs by Using Electro Magnetic Algorithm  [PDF]
H. Davoudpour,M. Hadji Molana
Journal of Applied Sciences , 2008,
Abstract: In the classical scheduling problems, processing time was assumed to be constant and takes predefined values. In many realistic environments, such as machine maintaining or crisis event management, processing time on each machine depends on the position of jobs on the machine sequence or their starting time on that machine. We assume that processing time was an increasing linear function of its start time, in other words pij = αijtij, in the literature these jobs were called deteriorating jobs. This problem addresses classic nmfCmax scheduling problem with a new assumption on the processing time of the jobs and it was surmised in the format of nmp,pij = αijtijCmax. We have used new Electro Magnetic meta-heuristic algorithm to find near optimum solution and compared the results with the results obtained from modified classical algorithms like CDS and Palmer.
Minimizing Total Weighted Completion Time on Parallel Unbounded Batch Machines

LI Shu-Guang,LI Guo-Jun,WANG Xiu-Hong,

软件学报 , 2006,
Abstract: This paper considers the problem of scheduling n jobs on m parallel unbounded batch machines to minimize the total weighted completion time. Each job is characterized by a positive weight, a release time and a processing time. Each unbounded batch machine can process up to B (B≥n) jobs as a batch simultaneo usly. The processing time of a batch is the longest processing time among jobs in the batch. Jobs processed in the same batch have the same completion time, I.e., their common starting time plus the processing time of the batch. A polynomial time approximation scheme (PTAS) for this problem is presented.
Scheduling Equal-length Jobs with Release Times and Deadlines on a Batch Macine  [PDF]
LIU Zhao-hui
Journal of Chongqing Normal University , 2009,
Abstract: A batch machine can process a number of jobs simultaneously as a batch, where alll the jobs processed in a batch have the same start time and the same completion time, and the processing time of a batch is given by the longest processing time of the jobs assigned to it . This paper studies the problem of scheduling n equal-length jobs with release times and deadlines on a batch machine, so as to obtain a feasible schedule. Baptiste has presented an O(n8)algorithm for the problem.Comparatively, Garey and others have given an O (n2) algorithm for the corresponding classical single machine scheduling problem. In this paper, we generalize Garey and others' algorithm to obtain an O(n2)algorithm for the above batch machine scheduling problem, which improves greatly on Baptiste's algorithm. Our algorithm is divided into two phases. In the first phase, we declare the so-called forbidden regions in which no jobs can start if the schedule is to be feasible. In the second phase, we schedule the jobs forward from time zero by using the earliest deadline scheduling rule. If the machine is idle and some unscheduled jobs are available at some time which is not in any forbidden region, we schedule the available unscheduled jobs with earlier deadlines as many as possible as a batch. If the idle time of the machine falls in some forbidden region, we first update the time to the right end of the forbidden region, and then make decision.
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.