Solving Scheduling Deteriorating Jobs with Rate Modifying Activity by Y?cel Y?lmaz ?zt?rko?lu A dissertation submitted to the Graduate Faculty of Auburn University in partial fulfillment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 9, 2011 Keywords: scheduling, rate-modifying activity-deteriorating jobs, single machine Copyright 2010 by Y?cel Y?lmaz ?zt?rko?lu Approved by Robert L. Bulfin, Chair, Professor Emeritus of Industrial and System Engineering Jorge Valenzuela, Associate Professor of Industrial and System Engineering Emmett J. Lodree, Assistant Professor of Industrial and System Engineering ii Abstract Traditional scheduling problems assume that the processing time of a given job is always fixed. However, the processing times may change in real industrial applicants. To reflect the real world, we use two new phenomenons in this study. The first one is known as the deterioration job where the job processing times are defined by functions of their starting times and positions in the sequence. And, the other one is rate-modifying-activity is an activity which affects and changes the production rate of the machines. This study aims to determine the work sequence, the number of breaks and their positions within the work sequence while considering the deterioration jobs and rate-modifying-activities. In this dissertation, three different mathematical models are introduced to solve the scheduling problems. The first model addresses a classical single machine problem with makespan and total flow time objectives to consider deteriorating jobs and rate-modifying- activity. The second model introduces a single worker scheduling problem which considers workers? physiological factors while determining the break time. The third model introduces a bi-criteria scheduling model with deteriorating jobs and rate-modifying-activities on a single machine. Also, several different heuristic algorithms are developed for large-sized problems. For each mathematical model and heuristic, independent experiments are performed to analyze the effectiveness of these algorithms. iii Acknowledgments First and foremost I would like to thank Dr. Robert L. Bulfin for his guidance, support endless patience and being my father in Auburn. Without him and his continuous guidance, I never would have seen the end of this study. Special thanks go to Dr. Jorge Valenzuela and Dr. Emmett J. Lodree for their valuable suggestions and opinions. Also, I would like to thank Dr. Alice E. Smith for her support throughout my doctoral study. My sincere appreciation is also extended to all my friends who made my years in Auburn memorable. I would like to thank to my parents, Dr. Zeki Yilmaz and Dr. Canan Yilmaz for their unlimited love and continued support; to my brother Dr. Yetkin Z. Yilmaz and my husband Omer Ozturkoglu. Finally, my thanks go to my biggest motivator to complete this study, my little princess Duru. I dedicate this dissertation to the memory of my uncle Dr. Cihangir Ciftci and my grandma, Hale A. Ciftci, who truly believed in me. iv Table of Contents Abstract ......................................................................................................................................... ii Acknowledgments........................................................................................................................ iii List of Tables .............................................................................................................................. vii Chapter 1. Introduction ............................................................................................................... 1 1. Background ......................................................................................................... 1 2. Major Contributions ............................................................................................ 2 3. Organization of the Dissertation ......................................................................... 4 References ............................................................................................................... 5 Chapter 2. Single Machine Scheduling With Deteriorating Jobs and RMA .............................. 6 Abstract ...................................................................................................................... 6 1. Introduction .......................................................................................................... 6 2. Literature Review ................................................................................................. 8 3. Problem Definition ............................................................................................. 12 4. The Mathematical Model ................................................................................... 14 5. Fundamental Properties and Special Cases ........................................................ 15 5.1. A Polynomial Alg. for Makespan with Identical Processing Times ........... 18 6. The Heuristic Algorithms .................................................................................. 20 6.1. Heuristic for Makespan ................................................................................. 20 6.2. Heuristic for Total Completion Time ........................................................... 22 7. Computational Results ....................................................................................... 24 8. Summary ............................................................................................................ 35 References? .............................................................................................................37 Chapter 3. Scheduling Jobs to Consider Physiological Factors ............................................... 40 Abstract ..................................................................................................................... 40 1. Background ......................................................................................................... 40 2. The Mathematical Model .................................................................................... 43 3. Complexity Result ............................................................................................... 51 4. Heuristic Algorithm ............................................................................................ 53 5. Numerical Example of Heuristic ........................................................................ 55 6. Summary ............................................................................................................. 58 References ................................................................................................................. 60 Chapter 4. A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity ............ 62 Abstract ..................................................................................................................... 62 1. Introduction ......................................................................................................... 62 2. Literature Review ................................................................................................ 62 3. Problem Description ............................................................................................ 66 4. Criterion .............................................................................................................. 69 4.1 Total Completion Time ................................................................................. 69 4.2 Total Tardiness .............................................................................................. 69 4.3 Maximum Tardiness ..................................................................................... 69 4.4 Number of Tardy Jobs .................................................................................. 70 5. Computational Experiments ................................................................................ 70 vi 5.1 Data Generations ............................................................................................ 71 5.2 Bi-criteria Approach ...................................................................................... 71 5.3 Secondary Objective Approach ..................................................................... 73 5.4 Weighted Method ........................................................................................... 74 6. Conclusions ......................................................................................................... 77 References ................................................................................................................. 79 Chapter 5. Conclusions ............................................................................................................. 83 List of Tables Chapter 2 Table 1 Complexity Results of He et al. (2005) ......................................................................... 11 Table 2 Average Run Time (sec.) for Total Completion Time .................................................. 25 Table 3 Average Run Time (sec.) for Makespan ........................................................................ 26 Table 4 Comparison of Heuristic 1 and Mathematical Model for Makespan ............................. 28 Table 5 Comparison of Heuristic 1 and Mathematical Model for Total Completion Time ....... 29 Table 6 Comparison of Run Times of Heuristic 1 for Makespan with 50 Jobs.......................... 31 Table 7 Comparison of Run Times of Heuristic 1 for Total Completion Time with 50 Jobs .... 32 Table 8 Results of Heuristic 2 for Total Completion Time ........................................................ 33 Table 9 Number of Rmas versus Factors for Total Completion Time Objective ...................... 34 Table 10 Total Run Time versus Factors for Total Completion Time Objective ...................... 35 Chapter 3 Table 11 Work-Rest Problems ................................................................................................... 42 Table 12 The Parameters of the Problem .................................................................................... 48 Table 13 Parameter Settings for Recovery Rate ......................................................................... 48 Table 14 Parameter Settings for Usage Rate .............................................................................. 48 Table 15 Parameter Settings for Cumulative Changes ............................................................... 49 Table 16 Parameter Settings for Acceptable Limits ................................................................... 49 Table 17 Average Run Time for Total Completion Time (sec.) ................................................. 50 viii Table 18 Average Run Time for Makespan (sec.) ...................................................................... 50 Table 19 Basic Information for the Numerical Examples .......................................................... 56 Table 20 Experimental Factors ................................................................................................... 56 Table 21 Comparison of Heuristic and Mathematical Model for Makespan .............................. 57 Table 22 Comparison of Heuristic and Mathematical Model for Total Completion Time ........ 58 Chapter 4 Table 23 The Parameter of the Problem ..................................................................................... 71 Table 24 Average Run Time (sec.) for ???? UTrmp jijij |/,)1(/1 m a x1? ............................. 73 Table 25 Average Run Time (sec.) for ????? FTrmp jijij |/,)1(/1 1? ........................... 74 Table 26 Weighted Method for ),(/,)1(/1 1 FTfrmp jijij ??? ? ............................................ 76 Table 27 Weighted Method for ),(/,)1(/1 m a x1 UTfrmp jijij ??? ? ......................................... 77 1 CHAPTER 1 INTRODUCTION 1. Background The competition between companies in the same industry has become vital due to the recession in the national and the international economy. Nowadays, the cost of production and the response to the customers? requirements are becoming more important on a daily basis for many of the industries to be successful in the market place. So, this leads them to redesign their processes and jobs. Hence, reducing the completion time of the product becomes one of the most important factors in job design. In this study, to be able to reduce the completion time of the products, we focus on the sequencing and scheduling of jobs, as well as some benefit activities. In both manufacturing and service industries, jobs might have variable processing times. Delaying a job may result in additional time to complete it, such as cleaning dirty dishes the longer they wait, the harder they are to clean. These kinds of jobs are known as deteriorating jobs in the literature; if processed later they take more time than when processed earlier. In other words, deteriorating jobs are tasks which need more time and effort to complete the process than when they are done earlier. Gupta and Gupta (1988), and Browne and Yechiali (1990) initiated studies on scheduling deteriorating jobs. Some examples of deteriorating jobs are searching for an enemy under growing darkness, treating a patient under worsening health conditions or producing steel under decreasing oven temperature (Mosheiov 1996). 2 If a job deteriorates, there is an activity called a rate-modifying activity (rma) which recovers the lost time of processing for a job because of the deterioration. Lee and Leon (2001) first introduced the rma which changes the production rate of a processor such as machines and workers. In the scheduling literature, an rma is defined as a maintenance or repair activity of a machine. So, when an rma is taken, there is some improvement on processing of that job, i.e., its processing time decreases. In this study we deal with two similar problems of scheduling a set of deteriorating jobs on a single machine. We propose three different models which reflect real life situations in which the processing time of a job increases or decreases depending on its initial processing time and other activities such as maintenance or repair of a machine, break for workers, etc. In our first model, we schedule deteriorating jobs on a machine and an rma as a maintenance activity. In our second model we schedule tasks processed by a human worker where the rma as a break given to the worker in order to let him/her recover. Since our processor is a worker, we consider some physiological factors which may affect processing of the job and cause deterioration of the job. In the last model, we have bi-criteria objectives to satisfy both customers and managers with real life assumptions. Therefore, managers should consider more than one measure when they try to find the best schedule for their production process. The general problem we deal with in this study is to determine the best work sequence, the number of rmas and the position of each rma for our specified model assumptions and objectives. 2. Major Contributions This study differs from existing studies in several ways. Contribution 1. We develop the first mathematical model to schedule deteriorating jobs and 3 rma to reflect real industrial situations. Another difference of the first model is our processing times. Specifically, we consider nonlinear deterioration which depends on the position. Up until now, all other research papers have considered time-dependent deterioration. Contribution 2. Another important contribution of this research is that we consider physiological factors of workers when scheduling the jobs. There has been no research which simultaneously considered deteriorating jobs and rma under some physiological constraints. Except for Lodree and Geiger (2010), to find an optimal sequence position for an rma, ergonomic factors have been mostly ignored in scheduling problems. So, this research acts as a bridge which connects scheduling with ergonomic issues. Thus, this study is an important milestone. Contribution 3. In our second model, we assume that jobs deteriorate because of worker fatigue. We define rate modifying activities as a resting period of workers. All other studies use rma as maintenance or repair activity of a machine. As workers tire, the job processing time increases. In the existing literature, jobs deteriorate because of the waiting time. Hence, as that kind of job waits in the queue to be processed, its processing time increases. Contribution 4. The literature is rich for job scheduling problems when we consider either deteriorating jobs or rma .But these are not directly related to customer and manager satisfaction at the same time. We propose the first bi-criteria model to consider rma and deteriorating jobs simultaneously. In our research the following three major questions are addressed to minimize the completion time of all given jobs: 1) How should jobs be scheduled? 4 2) How many rmas are needed? 3) Where are these rmas in the schedule? These questions are addressed for the problem with and without physiological factors. 3. Organization of the Dissertation The rest of the dissertation is organized as follows. In Chapter II, we present a mathematical model for scheduling deteriorating jobs with rma. An extension of the model, which considers physiological factors is discussed in Chapter III. In Chapter IV, we discuss a bi-criteria scheduling model. Conclusion and future work are provided in Chapter V. 5 References 1. Browne S. and Yechiali U. (1990). Scheduling deteriorating jobs on a single processor. Operations Research, 38, 495-498. 2. Gupta, J.N.D. and Gupta, S.K. (1988). Single facility scheduling with nonlinear processing times. Computers and Industrial Engineering, 14, 387-393. 3. Lee, C.Y. and Leon, V.J. (2001). Machine scheduling with a rate-modifying activity. European Journal of Operational Research, 128, 119-128. 4. Lodree, E. J. and Geiger, C.D. (2010). A note on the optimal sequence position for rate- modifying activity under simple linear deterioration. European Journal of Operational Research, 201 (2), 644-648. 5. Mosheiov, G. (1996). ?-Shaped policies to schedule deteriorating jobs. Journal of the Operational Research Society, 47, 1184-1191. 6 CHAPTER 2 SINGLE MACHINE SCHEDULING WITH DETERIORATING JOBS AND RATE- MODIFYING-ACTIVITIES Abstract In this study, we examine the scheduling a set of deteriorating jobs on a single processor. We propose a model which reflects real life situations in which the processing time of jobs change depending on its initial processing time and activities, such as machine maintenance or a break for workers. A rate-modifying-activity (rma) is a maintenance activity given to a machine to restore it to its original state. The general problem we deal with in this study is to determine the job sequence, the number of rmas, and rma positions within the work sequence. We formulate a unique integer program to solve this model for makespan and total completion time objectives. We also propose efficient heuristic algorithms for solving large size problems for both makespan and total completion time objectives. Polynomial algorithms for several special cases are derived. 1. Introduction In the last four decades, scheduling researchers have primarily concentrated on problems with a standard set of assumptions. One of these assumptions is that processing times of the jobs are constant. But in reality, processing times may change due to various factors such as deterioration and wear phenomena. 7 A deteriorating job can be defined as a job which takes more time when processed later than when processed earlier. In our study, an increase in processing times is caused by machine deterioration. After a while, the machine needs more effort to accomplish the task, this is described as the deterioration rate of jobs. Constant speed of machines or fixed processing times can be changed by rate- modifying activities (rma). The rma was first introduced by Lee and Leon (2001). The processing times of the jobs vary depending on whether a job is scheduled before or after the rma because the rma lets the machine or worker recover. After machines are maintained, they tend to have different speeds than before. In our study we define an rma as a maintenance activity during which the machine stops for a given period of time. After an rma is completed, the capability of the machine is expected to return to normal. In our study, the scheduling model we propose includes both deteriorating jobs and rma. More specifically, we develop a mathematical model to determine job sequences and placement of breaks under makespan and total completion time. We follow the three?field notation introduced by Graham et al. (1979) to describe scheduling problems. This notation is ??? || , where ? denotes the worker/machine condition, ? indicates the characteristics of the problem and ? shows the performance measure. Hence, we study ????? ni ijijij Crmpp 11 |,)1(|1 ? and m a x1 |,)1(|1 Crmpp jijij ??? ? . In this notation ijp ,? , rm and C represent actual processing time, deterioration rate, rma and completion time of jobs respectively. The remainder of this chapter is organized in eight sections. In Section 2, a literature review is given. The problem definition is in Section 3. A mathematical model is presented in Section 4. In Sections 5, an algorithm for makespan is presented. Heuristics for both 8 objectives are given in Section 6. Computational results are given in the Section 7. Finally, the conclusions are presented in the last section. 2. Literature Review Classical machine scheduling problems have been widely studied by many researchers. Recently, researchers have started to give more attention to scheduling problems with different characteristics including deteriorating jobs, learning effects or rate-modifying activities. Makespan, total completion time, total weighted completion time, maximum lateness, maximum tardiness and number of tardy jobs are the most commonly studied performance measures. Scheduling deteriorating jobs was first introduced by Gupta and Gupta (1988), and Browne and Yechiali (1990). Gupta and Gupta (1988) introduced a scheduling model with variable processing time of a job which is a polynomial function of its initial processing time. Then Browne and Yechiali (1990) mentioned deteriorating jobs; their processing times increase while they await service. They considered that a processor loses its efficiency with a certain rate as soon as it finishes its operation. In their model, all jobs are available at the beginning with their initial processing times. If the processing of a job is delayed, then the required time to process that job increases linearly based on its initial processing time. They constructed a scheduling problem to minimize the makespan for n jobs on a single machine. Mosheiov (1991) considered the problem of minimizing total completion time of jobs with different deteriorating rates and found that the optimal sequence of this problem is V-shaped. V-shaped scheduling indicates that ?jobs are arranged in descending order of growth rate if they are placed before the minimal growth rate job, and in ascending order if placed after it.? (Mosheiov (1991). Cai et al. (1998) developed a fully polynomial time approximation 9 scheme to minimize makespan for deteriorating jobs. Also Kubiak and Vende (1998) investigated the computational complexity of makespan under deterioration. They developed a heuristic and branch-and-bound algorithm for the problem. Kovalyov and Kubiak (1998) presented a fully polynomial approximation scheme for a single machine scheduling problem to minimize makespan of deteriorating jobs. Cheng and Ding (2000) studied a single machine to minimize makespan with deadlines and increasing rates of processing times. They found that both problems are solvable by a dynamic programming algorithm. Bachman and Janiak (2000) considered a single machine scheduling problem minimizing maximum lateness under linear deterioration. They presented two heuristics and proved that the maximum lateness problem is hardNP? . Bachman et al. (2002) showed that total weighted completion time is hardNP? for single machine scheduling in which the job processing times are decreasing linear functions dependent on their start times. These models all have the processing time of a job as a function of its start time. None of these works are valid for position based deterioration. Rma is a phenomenon in scheduling problems appearing in the last decade. In the scheduling literature, rma is defined as a maintenance or repair activity which improves the condition of the machine. Qi et al (1997) considered a problem where multiple maintenance activities need to be scheduled with jobs on a single machine. Also Lee and Chen (2000) scheduled jobs and maintenance activities to minimize total completion time on a set of jobs on parallel machines. They proposed branch-and bound algorithms for solving medium sized problems. Lee and Leon (2001) introduced a different perspective of scheduling maintenance activities. They studied a scheduling problem with maintenance activities which is commonly found in electronic assembly lines. One of the main decisions their model addresses is 10 whether to stop the machine and fix the problem or to let it work with a lower production rate. Hence, processing times of jobs may change after a maintenance activity. They also studied various performance measures including makespan, total completion time, total weighted completion time and maximum lateness. They developed polynomial algorithms for solving problems of minimizing both makespan and total completion time. In addition, they developed pseudo-polynomial algorithms to solve the total weighted completion time problem. They used the start time of the maintenance activity as a decision variable in their model. However, their model does not include the possibility of machine breakdowns. Lee and Lin (2001) studied single machine scheduling problems involving repair and maintenance activities which they also called rma. They focused on two types of processing cases which are resumable and nonresumable. Their objective functions sought to minimize the expected makespan, total expected completion time, maximum expected lateness, and expected maximum lateness respectively. If they decide not to do maintenance activities for the problem of minimizing the expected makespan and the total expected completion time, they obtained these interesting results: i) when the cumulative distribution function of x, F(x), which indicates that machine breaks down if there is no maintenance activity, is concave then the sequence of the jobs is in SPT (shortest processing time) order; ii) if F(x) is convex, then the sequence of the jobs is in LPT (largest processing time) order. He et al. (2005) studied a single machine to minimize makespan and total completion time of jobs. They assumed that an rma is not always valid because an activity needs some additional resources such as operators and equipment. These resources may not be available all the time. Thus, they considered the problem with a restricted rma. If the rma must be performed, they called it mandatory (man.); otherwise, it is called optional (opt.). They 11 analyzed the computational complexity of both makespan and total completion time. Table 1 presents their complexity results. Table 1. Complexity Results of He et al. (2005) max/,/1 Coptrm hardNP? if all 1?i? Pseudo-polynomially solvable in )( mnmsO time max/,/1 Cmanrm hardNP? if all 1?i? FPTAS running in )/( 2 ?mnO ? iCoptrm /,/1 hardNP? if all 1?i? , Open if 1?i? Open in general and pseudo- polynomially solvable for the agreeable rate case in )( mnmsO time ? iCmanrm /,/1 hardNP? if all 1?i? , Open if 1?i? Open in general and pseudo- polynomially solvable for the agreeable rate case in )( mnmsO time To minimize makespan, they presented a pseudo-polynomial time algorithm and a fully polynomial time approximation scheme (FPTAS). To minimize the total completion time, they proposed a pseudo-polynomial algorithm as a special case. When they fixed the start times for the rma, availability constraints can be applied. There has been little research that simultaneously considered time-dependent processing times and rma. Lodree and Geiger (2010) integrated time dependent processing times and rma for assigning a single rma to a position. They showed that a single rma should be inserted in the middle of the optimal job sequence to minimize makespan. To the best of our knowledge, except for the recent study of Lodree and Geiger (2010), the scheduling problem with the effects of deterioration and rma has not been studied in the literature. We also differ in that our deterioration depends on job position rather than 12 start time. 3. Problem Definition The problem we study in this paper is to schedule a set of n independent jobs ? ?nJJJJ ,....,, 21? and one or more rma?s for a single machine. All jobs are available for processing at all times. The machine (worker) can do only one job at a time. Each job has a deterioration rate ? which reflects a delay time (worker?s fatigue) from processing jobs. We assume that the deterioration rate ? has the same effect on processing times of different jobs and it changes the processing time of the job nonlinearly based on its position. Let us define model parameters and variables as follows: Model Parameters: n is the number of jobs to be sequenced i indicates the position number which is from 1 to n k indicates the position number which is from 0 to n (k=0 is initial position) j indicates the job number which is from 1 to n ? 10 ??? , is the constant deterioration rate of jobs when delayed by one position. q is the fixed period of time to perform an rma. jp is the initial processing time of job j before deterioration. jip is the processing time of jobj if done i positions after an rma or the initial position, i.e. ? ? jiji pp 11 ??? ? (3.1) 13 Model Variables: ??? ?? o t h e r w i s e 0 1,kp o s i t i o n b e f o r ej u s t done is w h i c h r m aa n a f t e r p o s i t i o n i t h i n t h e is j j o b if 1ijkx ???? z e r o o t h e r w i s e 0 i,p o s i t i o n b e f o r e done is r m aa n if 1iy iC Completion time of the job in position i. maxC Completion time of the job in the last position. In addition, our model assumptions are given as the following: ? There is only one machine (worker). ? The deterioration of a job depends on its position. ? Jobs are non-preemptive. ? After an rma, jobs revert to their initial/base processing time jp . That means the machine (worker) recovers completely after an rma (100% recovery). ? Deterioration process is the same after an rma. In our research the following three questions are addressed to minimize the completion time or makespan of all given jobs: 1) How should jobs be scheduled? 2) How many rmas are needed? 3) Where are rmas in the schedule? 14 4. The Mathematical Model As mentioned before, we consider two performance measures: total completion time and makespan. Hence, independently our objective function is to minimize each of those performance measures in our models. Minimize ? ?? n i iCZ 1 ni ,..,1? (total completion time) or Minimize maxCZ? , iCC ?max ni ,..,1? (makespan) The related constraints with our model are given as follows. ??? nj jj xpC 1 0111 (4.1) ?? ? ??? ??? nj ikijijkikii yqxpCC 1 ,,11 ni ,.....,2? (4.2) ?? ??? ?101 1ik ijkni x nj ,.....,1? (4.3) ?? ??? ?nj ijkik x110 1 ni ,.....,1? (4.4) 1?? ikji yx nk .....,2? nj ,.....,1? 1,.....,1 ?? ki (4.5) 15 ? ?1,0?ijkx nknjni ,.....,0,.....,1,.....,1 ??? (4.6) ? ?1,0?ky nk ,.....,2? (4.7) 0?iC ni ,.....,1? (4.8) In constraint (4.1), the completion time of the job in position 1?i is equal to the processing time of the job assigned to position 1?i . Before the first position, there is no rma ( 01?y ). In constraint (4.2), the completion time of the job in position i is equal to the completion time of the job in position 1?i plus the processing time of the job assigned to position i plus the rma time if assigned. In constraint (4.3), each job is assigned to exactly one position. In constraint (4.4), each position is scheduled for only one job. Constraint (4.5) requires an rma to be done in the related position if jobs are scheduled after rma and to control the sequence of the rma. Constraints (4.6), (4.7) and (4.8) show that the variables should be binary and non-negative. 5. Fundamental Properties and Special Cases In this section, we develop some fundamental properties and develop polynomial algorithms for the unit processing time problem. First, we examine the problem without rmas in Theorem 1 and then develop the result with a rma in Theorem 2. Theorem 1. For 1/ ? ? jiij pp 11 ??? ? / maxC , LPT sequencing minimizes the makespan. 16 Proof: Suppose schedule S minimizes makespan and is not in LPT order. Then there must be a pair of jobs in S , say job i and job j , with job i immediately after jobj in the thk and stk 1? positions, and ji pp? . Let B be the set of jobs before job i , and A the set of jobs after job. Let )(AC and )(BC be the sum, of processing times in sets A andB respectively. Now consider the schedule 'S , where 'S the same as S except job i and j have been interchanged and the sets of jobs A and B are in the same position in both schedules. ? ?',,, ?? jiS ? and ? ?'' ,,, ?? ijS ? where ? and '? denote partial sequences. The makespan for S is; ? ? ? ? ? ? ? ?ACppBCSC njin ???? ? 1 ? ? ? ? ? ? ? ?ACppBC jnin ?????? ?? 12 11 ?? (5.1) and the makespan for 'S is; ? ? ? ? ? ? ? ?ACppBCSC nijn ???? ? 1' ? ? ? ? ? ? ? ?ACppBC injn ?????? ?? 12 11 ?? (5.2) Subtracting equation (5.1) from (5.2) we get ? ? ? ? ? ? ? ? 01 2' ????? ? ijn ppSCSC ?? This implies the makespan of 'S is smaller thanS , which contradicts the assumption that S was optimal. Therefore, an optimal solution must be in LPT. Theorem 2. For 1/ ? ? rmpp jiij ,1 1??? ? / maxC the sequence of the jobs in an optimal solution is always in LPT order between any given pair of rmas. 17 Proof: Let ??BC be the total completion time of the jobs before given rma and ??AC be the total completion time of the jobs after given second rma. Now consider the schedule },,,,,,{ '?? rm akjirm aS ? (SPT order) and ? ?'' ,,,,,, ?? rm aijkrm aS ? (LPT order) where ? and '? denote partial sequences. The sets of jobs A and B are in the same position in both schedules. We assume that scheduleS is an optimal schedule. ? ?'' ,,,,,, ?? rm akjirm aS ? . Let us assume that, kji ppp ?? and after rma the first job assigned is in the thn )1( ? position. The m is defined as a duration of maintenance activity (rma). The makespan for S is; )3.5()()1()1()()( )1()1()()( )1()()( )()( 1 2m a x 1 1m a x 1 m a x 1m a x ACmpppmBCSC pppmBCSC ppmBCSC pmBCSC n k n jin n k n jin n jin in ????????? ??????? ????? ??? ? ? ? ? ? ? ?? ?? ? and the makespan for 'S is; )4.5()()1()1()()( )1()1()()( )1()()( )()( 1' 2m a x 1' 1m a x 1' m a x ' 1m a x ACmpppmBCSC pppmBCSC ppmBCSC pmBCSC n i n jkn n i n jkn n jkn kn ????????? ??????? ????? ??? ? ? ? ? ? ? ?? ?? ? Subtracting, equation (5.3) to (5.4) we get; ? ? ? ? ? ?? ?? ? 011'm a xm a x ?????? ikn ppSCSC ? The schedule 'S is better than scheduleS which contradicts the assumption that S was optimal. This means that between given two rma, the schedule is always LPT order, like schedule },,,,{ '' ?? ijkS ? . 18 5.1. A Polynomial Algorithms for Makespan with Identical Processing Times In this section, we give a polynomial algorithm for 1/ ? ? rmpp iij ,1 1??? ? / maxC which is a special case with ppj ? . Suppose we have a given number of rmas, say m. Then any schedule can be divided into 1?m groups of jobs scheduled between rmas and the beginning and of the schedule. Let the rmas be scheduled before positions mkkk ,....,, 21 . Let r mnd ??????? ?? 1 and 11 ??dk , ?? ? ????? ???? ? ? mrmidk rmidkk i i i ,....,11 ,....,2 1 1 A schedule with the m rmas before positions ik , mi ,...,1? is called a balanced schedule. This implies the number of jobs in each of the 1?m groups is as equal as possible, either having d or 1?d jobs. If 0?r , each group has exactly d jobs and we say the schedule is perfectly balanced. Theorem 3. Balanced schedules are optimal for 1/ ? ? mrmpp iij ??? ? ||,1 1? / maxC . Proof: We will assume an unbalanced schedule is optimal and show a contradiction. The makespan for a schedule with rmas at mkkk ,....,, 21 is; 11 1 11 1 11 1m a x )1(....)1()1( 1121 ??? ? ??? ? ?? ? ????????? ??? ? ikk i ikk i ik i pqpqpC mm ??? A balanced schedule has rm ??1 groups with d jobs and r groups with d+ 1 jobs. An unbalanced schedule must either have more than r groups with d+ 1 jobs or at least one 19 group with d+2 jobs. Assume an unbalanced schedule of the first type has minimal makespan. Without loss of generality; let the group before ik consist of d-1 jobs and the group after have d+ 1 jobs. The contribution to makespan of these two groups will be; dd id i id i pppppp ppSM )1(....)1()1(....)1( )1()1()( 2 11 1 11 1 ???? ?? ???????????? ???? ? ?? ? ?? ? ?? Now let 'S be an identical schedule to S except one job between 1?ik and 2?ik is moved between 1?ik and ik . Then 11 1 1 1 1 ' )1(....)1()1(....)1( )1()1()( ?? ? ? ? ? ???????????? ???? ?? dd id i id i pppppp ppSM ???? ?? and ?? )()( 'SMSM 0)1()1( 1 ???? ?ddp ?? , So S cannot be optimal. The other case can be shown non-optimal in the same way. To solve 1/ ? ? mrmpp iij ??? ? ||,1 1? / maxC , we create a balanced schedule for each possible value ofm . This is done in Algorithm 1. Algorithm 1 Step 0. Set 0?m , ??maxC . Step 1. Create a balanced schedule with m rmas and optimal makespan )(max mC If ,)( maxmax CmC ? )(maxmax mCC ? If nm? , stop Step 2. Set 1??mm , and go to Step1. 20 Step 1 requires at most )(nO operations and it will be repeated at most n times, so the algorithm is )( 2nO . 6. The Heuristic Algorithms Although our mathematical model, which we discussed in the previous section, can solve some problems in a reasonable run time, larger problems (e.g. n>50) are difficult to solve without considerable computational effort. Therefore, we propose heuristic algorithms to solve large problems. 6.1. Heuristic for Makespan For problems with a large number of jobs, Heuristic 1 provides a solution very close to the optimal solutions. Let us define; b Job with largest processing time within the set of unassigned jobs. s Job with smallest processing time within the set of unassigned jobs. m Potential position number after rma or initial position. ][iJ Job in position i ???? o t h e r w i s e 0 ip o s i t i o n b e f o r e p l a c e d is r m aa n if 1iy ijp Processing time of job j in position i as ? ? jkij pp 11 ??? ? iC Completion time of the job in position i The proposed heuristic first applies the LPT rule to sort the jobs. The job which has 21 the largest processing time is assigned to position 1. Then calculate the incremental amount of processing time of the first job which has smallest processing time. If this amount is greater than the rma time (q), then do an rma and assign the next largest job to the current position immediately after the rma. Otherwise do not do an rma and assign the smallest job to the current position without doing an rma. The procedure for the proposed heuristic for makespan problem is stated as follows: Heuristic 1 Step 1. Order the jobs in descending order (LPT) of processing times pj. set njpb j ,..,1m a x ?? Step 2. Assign the job with largest processing time to position 1?i and no rma at the beginning 01?y , nb? , 1?s Set npC 11? , bJ ?]1[ 1??bb , 1?s and 2?k . Step 3. Calculate; ]1[][ ??? ksks ppD If qD? go to Step 4 1?iy , bJk ?][ Set qpCC ibii ??? ?1 1??kk , 1??bb Go to Step 5. 22 Step 4. 0?iy , sJk ?][ Set isii pCC ?? ?1 , 1??ss , 1??mm and 1??kk Step 5. If nk? , Stop the algorithm, Makespan ][nC? ,otherwise go to Step 3. This algorithm is )log( nnO . It is well known that Step 1, can be completed in )log( nnO . In Step 2, there is only one iteration and this iteration can be completed in ).1(O There are at most n-1 iterations in step 3 and 4 and go through once for each job. Each iteration can be completed in )1( ?nO . Lastly, Step 5 can be completed in ).(nO 6.2. Heuristic for Total Completion Time The heuristic is developed for the problem of total completion time with given multiple rma?s. In the proposed heuristic, let J be a set of n jobs, },....,{ 21 nJJJJ ? and R be a set of m rmas?, },....,{ 21 mRRRR ? represents the position of the last job before the rma. Let S represent a schedule of n jobs and m rmas on a single machine, )},....,(),...,{( 2121 mn RRRJJJS ? . 1?mCT is the total processing time of the assigned jobs in the part m and assume },.....,,{ 121 ?mCTCTCT is the separate total processing of jobs in each part. The steps of the developed heuristic are given below: 23 Heuristic 2 Step 1: Split S into 1?m parts so that each part includes a set of jobs before each given consecutive rma. },....,{ 121 ?? mSSSS . And assume },.....,,m in { 121 ?mCTCTCT is the separate total completion of jobs in each part. Step 2: Order jobs based on LPT rule. Step 3: Assign one job, which has the largest processing time in the unscheduled list of jobs, into each part. ? ?}{},{},{ 121 ?? mJJJS Step 4: Calculate total completion time of the each part. 112211 ,, ?? ??? mm pCTpCTpCT Step 5: To assign the other jobs in each part, first select },.....,,m in { 21 mCTCTCT and then start to assign the next job to }min{CT . ? ?},{},,{},,{ 213241 ????? mmmm JJJJJJS And calculate new total completion time of the each part with adding deteriorated processing times. 2,113,224,11 ,, ????? ?????? mimmmimi ppCTppCTppCT Step 6: Repeat Step 5 until all jobs are assigned. Hence, the positions of the rma are naturally determined based on the scheduled jobs in each part. The best schedule is the *S , which gives the smallest flowtime. 24 7. Computational Results In this section, we conduct three experiments to analyze the effectiveness of our model. Experiment 1 focuses on the computational time to solve the proposed mathematical model for minimizing makespan and total completion time. In Experiment 2, we compare the computational effectiveness of all of the heuristic algorithms with the proposed mathematical model. In Experiment 3, an experimental design is built to estimate the relationship between parameters of the problem. To conduct our analyses on the proposed models, we identify four experimental factors: deterioration rate (? ), RMA time (q), mean processing time (M) and variance of processing time (V). Also, we specify three levels for each factor. So this is a 34 experimental design with six two-factor, four three-factor and one four-factor interactions. The defined levels of those factors in the experiments are: 1) ? : 0.02, 0.04 and 0.08 2) q : 5, 10 and 15 3) M : 20, 40 and 80 4) V : 0.20, 0.40 and 0.80 Using the variance and mean of processing time, we produced an interval for each combination; [18, 22], [10, 30], [1, 40], [36-44], [20-60], [1-80], [72-88], [40-120] and [1- 160]. We tested our models for 50 jobs, and 810 instances (10 replications) for each experiment. 25 Experiment 1: Performance of the Mathematical Model The proposed mathematical model is coded using AMPL and solved by CPLEX 9.1 on a computer with a Pentium IV 2.8 GHz processor and 1GB of RAM. Ten replications of each of the combination were run for each performance measure. The average computational time (in seconds) of each of the combination for each objective is given in Table 2 and Table 3, respectively. Table 2. Average Run Time (sec.) for Total Completion Time Jobs numb. (n) Det. Rate (? ) Rma time (q) Ave. Time (sec.) 0.02 5 9.2 0.02 10 16.1 0.02 15 29.7 0.04 5 14.5 25 0.04 10 20.1 0.04 15 20.2 0.08 5 9.9 0.08 10 20.2 0.08 15 21.2 0.02 5 58.3 0.02 10 91.5 0.02 15 119.5 0.04 5 28.2 50 0.04 10 56.6 0.04 15 61.1 0.08 5 11.6 0.08 10 32.7 0.08 15 45.1 26 Table 3. Average Run Time (sec.) for Makespan Jobs numb. (n) Det. Rate (? ) Rma time (q) Ave. Time (sec.) 0.02 5 11.6 0.02 10 12.9 0.02 15 18.4 0.04 5 15.6 25 0.04 10 22.7 0.04 15 23.1 0.08 5 12.6 0.08 10 19.8 0.08 15 22.4 0.02 5 78 0.02 10 109.4 0.02 15 101.9 0.04 5 51.2 50 0.04 10 83.6 0.04 15 93.8 0.08 5 25.5 0.08 10 51.8 0.08 15 66.8 The efficacy of the model is based on the average run time in seconds. The average time for 50 jobs for total completion time is 56.06 seconds and for the makespan it is 73.55 seconds. As seen in the tables, as the rma time increases, run time for both models increase. We expect this result because increasing the rma time means fewer rmas and jobs deteriorate more. For example, if the rma time is very small compared to deterioration, we expect the model to have many rmas. When the deterioration rate increases with the fixed rma time, run time for both models decreases for the same reason. Also, the problem of minimizing total completion time requires less time than that of makespan. Experiment 2: Performance of the Heuristic Algorithms The input parameters are the same as in Experiment 1. The heuristic algorithms were coded in Java. The solution quality percentage error is calculated by using the following 27 equation: ? ?? ? 100*/ optopth FFFe ?? In this equation, hF is the measure of the heuristic model and optF is the measure of the optimal solution obtained by the mathematical model. When we tested our models for 10 replications for each specific set of conditions, we obtained the average percentage errors of the heuristic models, which are given in the Table 4. 28 Table 4. Comparison of Heuristic 1 and Mathematical Model for Makespan Ave. Error of Heuristic 1 (%) Mean Ranges of Process Time ? RMA time 5 10 15 20 [18,22] 0.02 2.06 3.70 4.90 0.04 0.86 4.06 4.86 0.08 0.54 0.59 0.84 [10,30] 0.02 1.35 2.01 5.59 0.04 1.96 4.36 4.72 0.08 0.31 0.43 2.95 [1,40] 0.02 2.60 4.28 4.91 0.04 1.77 5.47 5.78 0.08 0.19 0.45 2.14 40 [36,44] 0.02 1.40 2.93 3.20 0.04 0.06 0.92 3.53 0.08 1.20 1.11 2.98 [20,60] 0.02 1.68 4.39 5.85 0.04 0.01 1.30 3.51 0.08 0.42 1.61 3.57 [1,80] 0.02 1.71 4.07 5.28 0.04 1.04 2.66 3.03 0.08 0.39 2.36 4.58 80 [72,88] 0.02 0.42 1.28 2.60 0.04 0.06 0.65 1.61 0.08 0.01 0.01 0.81 [40,120] 0.02 0.59 1.71 2.92 0.04 0.05 0.97 1.90 0.08 0.07 0.04 1.02 [1,160] 0.02 0.7 1.84 3.01 0.04 0.54 1.01 2.28 0.08 0.43 0.64 1.55 The average percentage error of all 810 instances is calculated as 2.06 % with the worst instance 5.85% for makespan. We also ran Heuristic 1 for the total completion time objective. 29 Table 5. Comparison of Heuristic 1 and Mathematical Model for Total Completion Time Ave. Error of Heuristic 1 (%) Mean Ranges of Process Time ? RMA time 5 10 15 20 [18,22] 0.02 2.06 3.70 4.90 0.04 0.86 4.06 4.86 0.08 0.54 0.59 0.84 [10,30] 0.02 1.35 2.01 5.59 0.04 1.96 4.36 4.72 0.08 0.31 0.43 2.95 [1,40] 0.02 2.60 4.28 4.91 0.04 1.77 5.47 5.78 0.08 0.19 0.45 2.14 40 [36,44] 0.02 1.40 2.93 3.20 0.04 0.06 0.92 3.53 0.08 1.20 1.11 2.98 [20,60] 0.02 1.68 4.39 5.85 0.04 0.01 1.30 3.51 0.08 0.42 1.61 3.57 [1,80] 0.02 1.71 4.07 5.28 0.04 1.04 2.66 3.03 0.08 0.39 2.36 4.58 80 [72,88] 0.02 0.42 1.28 2.60 0.04 0.06 0.65 1.61 0.08 0.01 0.01 0.81 [40,120] 0.02 0.59 1.71 2.92 0.04 0.05 0.97 1.90 0.08 0.07 0.04 1.02 [1,160] 0.02 0.7 1.84 3.01 0.04 0.54 1.01 2.28 0.08 0.43 0.64 1.55 The average percentage error of all 810 instances is calculated as 1.85 % with the worst instance 4.39% for total completion time. If the deterioration rate is fixed and the rma duration increases, average percentage error increases. When the rma time increases, 30 scheduling the jobs based on the order results in a larger error than scheduling the job by investigating each job separately. On the other hand, if the duration of the rma is fixed and the deterioration rate rises, the average percentage error decreases. In this case, jobs are deteriorating more because of the increasing deterioration rate with fixed rma time. The difference between the required additional time due to the deteriorated job and the rma time converges. Hence, the position of the rma becomes less critical. Additionally, when the variation of the mean of processing time increases, the average percentage error of all instances in that group increases. Table 6 and Table 7 shows the comparison of the computational times for both the proposed models for makespan and total completion time objectives. By comparing the heuristic model with the mathematical model, it is clear that the heuristic model requires much less computation time than the proposed mathematical model. 31 Table 6. Comparison of Run Times of Heuristic 1 for Makespan with 50 Jobs rma time=10 Ranges of Process Time ? Mathematical Model (sec.) Heuristic Model (sec.) [18,22] 0.02 93 0.05 0.04 82.13 0.03 0.08 43.15 0.02 [36,44] 0.02 88.53 0.04 0.04 61.43 0.03 0.08 48.2 0.04 [72,88] 0.02 72.6 0.03 0.04 41.8 0.02 0.08 17.3 0.02 [10,30] 0.02 98 0.03 0.04 113.13 0.03 0.08 88.26 0.02 [20,60] 0.02 100.72 0.05 0.04 95.4 0.04 0.08 45.13 0.03 [40,120] 0.02 86.23 0.04 0.04 43.03 0.03 0.08 16.56 0.02 [1,40] 0.02 129.5 0.05 0.04 121.7 0.04 0.08 104.83 0.04 [1,80] 0.02 123.6 0.08 0.04 80.96 0.03 0.08 40.23 0.03 [1,160] 0.02 90.61 0.05 0.04 34.51 0.05 0.08 11.12 0.02 32 Table 7. Comparison of Run Times of Heuristic 1 for Total Comp. Time with 50 Jobs rma time=10 Ranges of Process Time ? Mathematical Model (sec.) Heuristic Model (sec.) [18,22] 0.02 42.11 0.03 0.04 67.97 0.04 0.08 40.08 0.03 [36,44] 0.02 59.35 0.04 0.04 64.17 0.05 0.08 41 0.03 [72,88] 0.02 58.34 0.03 0.04 21.44 0.03 0.08 19.10 0.01 [10,30] 0.02 52 0.04 0.04 97.61 0.05 0.08 72.69 0.04 [20,60] 0.02 59.38 0.03 0.04 89 0.05 0.08 51.64 0.04 [40,120] 0.02 80.74 0.03 0.04 21.09 0.03 0.08 16 0.01 [1,40] 0.02 92.50 0.04 0.04 101.03 0.04 0.08 77.12 0.04 [1,80] 0.02 119.45 0.06 0.04 51.18 0.05 0.08 46.39 0.03 [1,160] 0.02 71.40 0.04 0.04 30.18 0.04 0.08 18.73 0.02 Therefore, as the number of jobs increases, the computational time for the mathematical model increases dramatically in comparison to the heuristic model. For example, we tested both models with 100 jobs with 5 replications. We used a deterioration 33 rate of 0.08, the rma time of 5, and the ranges of processing time is [1,160] with mean 80. Based on the results, the average percentage error is 0.369%. However, while the averages run time for the mathematical model is 2861.66 seconds, the heuristic model is only 46.5 seconds. This shows that the heuristic model has reasonable error with very short computational time for a large number of jobs compared to the mathematical model. Table 8. Results of Heuristic 2 for Total Completion Time The results of the average percentage error for minimizing total completion time to Heuristic 2 are presented in Table 8. Heuristic 2 gives very close to optimal solutions while the average percentage error is 0.65%. Experiment 3: Experimental Design To estimate the effects of input factors of the model, an experimental design is built. The input parameters are the same as in previous experiments. Table 9 shows the result of the experimental design for the problem of minimizing completion time. n = 50 Ave. Error of Heuristics (%) Rma Time Det. Rate Num. of Rma Heuristic2 5 0.02 20 0.62 0.04 23 0.53 0.08 24 0.51 10 0.02 19 0.63 0.04 19 0.78 0.08 21 0.62 15 0.02 18 0.65 0.04 20 0.71 0.08 20 0.88 34 Table 9. Number of Rmas Versus Factors for Total Completion Time Objective Source D.F. SS MS F P Det. Rate (?) 2 15500 7750.02 16064.2 0.00<0.05 sig. RMA Time (q) 2 9015.83 4507.92 9343.96 0.00<0.05 sig. Mean (M) 2 13148.7 6574.35 13627.2 0.00<0.05 sig. Variance (V) 2 159.9 79.95 165.72 0.00<0.05 sig. ? *q 4 508.9 127.23 263.71 0.00<0.05 sig. ? *M 4 878.39 219.6 455.18 0.00<0.05 sig. ? *V 4 433.77 108.44 224.78 0.00<0.05 sig. q *M 4 441 110.25 228.52 0.00<0.05 sig. q * V 4 311.49 77.87 161.41 0.00<0.05 sig. M* V 4 368.91 92.23 191.17 0.00<0.05 sig. ? *q*M 8 67.8 8.48 17.57 0.00<0.05 sig. ? *q*V 8 731.8 91.48 189.61 0.00<0.05 sig. ? *M*V 8 918.42 114.8 237.96 0.00<0.05 sig. q *M*V 8 772.51 96.56 200.16 0.00<0.05 sig. ? *q*M*V. 16 1490.8 93.18 193.13 0.00<0.05 sig. Error 729 351.7 0.48 Total 809 45100 R2 = 99.22% Table 9 clearly indicates that 99.22% of the variation in the number of rmas, which is a main variable of the model, is explained by all factors. Table 10 shows that 54.46% of the variation in total run time of the model is explained by all factors. This is the evidenced by the fact that the interaction of some factors is not significantly different. 35 Table 10. Total Run Time Versus Factors for Total Completion Time Objective Source D.F. SS MS F P Det. Rate (?) 2 433002 216501 122.29 0.00<0.05 sig. RMA Time (q) 2 258126 129063 72.90 0.00<0.05 sig. Mean (M) 2 488619 244310 138.00 0.00<0.05 sig. Variance (V) 2 89859 44930 25.38 0.00<0.05 sig. ? *q 4 7338 1834 1.04 0.38<0.05 sig. ? *M 4 5565 1391 0.79 0.535 not sig. ? *V 4 12511 3128 1.77 0.13<0.05 sig. q *M 4 4678 1169 0.66 0.620 not sig. q * V 4 16207 4052 2.29 0.058 sig. M* V 4 71023 17756 10.03 0.00<0.05 sig. ? *q*M 8 27955 3494 1.97 0.04<0.05 sig. ? *q*V 8 10868 1358 0.77 0.632 not sig. ? *M*V 8 43040 5380 3.04 0.00<0.05 sig. q *M*V 8 19171 2396 1.35 0.21<0.05 sig. ? *q*M*V. 16 55393 3462 1.96 0.01<0.05 sig. Error 729 1290563 1770 Total 809 2833916 R2 = 54.46% According to the experimental design results, there are significant differences among deterioration rate, rma time, mean processing times, variance of mean processing times and their interactions at the level of significance of 0.05. If one of the factors is changed, the optimal number of rma and their sequence position changes also. Furthermore, the change in the interactions between the model factors affects the result to a lesser degree. 8. Summary This paper investigates a scheduling problem with deteriorating jobs and rate- modifying-activity simultaneously. First, we present a mathematical model with the objective of minimizing the makespan and total completion time. Our model can decide the sequence 36 in which jobs should be scheduled, how many rmas to use, if any, and where to insert them in the schedule. We show that, as the number of jobs increases the computational time to solve the problem increases dramatically for the mathematical model. We provide polynomial time algorithms for unit processing time for makespan to solve the problem optimally. Several theoretical proofs are proposed to solve the problem with different special cases. We propose heuristics for both makespan and total completion time. Then, we present some computational experiments. According to the experimental results, the performance of the proposed model and the heuristics are quite satisfactory. Also, the heuristic models give a reasonable error for 50 jobs when compared to the mathematical model. These heuristic algorithms are able to construct near optimal solutions with much less computational time for large number of jobs )50( ? . 37 References 1. Bachman, A., Janiak, A. and Kovalyov, M.Y. (2002). Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters, 81(2), 81-84. 2. Bachman, A. and Janiak, A. (2000). Minimizing maximum lateness under linear deterioration. European Journal of Operational Research, 126(3), 557-566. 3. Browne S. and Yechiali U. (1990). Scheduling deteriorating jobs on a single processor. Operations Research, 38, 495-498. 4. Bureau of Labor Statistics, US Dept of Labor (2009). Generated report-Number of nonfatal occupational injuries and illnesses involving days away from work by selected industry. Retrieved from www.bls.gov. 5. Cai, J.Y. and Cai, P. (1998). On a scheduling problem of time deteriorating jobs. Journal of Complexity, 14, 109-209. 6. Cheng, T. C.E. and Ding, Q. (2000). Single machine scheduling with deadlines and increasing rates of processing times. Acta Informatica, 36, 673-692. 7. He Y., Ji, M. and Cheng, T.C.E. (2005). Scheduling with a restricted rate-modifying activity. Naval Research Logistics, 52, 361-369. 38 8. Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy, K. A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annual Discrete Math., 5, 287?326. 9. Gupta, J.N.D. and Gupta, S.K. (1988). Single facility scheduling with nonlinear processing times. Computers and Industrial Engineering, 14, 387-393. 10. Kovalyov, Y. M. and Kubiak, W. (1998). A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs. Journal of Heuristics, 3, 287-297. 11. Kubiak W. and Vende, S. (1998). Scheduling deteriorating jobs to minimize makespan. Naval Research Logistics, 45, 511-523. 12. Lee, C. Y. and Chen, Z. L. (2000). Scheduling of jobs and maintenance activities on parallel machines. Naval Research Logistics, 47, 61-67. 13. Lee, C.Y and Lin, C.S. (2001). Single-machine scheduling with maintenance and repair rate-modifying activities. European Journal of Operational Research, 135, 493-513. 14. Lee, C.Y. and Leon, V.J. (2001). Machine scheduling with a rate-modifying activity. European Journal of Operational Research, 128, 119-128. 39 15. Lodree, E. J. and Geiger, C.D. (2010). A note on the optimal sequence position for a rate- modifying activity under simple linear deterioration. European Journal of Operational Research, 201 (2), 644-648. 16. Mosheiov, G. (1991). V-Shaped polices to scheduling deteriorating jobs. Operation Research, 39, 979-991. 17. Mosheiov, G. (1996). ?-Shaped policies to schedule deteriorating jobs. Journal of the Operational Research Society, 47, 1184-1191. 18. Qi, X., Chen, T. and Tu, F. (1997). Scheduling with the maintenance on a single machine. Working Paper, Department of Computer System Sciences, Nankai University, China. 40 CHAPTER 3 SCHEDULING JOBS TO CONSIDER PHYSIOLOGICAL FACTORS Abstract In this paper, we study scheduling jobs and breaks for a single worker. The processing times of jobs increases as the worker tires. In this study, we assume that conventional machine scheduling models don?t always work for humans. So while determining the break time, we consider the workers physiological factors. The two objectives considered are total flow time and makespan. An exact mathematical model is presented with some physiological constraints. We prove the problem is hardNP? by a reduction from Equal-Size-Partition. Thus, we develop a heuristic algorithm to solve large problems. Numerical examples are presented for understanding and analyzing the performance of the mathematical model and the heuristic. 1. Background In classical scheduling problems, the optimal sequence of jobs on a single machine is equivalent to the optimal sequence of jobs performed by a single worker. But this is not the case in real life because the algorithm ignores constraints related to a human?s physiological factors and limitations. Workers get tired both physically and mentally while they are doing their job. So, this situation causes reduced performance and productivity of the workers. Fatigue is one important reason for decreasing performance. It can be caused by 41 extended working hours, inadequate rest periods and unsuitable working conditions. According to Fatigue Management System Guidelines (FMSG), a fatigued worker?s ability to perform their task may be lost or impaired. Fatigued workers can have; ? Reduced motivation ? Decreased speed of task ? Increase in memory errors ? Inability to concentrate ? Incorrect action Konz (1998) has declared that fatigue increases exponentially with time. Therefore, it is important to get rest before the fatigue level becomes too high. To prevent fatigue, workers need adequate rest periods during work periods. Breaks are designed to provide time for workers to overcome the fatigue arising from the work. Resting time is classified by Konz and Johnson (2004) as formal breaks (lunch, coffee), informal break (interruptions, training) and micro breaks (short pauses of a minute). When a break is given, the worker?s performance is expected to increase due to recovery. The recovery depends on how fatigued the worker is when the rest begins and the length of the rest. If the length of the break is small, the incremental amount of recovery is less than the incremental amount of time. For example, 4 breaks of 5 minutes are often more useful than 1 break of 20 minutes for two reasons; fatigue will not be increased as much and the recovery will be greater. In this study, we use rate- modifying activities (rma) as a kind of resting activity for workers. Rma was first introduced in the literature by Lee and Leon (2001). They defined rma as an activity which alters the production rates of machines. The rma plays an important 42 role in work-rest scheduling in the human factors literature. The main idea of work-rest scheduling is to obtain the number, place and duration of rest periods. While determining those decisions, productivity, safety and comfort are considered. In the literature, the objectives of the work-rest problem are to minimize fatigue and to provide recovery of the worker while not reducing productivity. Boucsein and Thum (1997) found that short breaks are more effective in promoting recovery from both mental and emotional recovery. Table 11 shows several researchers who studied the work-rest problem for various physiological variables such as heart rate, blood pressure, oxygen uptake and electromyography (EMG) signals. They found that resting time is important to recover from fatigue. Table 11. Work-Rest Problems Veltman and Gaillard (1993) Heart rate, blood pressure Boucsein (1993) Heart rate variability (HRV), EMG signals, electro dermal activity Imbeau et al. (1995) Heart rate, Maximum aerobic capacity (% max2VO ) Wu and Wang (2002) % max2VO , Heart Rate Tiwari and Gite (2006) Heart rate Hsie et al. (2009) % max2VO Our scheduling model is based on one developed by Ozturkoglu et al. (2011). Their model is to determine the work sequence, the number of breaks and the place of each break without considering the physiological factors of the worker. In this study, we consider the human characteristics while determining the work sequence, the number of breaks and the optimal break schedule. This study differs from existing research in several ways. First, we define rate- modifying activities as a resting period for workers; whereas all other studies use rate- 43 modifying activities as machine maintenance and repair time. Therefore, a rate modifying activity is a break given to workers in order to let them recover. Second, there is no research that considered the workers physiological factors when scheduling the jobs. Third, in our study, deteriorated jobs are caused by fatigue of the worker, but in the literature, jobs deteriorate while waiting to process. Thus, tiredness or fatigue of the worker is described as the deterioration rate of jobs. When we consider the industrial side, this study can provide insight on increasing worker efficiency to assigned job tasks. To the best of our knowledge, there is no research that proposed a task sequencing approach which combines deteriorating jobs, rma and considers the human characteristics. The chapter is organized as follows. In Section 2, we propose a mathematical model and test it computationally. In Section 3, we determine the computational complexity of the problem which is introduced in Section 1. We present a heuristic algorithm for larger problems and experimental results of the heuristic in sections 4 and 5 respectively. Lastly, we offer a summary in Section 6. 2. The Mathematical Model This model is motivated by the problem of manual order picking activities in warehousing systems. The problem is to determine the sequence in which the orders should be picked in minimum time and within acceptable levels of human physiological factors. In addition, breaks can be scheduled to allow workers to recover during the order picking sequence. We consider sequencing n orders (jobs) on a single worker (processor) with varying processing speed due to the effects of various ergonomic factors. We assume that a break time (rma) can be scheduled to improve the worker state any time after the first task is 44 scheduled. During the resting period, the worker stops doing his/her job. After an rma is scheduled, the speed of a worker is expected to return to normal limits. Ozturkoglu et al. (2011) determined the optimal job sequence with the optimal number of breaks and the place of each break. But that model does not consider the human?s physiological factors. Therefore, we add new constraints which consider physiological factors to obtain the optimal job schedule for a single worker. The mathematical model decides the sequence in which jobs should be scheduled, how many breaks to use to avoid fatigue, if any, and where to position them in the schedule. Those decisions are affected by human factors such as heart rate, oxygen consumption, and blood pressure. The worker may not recover completely after a break. Hence, we assume that every job consumes the worker?s physiological capacity at some level. The recovery rate changes with the position of the job. Also the types of jobs affect the recovery rate of the worker. Therefore, heavy jobs need more effort than light jobs. Assumptions ? Breaks should be taken during work shifts. ? The worker may not recover completely after breaks. ? Consider at least one physiological factor. ? Worker can not process two or more jobs simultaneously. Parameters n indicates the number of jobs to be sequenced i indicates the position number which is from 1 to n k indicates the position number which is from 0 to n (k=0 is initial position) j indicates the job number which is from 1 to n 45 F indicates the number of physiological factors ? is the constant deterioration rate of jobs for 10 ??? when delayed by one position. q is the fixed period of time to perform the rma jp is the initial processing time of job j before deterioration jip is the processing time of jobj if done i positions after an rma or initial position, i.e. ? ? jiji pp 11 ??? ? (2.1) fr is the recovery rate of physiological factor f fja is the usage rate of physiological factor f by job j fis is the change in cumulative physiological factor f caused by the i th rma ? ?ff RR is a lower (upper) limit on physiological factor f Decision Variables ??? ?? o t h e r w i s e 0 1,kp o s i t i o n b e f o r e p l a c e d is w h i c h r m aa n a f t e r p o s i t i o n i t h i n t h e is j j o b if 1ijkx ???? o t h e r w i s e 0 ip o s i t i o n b e f o r e p l a c e d is r m aa n if 1iy iC = Completion time of the job in position i. fiR = Cumulative value of physiological factor f at position i, Objective Functions To solve the problem, the objective of minimizing total flow time or makespan is used. 46 Minimize ? ?? n i iCZ 1 ni ,..,1? (2.2) Minimize maxCZ? , iCC ?max ni ,..,1? (2.3) . Mathematical Model ??? nj jj xpC 1 0111 (2.4) ?? ? ??? ??? nj ikijijkikii yqxpCC 1 ,,11 ni ,.....,2? (2.5) ?? ??? ?101 1ik ijkni x nj ,.....,1? (2.6) ?? ??? ?nj ijkik x110 1 ni ,.....,1? (2.7) ? ??? ?? nj jjfjff xparR 1 0111 Ff ,.....,1? (2.8) ? ??? ? ??? ???? nj ifikijijkfjfikiffi ysxparRR 1 ,,11, ni ,.....,2? Ff ,.....,1? (2.9) fR ? fiR ? fR ni ,.....,1? Ff ,.....,1? (2.10) 47 1?? ikji yx nk .....,2? nj ,.....,1? 1,.....,1 ?? ki (2.11) ? ?1,0?ijkx ni ,.....,1? nknj ,.....,0,.....,1 ?? (2.12) ? ?1,0?ky nk ,.....,2? (2.13) 0?iC ni ,.....,1? (2.14) In constraint (2.4), the completion time of the job in position one is equal to the processing time of the job assigned to position one. Before the first position, there is no rma ( 01?y ). In constraint (2.5), the completion time of the job in position i is equal to the completion time of the job in position 1?i plus the processing time of the job assigned to position i plus the rma time if assigned. In constraint (2.6), each job is assigned to exactly one position. In constraint (2.7), each position is scheduled for only one job. Constraint (2.8) computes the cumulative level of a physiological factor of the worker at the end of position 1. Constraint (2.9) determines the cumulative level of a physiological factor of the worker at the end of position i. Constraint (2.10) ensures that the level of cumulative physiological factor is always within prescribed acceptable limits. Constraint (2.11) requires an rma to be placed in the related position if jobs are scheduled after the rma and to control the sequence of the rma. Lastly, constraints (2.12), (2.13) and (2.14) indicate the decision variables are binary and all other variables are non-negative. 48 Performance of the Model A computational experiment is conducted to test the performance of the mathematical model with different numbers of jobs, deterioration rates and the rma time. Table 10 summarizes the model factors and each of their respective levels. In the model, we use three different physiological factors which are oxygen consumption ( max2VO ), heart rate ( maxHR ) and blood pressure ( BP ). These parameters are generated from a uniform distribution. Tables 12 through Table 16 summarize the physiological factor parameters. Table 12. The Parameters of the Problem Parameters Values jp U~ [1-50] # of jobs 25, 50 ? 0.02,0.04 and 0.08 rma time 5, 10, 15 (min.) Table 13. Parameter Settings for Recovery Rate Physiological factors Recovery rate ( fr ) maxHR fr ~U[1-20 ] % max2VO fr ~U[ 1-15] % BP fr ~U[ 1-20] % Table 14. Parameter Settings for Usage Rate Physiological factors Usage rate ( fja ) maxHR fja ~U[1-15 ] % max2VO fja ~U[ 1-15] % BP fja ~U[ 1-15] % 49 Table 15. Parameter Settings for Cumulative Changes Physiological factors Changes based on factors ( fis ) maxHR fis ~U[ 1-10] % max2VO fis ~U[ 1-10] % BP fis ~U[ 1-10] % Table 16. Parameter Settings for Acceptable Limits Physiological factors Acceptable limits ( ? ? ff RR ) maxHR 160 bpm- 220 bpm max2VO 15 % - 33% BP 75 mmHg -115 mmHg The proposed model is coded using AMPL and solved by CPLEX 9.1 on a computer with a Pentium IV 2.8 GHz processor and 1GB of RAM. For each parameter set, we run the model 10 times; 180 replications were run for both total completion time and makespan objective functions. The average computation times are given in Tables 17 and 18. 50 Table 17. Average Run Time for Total Completion Time (sec.) Jobs numb. Det. Rate Rma Time Ave. Comp. Time (sec.) 0.02 5 8.7 0.02 10 14.2 0.02 15 19.5 0.04 5 8.5 25 0.04 10 11.0 0.04 15 20.2 0.08 5 8.1 0.08 10 10.3 0.08 15 18.7 0.02 5 33.7 0.02 10 42.5 0.02 15 51.8 0.04 5 21.9 50 0.04 10 37.2 0.04 15 51.9 0.08 5 11.1 0.08 10 28.2 0.08 15 43.7 Table 18.Average Run Time for Makespan (sec.) Jobs numb. Det. Rate Rma Time Ave. Comp. Time (sec.) 0.02 5 12.5 0.02 10 15.1 0.02 15 19.9 0.04 5 10.3 25 0.04 10 15.6 0.04 15 21.2 0.08 5 9.4 0.08 10 16.7 0.08 15 23.8 0.02 5 41.2 0.02 10 47.9 0.02 15 54.5 0.04 5 38.3 50 0.04 10 46.4 0.04 15 51.4 0.08 5 18.3 0.08 10 29.9 0.08 15 48.1 51 The efficacy of the model is based on the average run time in seconds. The average time for total completion and the makespan problem is 24.5 seconds and 28.91 seconds respectively. As expected, run time increases as the number of jobs increase. The run time for the problem of both objectives decreases as the deterioration rate increases. Also, run time increases as the rma time goes up. These results are similar to the results of Ozturkoglu et al. (2011). When we compare run times, this model is computed faster than their model, because it is more constrained and the feasible region gets smaller. Another difference between the models is the place and the number of the breaks. Breaks are given more frequently in this model. This is expected because of the worker?s physiological factors. As a result, this model reflects a real industry situation. 3. Complexity Result In this section, we show m a x1 |,,)1(|1 Cphyrmpp jijij ??? ? is hardNP? . The reduction is based upon Equal-Size-Partition which is ordinary NP-complete. Equal-Size-Partition (ESP): Given a multi-set S ? ? 0,,....,, 221 ?jn aaaa with ? ? ? n j j Ba 2 1 2 is there a partition 1S and 2S such that Baa n Si i n Si i ????? 21 ? and ?21 nSS ?? Theorem 1. m a x1 |,,)1(|1 Cphyrmpp jijij ??? ? is hardNP? . Proof: Given an instance of ESP, we construct an instance of m a x1 |,,)1(|1 Cphyrmpp jijij ??? ? so that its optimal solution is 12?n if and only if the ESP has a solution. 52 For each element of S we create a job with 1?jp ; there are n2 jobs. Let the deterioration rate 0?? and the rma time 1?q . We only need one physiological factor, so we omit the subscript f . The recovery rate 0?r and the changing factor caused by the rma Bs? . The usage rate for job j is ja , Sj? . Let 0?R and BR? . If the ESP has a solution, then m a x1 |,,)1(|1 Cphyrmpp jijij ??? ? has the following schedule; 121 ?? nnn The makespan of this schedule is minimal since there must be at least one rma since jSj j Ba ??? and it is feasible since ,0 BRi ?? ,,..,1 ni? 0?nR and BRn ??1 due to the rma. If the ESP has no solution, then there must be at least 2 rma?s, resulting in 22max ?? nC . Lemma. ???? Cphyrmpp jijij |,,)1(|1 1? is hardNP? . Proof: The proof is identical to the makespan proof except the optimal value of the total completion time is; )1(22 )1()1(2 )1( ??????? nnnnnnnn 1S rma 2S 53 4. Heuristic Algorithm In this section, we present a polynomial time heuristic algorithm for m a x1 |,,)1(|1 Crmpp jiij ??? ? . In addition to the complexity of the problem, the larger sizes present some difficulty. Therefore, to solve large problems, a heuristic algorithm may be needed. In the proposed heuristic algorithm, we first provide the worker?s basic information such as gender, age, height and weight. Then, sort the jobs according to the SPT rule. The job which has the largest processing time is assigned to position 1. After assigning the job, calculate the fatigue rate of the worker. Fatigue can be used as an upper limit for energy expenditure during the work. Next, we determine an upper limit from the Borg scale. If this amount is larger than acceptable limits, then insert an rma and assign the next largest job to the position immediately after the rma. Otherwise assign the smallest job to the current position without doing an rma. Stop the heuristic when all jobs are assigned. Santos and Resnick (1999) developed an equation which calculates a worker?s predicted fatigue rate. We use fatigue as the single physiological factor, other factors could be used as well. Let us define a set of given jobs as J= {J1, J2, J3? J n}. The parameters and the equation are given below; prmtF 08.053.063.025.2 ????? (4.1) F The fatigue rate of the worker m The mass of the handled load in kg t The time into shift in minutes 54 pr The production rate in units per minute b job with largest processing time within the set of unassigned jobs s job with smallest processing time within the set of unassigned jobs i Position number after rma or initial position ][iJ Job in position i ???? o t h e r w i s e 0 ip o s i t i o n b e f o r e p l a c e d is r m aa n if 1iy ijp Processing time of job j in position i as ? ? jiij pp 11 ??? ? iC Completion time of the job in position i The procedure is described as follows: Step 1. Determine the basic information that will be used. (e.g. mass of the load, production rate and time) Step 2. Sequence the jobs in SPT order. Step 3. Schedule the job with largest processing time in position one and no rma at the beginning. 01?y , ?]1[J n Set npC 11? , 1??bb , 1?s , 2?k . Step 4. Calculate the ?Fatigue ?; prmtF 08.053.063.025.2 ????? Step 5. Determine the acceptable limit of the worker?s fatigue. Step 6. Decide if fatigue is within the acceptable limits 55 If ?F fR Then schedule the jobs with smallest processing time in that position and do not insert an rma. 0?iy , sJk ?][ Set isii pCC ?? ?1 , 1??ss and 1??kk ; Step 7. If ?F fR Then schedule the job with largest processing time in that position and insert an rma after that position. 1?iy , bJk ?][ Set qpCC jii ??? ?1 1??bb , 1??kk If ni? , go to Step 4. Otherwise go to Step 8. Step 8. If nk? , Stop the algorithm, Makespan iC? . 5. Numerical Example of Heuristic In this section, we use several numerical examples to illustrate the behavior of the model. In all the examples we assume parameters values from Table 19 and Table 20. 56 Table 19. Basic Information for the Numerical Examples Mass of the hand load U~[3-20] kg Time into the shifts U~[1-10]minutes Production Rate U~[1-10]unit /minute Table 20. Experimental Factors Factors Levels Number of jobs 10, 25, 50 Processing time U~[10-100] Deterioration rate 0.04, 0.06, 0.08 Rma time 5, 10, 15 To analyze the performance of the heuristic in terms of the error percentages, we compare heuristic solutions to an optimal solution on an instance taken randomly from the solution sets. We use the following equation: %100* opt opth F FFe ?? (5.1) In this equation, hF is the makespan value of the heuristic model, optF is the makespan value of the optimal solution and e is the average performance of the heuristic. The heuristic is replicated 10 times for each problem case. It is coded in JAVA and solved with a Pentium IV, 2.8 GHz processor and 1GB of RAM. The number of problems solved in each combination data set is 10. We obtained the average percentage error of the heuristic for makespan and total flow time objectives which are given in Tables 21 and 22. The experimental results show that the heuristic requires small run times for large problems. In general, the heuristic can be applied to any problem size. 57 Also, the heuristic algorithm finds near optimal solutions for all problems tested. The average error percentage is % 0.37 for total flow time and % 0.64 for makespan. Table 21. Comparison of Heuristic and Mathematical Model for Makespan Number of jobs ? Rma Time Ave. Error of Heuristic (%) 10 0.04 5 0.13 10 0.32 15 0.24 0.06 5 0.33 10 0.13 15 0.23 0.08 5 0.45 10 0.92 15 0.51 25 0.04 5 0.19 10 0.54 15 0.44 0.06 5 0.69 10 0.63 15 0.16 0.08 5 0.48 10 0.58 15 0.31 50 0.04 5 0.32 10 0.17 15 0.60 0.06 5 0.41 10 0.14 15 0.48 0.08 5 0.37 10 0.18 15 0.19 58 Table 22. Comparison of Heuristic and Mathematical Model for Total Completion Time Number of jobs ? Rma Time Ave. Error of Heuristic (%) 10 0.04 5 0.34 10 0.96 15 0.33 0.06 5 0.45 10 0.92 15 0.78 0.08 5 1.02 10 0.59 15 0.54 25 0.04 5 0.79 10 0.17 15 0.81 0.06 5 0.94 10 0.63 15 0.38 0.08 5 0.68 10 0.37 15 0.42 50 0.04 5 0.62 10 0.91 15 0.25 0.06 5 0.91 10 0.43 15 0.98 0.08 5 0.37 10 0.84 15 0.93 6. Summary This paper deals with scheduling rate-modifying-activities for a single worker. In order to reflect real industrial applications, we assume that the processing times of jobs deteriorate. This study is the first study to consider the physiological condition of workers while determining the number and timing of breaks. We minimize flow time and makespan. The model is relatively fast and can be solved in less than one minute with 50 jobs. Also, the 59 usage of jobs and recovery rate affects the solution when compared to the result of Ozturkoglu et al. (2011). The model gives higher completion time or makespan values because of the changing recovery rate. In this model, the worker doesn?t recover completely. Thus, this increases the realized processing times of jobs, and thus, total completion time. Additionally, the number and placement of breaks is completely different from models which do not consider physiological factors. We proved that this problem is hardNP? for both objectives. Therefore, we developed a heuristic algorithm for large problems. The computational results show that the heuristic gives near-optimal results in a reasonable time for the large problems. 60 References 1. Boucsein, W. (1993). Psychophysiology in the computer work-place goals and methods. Elsevier North Holland, Amsterdam, 135-139. 2. Boucsein, W. and Thum, M. (1997). Design of work/rest schedule for computer work based on psycho-physiological recovery measures. International Journal of Industrial Ergonomics, 20, 7-51. 3. Hancock, P.A. and Desmond, P.A. (2001). Stress, workload and fatugue: Human factors in transportation. Mahwah, NJ: Lawrence Erlbaum Associates, Inc. 4. Hsie, M., Hsiao, Cheng, T. and Chen, H. (2009). A model used in creating a work-rest schedule for laborers. Automation in Construction, 18, (6), 762-769. 5. Imbeau, D., Desjardins, L., Dessureault, P.C., Riel, P. and Fraser, R. (1995). Oxygen consumption during scaffold assembling and disassembling work: Comparison between field measurements and estimation from heart rate. International Journal of Industrial Ergonomics, 15, 247-259. 6. Konz, S. (1998). Work/rest: Part II - The scientific basis (knowledge base) for the guide. International Journal of Industrial Ergonomics, 22, 73?99. 7. Konz, S. and Johnson, S. (2004). Work design. Sixth edition, Scottsdale, AZ: Holcomb Hathaway. 61 8. Lee, C.Y. and Leon, V.J. (2001). Machine scheduling with a rate-modifying activity. European Journal of Operational Research, 128, 119-128. 9. Ozturkoglu, Y., Bulfin, R. L. and Lodree E. (2011). A Model for Scheduling Deteriorating Jobs with Rate-Modifying-Activities on a Single Machine. Working paper. 10. Santos, E. and Resnick, M.L. (1999). The effects of fatigue on quality and productivity in repetitive tasks, Florida International University. 11. Tiwari, P.S. and Gite, L.P. (2006). Evaluation of work-rest schedules during operation of a rotary power tiller. International Journal of Industrial Ergonomics, 36, 203-210. 12. Veltman, J.A. and Gaillard, A.W.K. (1993). Indices of mental workload in a complex task environment. Neuropsychobiology, 28, 72-75. 13. Wu, H.C. and Wang, M.J. (2002). Relationship between maximum acceptable work time and physical workload. Ergonomics, 45, 280?289. 62 CHAPTER 4 A BI-CRITERIA SINGLE MACHINE SCHEDULING WITH RATE-MODIFYING- ACTIVITY Abstract We consider a single machine scheduling problem with two criteria: minimizing both total flow time with total tardiness and minimizing maximum tardiness with a number of tardy jobs. We present a mathematical model which is based on a model developed by Ozturkoglu et al. (2011) to find the optimal schedule. In the mathematical model, job processing times are assumed to deteriorate. Besides deteriorated jobs, we also consider rate- modifying-activities. To analyze the mathematical model, we use three different approaches. According to computational results, up to 50 jobs can be solved in less than one minute. 1. Introduction In real life applications, customers and producers may have completely different perspectives. For instance, a producer wants to maximize his selling price of the product whereas a customer wants to minimize cost of product. To satisfy both customers and production effectiveness at the same time, minimizing both total completion time and number of tardy jobs is appropriate. So, managers should consider more than one measure when they try to find the best schedule for their production process. Therefore, bi-criteria scheduling is becoming more attractive. In most applications it is beneficial and necessary to measure the objectives of a 63 schedule with respect to different criteria. This provides more flexibility to the decision maker by allowing him/her to consider multiple schedules corresponding to the different solutions. Research on bi-criteria scheduling is rare compared to research in single criterion scheduling. Almost all bi-criteria research assumes job processing times are constant. But in a real life situation, job processing times may deteriorate while jobs are waiting to be processed. Both machine and operator may cause this deterioration. For instance, a machine or tools may wear and processing time and quality of the jobs will change. Or the operator?s physical condition may cause the processing speed to change over time. Browne and Yechiali (1990) introduced deteriorated processing times in the scheduling literature. They assumed that the processing time of a job grows linearly, depending on the start time of the job. To prevent job deterioration, repair or maintenance, called a rate-modifying activities (rma), are needed. The rma, an activity which affects and changes the production rate of the machines, was first introduced by Lee and Leon (2001). This research addresses bi-criteria scheduling problems involving a single machine with deteriorating jobs and rate-modifying-activities. We study two bi-criteria models; total flow time, total tardiness, maximum tardiness and number of tardy jobs. Minimizing total flow time leads to manufacturer satisfaction, while tardiness leads to customer dissatisfaction. To satisfy both sides by using these performance measures, we propose mathematical models and present experimental results for both ???? UTrmpp jiij |/,)1(/1 m a x1? and ????? TFrmpp jiij |/,)1(/1 1? . 64 2. Literature Review In the bi-criteria literature, some criteria are used very often. Therefore, we divide the literature review based on performance measures. We classify the most common criteria studied in bi-criteria single machine scheduling problems by researchers. But before giving information about previous research, we explain major approaches to solve bi-criteria problems. There are three approaches. 1) Bi-criteria Approach Generate the Pareto curve for all non-dominated schedules. Using Graham et al. (1979) three field notation, we denote single machine bi-criteria problems under basic assumptions as 21,//1 ?? . 2) Secondary Objective Approach First try to optimize the primary criterion and then solve the remaining secondary criterion subject to the primary criterion remaining optimal. Denote the single machine bi- criteria problems under basic assumptions as 12 |//1 ?? . 3) The Weighting Method In this method a weighted combination of both objectives is optimized. Mathematically, the weighting method can be stated as follows: )()1()()(m in 2111 xzwxzwxz ??? (2.1) 65 In this study, we use three approaches to analyze our mathematical model. Various combinations of the criteria are considered and analyzed as primary and secondary criteria in the literature. We give a brief literature review of the most commonly used performance measures. Total Completion Time and Maximum Tardiness Smith (1956) developed a polynomial time algorithm to use secondary objective approach scheduling problems with these two objectives. Afterwards, Heck and Roberts (1972), Emmons (1975), Van Wassenhove and Gelders (1980) extended Smith?s study and developed some algorithms for the secondary approach. Chen and Bulfin (1993) proved that flow time with maximum tardiness bi-criteria problems are NP-hard. Later, Kondakci et al. (1996) presented an algorithm to produce all efficient schedules for any given non decreasing function of the total completion tine and maximum tardiness objectives. Chen (2007) developed a heuristic to an objective of minimizing total flow time with maximum tardiness objectives. Weighted Completion Time and Maximum Tardiness Burns (1976) presented an algorithm that provide to a local optimum for both the weighted and unweighted problems in bi-criteria objectives. For the secondary approach, Bansal (1980) extended Burns (1976) algorithm and applied a branch and bound algorithm to find a globally optimal solution. In his algorithm, he found a locally optimal solution for the problem of minimizing weighted sum of completion times subject to the condition that every job be completed by its due date. Miyazaki (1982) solved bi-criteria problem with different approach which one of the criteria as objective and the other as a constraint. He developed a 66 necessary condition under which the local and global solutions are different and developed an algorithm to obtain an improved schedule based on the locally optimal schedule. Shanthikumar and Buzacott (1982), Potts and Van Wassenhove (1983) developed some heuristics for problem FT |//1 max . Posner (1985) and Bacghi and Ahmadi (1987) considered with these two performance measures with deadlines and they found tightest bound for same objectives. Chen and Bulfin (1993) proved that weighted flow time with maximum tardiness bi-criteria problems max|//1 TwT and max|//1 Twu are NP-hard. Total Completion Time and Number of Tardy Job Emmons (1975) was the first to study the secondary approach and presented a branch and bound algorithm for it. Then, Nelson et al. (1986) presented branching procedures for the bi-criteria approach. Chen and Bulfin (1993) proved that these objectives are NP-hard. Maximum Tardiness and Number of Tardy Job Firstly, Shanthikumar (1983) developed a branch and bound algorithm for the problem ? jUT |||1 max . Later on, Nelson et al. (1986) and Chen and Bulfin (1994) proposed both heuristic and branch and bound algorithms for problem ? max|||1 TU j . Huo et al. (2007) considered complexity relationship of single machine problems ? }m ax{|||1 jjj TwU and ? jjj UTw |}m ax{||1 with weighted tardiness. Also they proposed several fast heuristics. Most papers mentioned above assume processing time is constant. To the best of our knowledge, there is no study which combines bi-criteria scheduling problems with 67 deteriorating jobs. So this paper is the first study which combines deteriorating jobs with rate-modifying-activity in bi-criteria objectives. 3. Problem Description As stated earlier, this study focuses on the single machine bi-criteria scheduling problem. There are n jobs to be processed on a single machine. The jobs are available at time zero and are independent of each other. Preemption is not allowed. The machine can handle one job at a time. Each job has a base processing time jp before deterioration, a due date jd and an actual processing time jip which is the processing time of jobj if done i positions after an rma or the initial position. We calculate jip by; ? ? jiji pp 11 ??? ? (3.1) where ? is the deterioration rate of jobs for 10 ??? when delayed by one position. This is non-linear deterioration based on position rather than start time. And, q is the fixed period of time to perform the rma. Decision Variables ??? ?? o t h e r w i s e 0 1,kp o s i t i o n b e f o r e done is w h i c h r m aa n a f t e r p o s i t i o n i t h i n t h e is j j o b if 1ijkx ???? o t h e r w i s e 0 ip o s i t i o n b e f o r e done is r m aa n if 1iy iC = Completion time of the job in position i. Our model is based on Ozturkoglu et al. (2011). The constraints for our model are; 68 ??? nj jj xpC 1 0111 (3.2) ?? ? ??? ??? nj ikijijkikii yqxpCC 1 ,,11 ni ,.....,2? (3.3) ?? ??? ?101 1ik ijkni x nj ,.....,1? (3.4) ?? ??? ?nj ijkik x110 1 ni ,.....,1? (3.5) 1?? ikji yx nk .....,2? ; nj ,.....,1? ; 1,.....,1 ?? ki (3.6) ? ?1,0?ijkx nknji ,.....,0;,.....,1, ?? (3.7) ? ?1,0?ky nk ,.....,2? (3.8) 0?iC ni ,.....,1? (3.9) In constraint (3.2), the completion time of the job in position one is equal to the processing time of the job assigned to position one. Before the first position, there is no rma ( 01?y ). In constraint (3.3), the completion time of the job in position i is equal to the completion time of the job in position 1?i plus the processing time of the job assigned to position i plus the rma time if assigned. In constraint (3.4), each job is assigned to exactly one position. In constraint (3.5), each position is scheduled for only one job. Constraint (3.6) 69 requires an rma to be done in the related position if jobs are scheduled after rma and to control the sequence of the rma. Lastly, constraints (3.7), (3.8) and (3.9) indicate the decision variables are binary and all other variables are non-negative. 4. Criterion In this paper we focus on four different objectives which are to minimize total flow time, total tardiness, maximum tardiness and number of tardy jobs. Different combinations of two of these criteria are studied. The mathematical formulation for each criterion is given below. 4.1. Total Completion Time Minimizing flow time keeps the work-in-process inventory at a low level. Also, it minimizes completion times, lateness and job waiting times. It is defined as: ??? ni iCz 1min (4.1) Subject to: Constraint sets (3.2), (3.3), (3.4), (3.5), (3.6), (3.7), (3.8) and (3.9) respectively. 4.2. Total Tardiness Minimizing total tardiness reduces penalties caused by late jobs. Let jT be the tardiness of jobj . ??? nj jTz 1min (4.2) 70 Subject to: Constraint sets (3.2), (3.3), (3.4), (3.5), (3.6), (3.7), (3.8), (3.9) and iii dCT ?? ni ,..,1? (4.3) 4.3. Maximum Tardiness Minimizing maximum tardiness is a measure of customer satisfaction based on due dates. maxmin Tz? (4.4) Subject to: Constraint sets (3.2), (3.3), (3.4), (3.5), (3.6), (3.7), (3.8), (3.9) and ii dCT ??max ni ,..,1? (4.5) 4.4. Number of Tardy Jobs Often used in real applications, we try to finish as many jobs as possible on time because of the penalty costs. ? ?? n i iNz 1min (4.6) Subject to: Constraint sets (3.2), (3.3), (3.4), (3.5), (3.6), (3.7), (3.8), (3.9) and ii TMN? ni ,..,1? (4.7) ? ?1,0?iN ni ,..,1? (4.8) M is a very big number. 4 5. Computational Experiments 71 To understand the behavior of the mathematical model, three approaches are used. The proposed mathematical model is coded using AMPL and solved by CPLEX 9.1 on a computer with Pentium IV 2.8 GHz processor and 1GB of RAM. We perform an empirical study of the three bi-criteria approach. In the next subsection, we describe how we generate the data. And then we give results and analysis of experiments. 5.1. Data Generation In our experiments, we consider 25 and 50 jobs. Job processing times are generated from a uniform distribution on the interval [1-50]. To generate the due dates, we use ? and R based on Huo et al. (2007) which denote the due date range and tardiness factor respectively. To generate each job?s due date, we use a discrete uniform distribution with intervals )2/1()2/1( 11 RpandRp nj jnj j ???? ?? ?? ?? . Table 23 gives problem parameters. Table 23. The Parameter of the Problem Parameter Values jp U~ [1-50] jobsof# 25 and 50 ? 0.025, 0.05, 0.075 q 2, 5, 8 (min.) ? 0.25, 075 R 0.25, 0.50 iw 75.0,50.0,25.0 72 Ten replications of each of the possibilities were run for each combination of performance measure. Totally, 540 instances were generated. The results and analysis of experiments are given in the below. 5.2. Bi-criteria Approach One of the commonly used methods in bi-criteria is the Pareto curve. In this method, solution 1s is dominated by solution 2s , if 2s is not worse than 1s in all objectives and if 2s is strictly better than 1s for at least one of the objectives. This solution is called non- dominated and the set of non-dominated solutions in the feasible problem space is the Pareto optimal set. To try to find efficient Pareto curve we have plotted the 25 points which are our objective functions. These points lie on the objective function line. To obtain these points, we use 25 jobs with 0.025 deterioration rate. All other parameters are the same. 0.00 10000.00 20000.00 30000.00 40000.00 50000.00 60000.00 70000.00 80000.00 0.00 20.00 40.00 60.00 80.00 100.00 120.00 140.00 160.00 Total Flow Time 73 Figure 1. Pareto Curve for ????? TFrmp jiij ,/,)1(/1 1? Non-dominated means that there is no other solution in which one objective function can be improved without a simultaneous detriment to the other objective. In Figure 1, each of these points determines the extreme points of the dominated set in the decision space. All points are equally acceptable as the solution to the bi-criteria optimization problem. But, the decision maker should select only one solution for practical purposes. Therefore, the decision maker may choose a schedule that provides a more balanced performance of the two criteria employed. 5.3. Secondary Objective Approach For the secondary objective, we solve in two stages. First, optimize the primary criterion and then solve the secondary criterion with the constraint that value of the primary criterion is equal to its optimal value. Tables 24 and Table 25 show the computational time and given an rma of the ???? UTrmp jijij |/,)1(/1 m a x1? and ????? FTrmp jijij |/,)1(/1 1? respectively. Table 24. Average Run Time (sec.) for ???? UTrmp jijij |/,)1(/1 m a x1? Jobs numb. Det. Rate Rma time Ave. Comp. Time (sec.) Num. of Rma 0.025 2 5.7 9 0.025 5 5.6 9 0.025 8 5.9 9 0.05 2 6.2 10 25 0.05 5 6.3 10 0.05 8 6.1 10 0.075 2 8.6 11 0.075 5 8.5 12 0.075 8 8.8 12 0.025 2 18.7 20 0.025 5 19.0 21 0.025 8 19.4 21 74 0.05 2 22.2 22 50 0.05 5 24.3 22 0.05 8 24.1 23 0.075 2 28.5 24 0.075 5 28.7 24 0.075 8 29.4 24 Table 25. Average Run Time (sec.) for ????? FTrmp jijij |/,)1(/1 1? Jobs numb. Det. Rate Rma time Ave. Comp. Time (sec.) Num. of Rma 0.025 2 19.1 8 0.025 5 19.8 8 0.025 8 20.2 8 0.05 2 22.9 8 25 0.05 5 23.3 8 0.05 8 23.4 9 0.075 2 26.6 9 0.075 5 27.1 10 0.075 8 28.5 10 0.025 2 32.9 17 0.025 5 32.7 17 0.025 8 34.3 16 0.05 2 36.8 17 50 0.05 5 37.8 18 0.05 8 39.1 18 0.075 2 38.4 19 0.075 5 39.9 19 0.075 8 40.9 19 Based on the tables, the number of rmas is based on both deterioration rate and rma time. A larger deterioration rate results in more rmas. It is obvious that for larger rma times, larger computation time is needed. 75 5.4. Weighted Method The two objectives can be optimized at the same time by assigning proper weights in the weight method. Mathematically, the weighting method can be stated as follows: )()1()()(m i n 2111 xzwxzwxz ??? )1.5( We use three different values of )75.0,50.0,25.0(iw in our calculations. The extension of weight ranges is important for the stability of solution. Before using Equation 5.1, we normalize our objective function values to obtain reliable results. Normalization In practice, multiple objectives have different dimensions and it is difficult to compare different objective types. The individual preferences of the objectives are described by weights. These weights are assigned by the decision maker. But assigning proper weights is difficult and may cause problems. To prevent problems, normalization of objectives is necessary to get reliable solutions. Normalization of different objectives permits comparison of various dimensions and to find the relationship between different objectives. In our data set, normalization is necessary. We transform the data into a range between 0 and 1. The normalization of the objective function values are found by using; LiUi Lii i zz zxft ??? )( (5.2) where ?)(xfi original value , 76 ))((max xfz iUi ? , ))((min xfz iLi ? , ?it transformed value. This value provides the best normalization results as we normalize the objective functions by the true intervals of their variation over the Pareto Optimal set. After normalization, we run our new data set and obtain Tables 26 and 27. Table 26. Weighted Method for ),(/,)1(/1 1 FTfrmp jijij ??? ? Jobs numb . Det. Rate Rma time 25.01 ?w 5.01?w 75.01 ?w Ave.Flow.T (sec.) Num.of rma 0.025 2 6007.1 4257.2 2507.3 2.2 9 0.025 5 6192.9 4388.5 2584.1 3.1 5 0.025 8 6322.3 4480.5 2638.6 3.3 4 0.05 2 6295.4 4446.4 2597.3 3.5 10 25 0.05 5 6575.01 4643.1 2711.2 3.6 7 0.05 8 6770.1 4780.6 2790.8 3.6 4 0.075 2 6467.4 4573.8 2680.1 3.9 19 0.075 5 6808.1 4811.8 2818.5 4.1 13 0.075 8 7034.2 4973.48 2912.2 4.0 9 0.025 2 24789.9 17060.5 9331 18.3 16 0.025 5 25499.6 17547.8 9595.9 21.5 14 0.025 8 25943.7 17851.7 9759.6 19.5 10 0.05 2 16395.8 11315.5 6235.2 18.2 20 50 0.05 5 17197.9 11866.8 6532.7 23.6 13 0.05 8 17717.2 12261.3 6751.2 21.1 10 0.075 2 14993.8 9674.1 4949.4 21.6 28 0.075 5 15108.7 11716.9 5432.7 22.7 22 0.075 8 15473.9 11920.3 5748.1 24.1 16 77 Table 27. Weighted Method for ),(/,)1(/1 m a x1 UTfrmp jijij ??? ? Jobs numb. Det. Rate Rma time 25.01 ?w 5.01?w 75.01 ?w Ave. Comp. Time (sec.) Num. of rma 0.025 2 8857.2 6675.3 4964.2 6.2 8 0.025 5 8909.1 6818.1 4997.6 6.1 6 0.025 8 9121.7 6908.6 5271.9 9.7 5 0.05 2 7995.3 5881.3 4495.4 14.5 12 25 0.05 5 8093.1 5934.2 4214.6 20.1 10 0.05 8 8380.6 5534.9 3984.3 20.2 9 0.075 2 7307.8 4983.4 3439.5 9.9 15 0.075 5 7495.5 4811.8 3692.4 20.2 13 0.075 8 7693.9 4731.5 3934.5 21.2 10 0.025 2 25822.2 16346.7 13488.7 58.3 20 0.025 5 26981.7 16984.6 14989.1 89.5 18 0.025 8 27349.4 17964.2 15349.1 89.5 15 0.05 2 22901.6 11594.7 8320.9 28.2 26 50 0.05 5 23714.5 13688.7 9341.3 56.6 25 0.05 8 26341.8 14143.8 9918.6 61.1 22 0.075 2 19737.0 9985.2 8374.9 11.6 30 0.075 5 23813.7 10671.1 8964.1 32.7 26 0.075 8 25749.1 13462.7 10438.6 45.1 25 Tables 26 and 27 show a summary of the computational results. Problems with 75.0?w have the smallest objective function. As rma time and deterioration rate get bigger, the objective function gets bigger for the same weights. If we fix rma time, the objective function increases as the deterioration rate increases. The decision manager can make his/her decisions quickly and control their manufacturing systems by choosing proper weights. 6. Conclusions This is the first study on bi-criteria scheduling with deteriorating jobs and rate- modifying-activity. We address a real-life scheduling problem with periodic maintenance 78 activity. In reality, scheduling maintenance will result in some jobs being tardy and a larger flow time. Thus, the bi-criteria used in this study are minimize total flow time with total tardiness, and minimize maximum tardiness with number of tardy jobs. Generally, mathematical models have not been used extensively for scheduling problems. In this study, all combinations are studied with the proposed mathematical programming model. This is the first study which uses all three approaches to analyze the efficiency of the mathematical model with bi-criteria objectives. First, we use the model to find the Pareto Curve for both objectives, so a manager can make his decision from points on the curve. Then we use secondary objective method. Computational results show that the solution of the problem is dependent on the number of jobs and the other parameters of the problem. Although, 50 job problems are solved in around one minute, exponential growth in solution times makes larger problems much harder to solve. Lastly, we use weighted method to analyze model. 79 References 1. Azizoglu, M., Kondakci, S. and Kirca, O. (1991). Bicriteria scheduling problem involving total tardiness and total earliness penalties. International Journal of Production Economics, 23, 17-24. 2. Bacghi,U. and Ahmadi, R. H. (1987). An improved lower bound for minimizing weighted completion times with deadlines. Operations Research, 35, 311-313. 3. Baker K.R. and Scudder G.D. (1990). Sequencing with earliness and tardiness penalties: A Review. Operations Research, 38 (1), 22-36. 4. Bansal, S. P. (1980). Single machine scheduling to minimize the weighted sum of completion times with secondary criterion: A branch and bound approach. European Journal of Operational Research, 5, 177-181. 5. Browne S. and Yechiali U. (1990). Scheduling deteriorating jobs on a single processor. Operations Research, 38, 495-498. 6. Burns, R. N. (1976). Scheduling to minimize weighted sum of completion times with secondary criteria. Naval Research Logistics Quarterly, 23-1,125-129. 80 7. Chen, W.-J. (2007). Minimizing total flow time and maximum tardiness with periodic maintenance. Journal of Quality in Maintenance Engineering, 13-3, 293-303. 8. Chen, C. L. and Bulfin, R. L. (1993). Complexity of single machine, multi-criteria scheduling problems. European Journal of Operational Research, 70, 115-125. 10. C.L. Chen and R. L. Bulfin (1994). Scheduling a single machine to minimize two criteria: Maximum tardiness and number of tardy jobs. IIE Transactions, 26, 76-84. 11. Emmons, H. (1975). A note on a scheduling problem with dual criteria. Naval Research Logistics Quarterly, 22, 615-616. 12. Emmons, H. (1975). One machine sequencing to minimize mean flow time with minimum tardy. Naval Research Logistics Quarterly, 22, 585-592. 13. Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy, K. A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A Survey. Annual Discrete Mathematics, 5, 287?326. 14. H. Heck and Roberts S. (1972). A note on the extension of a result on scheduling with secondary criteria. Naval Research Logistics Quarterly, 19, 403-405. 15. Hino C.M., Ronconi D.P., Mendes A.B. (2005). Minimizing earliness and tardiness penalties in a single machine problem with a common due date. European Journal of Operational Research, 160,190-201. 81 16. Huo Y., Leung, J.Y.T. and Zhao, H. (2007). Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness. European Journal of Operational Research, 177, 116-134. 17. Kondakci, S., Azizoglu, M. and Koksalan, M. (1996). Note: Bicriteria scheduling for minimizing flow time and maximum tardiness. Naval Research Logistics, 43, 929-36. 18. Lee, C.Y and Lin, C.S. (2001). Single-machine scheduling with maintenance and repair rate-modifying activities. European Journal of Operational Research, 135, 493-513. 17. Miyazaki, S. (1981). One machine scheduling problem with dual criteria. Journal of the Operations Research Society of Japan, 24-1, 37-50. 19. Mondal S.A and Sen A. (2001). Single machine weighted earliness-tardiness penalty problem with a common due date. Computers and Operations Research, 28, 649-669. 20. Nelson, R.T., Sarin, R.K. and Daniels, R.L. (1986). Scheduling with multiple performance measures: The one-machine case. Management Science, 32, 464-480. 21. Posner, M. E., (1985). Minimizing weighted completion times with deadlines. Operations Research, 33, 562-574. 82 22. Potts, C. N. and Van Wassenhove,L. N. (1983). An algorithm for single machine sequencing with deadlines to minimize total weighted completion time. European Journal of Operational Research, 12, 379-387. 23. Shanthikumar, J. G. and Buzacott, J. A. (1982). On the use of decomposition approaches in a single machine scheduling problem. Journal of the Operations Research Society of Japan, 25, 29-47. 24. Shanthikumar, J. G. (1983). Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number tardy. Computers and Operations Research, 10, 255-266. 25. Smith, W.E. (1956). Various optimizers for single state production. Naval Research Logistics Quarterly, 3, 59-66. 26. Van Wassenhove, L. N. and Gelders, L.F. (1980). Solving a bicriterion scheduling problem. European Journal of Operational Research, 4, 42-8. 27. Wen-Jinn, C. (2007). Minimizing total flow time and maximum tardiness with periodic maintenance. Journal of Quality in Maintenance Engineering, 13 (3), 293-303. 83 CHAPTER 5 CONCLUSIONS Minimizing completion time and makespan are important objectives for managers. The purpose of this dissertation is to increase producer and customer satisfaction by decreasing completion time of the jobs while considering some real life assumptions. To do this, we need to decide job positions and, if needed, when to do maintenance. In this dissertation, we studied scheduling jobs and preventive maintenance under two new phenomena in the scheduling literature. First is a deteriorated job. Deteriorating jobs are tasks which need more time and effort to complete the process than when they are done earlier. Deterioration of the jobs is commonly due to machine wear. To prevent wear there is an activity called a rate-modifying activity (rma). Rma is also a new phenomena in scheduling problems. We presented a simple integer programming formulation to minimize makespan, total completion time, or total weighted completion to consider these two phenomena. In real life problems there may be many jobs, so we proposed a number of heuristic algorithms to solve larger problems in reasonable computational time. 84 In Chapter 2, the main concepts of our problem are introduced and a detailed overview of its literature is given. The main mathematical model is developed. We presented polynomial time algorithms for makespan objective when the jobs have equal processing times. We developed heuristics for both objectives. Three different experiments are done to analyze performance of the mathematical model and heuristics. As the computational experiments show, heuristics are very fast and provides close-to optimal solutions for both objectives. The behavior of the proposed heuristics performs well in terms of the execution time and the size of the problems. In Chapter 3, an extended mathematical model is proposed. In this model, our processor is a worker who tires. We consider the physiological factors of the worker and added some new physiological constraints to our model. We proved that the problem and m a x1 |,,)1(|1 Cphyrmpp jijij ??? ? and ???? ijijij Cphyrmpp |,,)1(|1 1? is hardNP? . The reduction is based on the Equal-Size-Partition problem. For large problems, we developed an efficient heuristic for both makespan and total completion time objectives. According to numerical experiments, the heuristic is very effective for small to large size of problems and it yields much shorter run time when the problem size is large. In Chapter 4, we provided a bi-criteria mathematical model under the same assumptions. The mathematical model is studied for two different objective sets; ???? UTrmpp jijij |/,)1(/1 m a x1? and ????? TFrmpp jijij |/,)1(/1 1? . To analyze the efficacy of the mathematical model, we use three different approaches. In the bi-criteria approach, the extreme points of the dominated set in the decision space on a Pareto Curve are generated. Then, a secondary approach is used to compare both objectives. Lastly, the weighted method is used to analyze the mathematical model. 85 In this dissertation, we have shown promising results for special scheduling problems. There is, of course, more research to be done. We would like to extend our problem to consider learning effect phenomena. Also, we could extend the problems to multiple machine settings. Lastly, possible research directions should be including other scheduling objectives and other processor environments.