الگوریتم های ژنتیکی برای برنامه ریزی دستگاه منفرد با زوال وابسته به زمان و فعالیت های اصلاح نرخ

In this paper, the integration of two emerging classes of scheduling problems, the class of scheduling problems with time-dependent deterioration and the class of scheduling problems with rate-modifying activities, are addressed. The scheduling problems have been studied independently. However, the integration of these classes is motivated by human operators of tasks who have fatigue while carrying out the operation of a series of tasks. This situation is also applicable to machines that experience performance degradation over time due to mal-position or mal-alignment of jobs, abrasion of tools, and scraps of operations, etc. It requires maintenance in order to sustain acceptable production rates. We consider the single machine scheduling problem with time-dependent deterioration and multiple RMAs. A mathematical model for an optimal solution to minimize the makespan is derived and genetic algorithms are proposed. The performance of the genetic algorithms is evaluated using randomly generated examples.

In the classical scheduling, the common assumption is that processing times of the jobs are fixed and known a priori with certainty. In practice, however, machine production rate becomes less than normal due to a mal-position of tools, mal-alignment of jobs, abrasion of tools, and scraps of operations, etc. In these situations, the processing time of the jobs increases depending upon the sequence of jobs or the starting time of jobs. Such problems are generally known as machine scheduling problems with deterioration. The deteriorated processing time of jobs is recovered to an original processing time by the maintenance or cleaning process of machines. The recovering process bringing back to a normal processing time is called rate-modifying activity (RMA) (Lee & Leon, 2001). The phenomenon known as deterioration has been received increasing attention over the last two decades in recent years, after pioneering efforts of scheduling models by Gupta and Gupta (1988) and Browne and Yechiali (1990). They considered a single machine scheduling problem with deteriorating jobs. Gupta and Gupta (1988) introduced a single machine scheduling problem with the processing time of a task being a polynomial function of its starting time. Browne and Yechiali (1990) considered a single machine scheduling problem with the job processing time of a task being a non-decreasing with start time-dependent linear function. Alidaee and Womer (1999) reviewed a comprehensive review of job processing time is time-dependent and provide various forms of the function of processing time including linear, piecewise linear, and nonlinear. Their work demonstrated the majority of the literatures for the processing time function with single machine environment. Cheng, Ding, and Lin (2004) also surveyed a class of machine scheduling problems in which processing time of a task is dependent on its starting time in a schedule. They classified scheduling problems with various time-dependent deterioration functions and provided a framework to illustrate how models for the class of problems have been generalized from the classical scheduling theory. Cheng and Ding (2000) proposed a single machine scheduling model to minimize makespan with deadlines and increasing rates of processing times. They found that both problems are solvable by a dynamic programming algorithm. Bachman, Janiak, and Kovalyov (2002) proved the NP-hardness of total weighted completion time for single machine scheduling in which the job processing times are decreasing linear functions dependent on their start times. Wang, Sun, and Sun (2011) studied single-machine total completion time scheduling with a time-dependent deterioration. They proposed two heuristic algorithms utilizing the V-shaped property. Since the complexity of the problem remains open, they compared the worst case error bound using SPT with two proposed heuristics. Several research focus on developing meta-heuristics. Shin, Kim, and Kim (2002) presented a heuristic and tabu search algorithm for the single-machine scheduling problem with sequence-dependent setup times, release times, and due dates, with the objective function of minimizing the maximum lateness. Stecco, Cordeau, and Moretti (2009) developed a tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine. Bahalke, Yolmeh, and Shahanaghi (2010) proposed several hybrid meta-heuristic algorithms for the single-machine scheduling problem with sequence dependent setup time and deteriorating jobs, with minimize makespan. Meanwhile, in RMA, Lee and Leon (2001) initially introduced a single machine scheduling with a RMA. They assumed that one rate-modifying activity which changes the production rate of equipment was included during the planning horizon. Given a set of jobs to be performed by a resource and an RMA of fixed length that recovers the processing rate of the resource, they determined (i) the sequence in which the jobs should be performed and (ii) when to schedule the fixed length RMA so that the objective of the scheduling is optimized. They separately classified the scheduling problem to following four objective functions: makespan, total completion time, total weighted completion time, and maximum lateness and each of the cases propose a dynamic programming algorithm after they found optimality properties. Qi, Chen, and Tu (1999) considered a single machine problem with the possibility for multiple maintenance activities, but during scheduling period they ignored the deterioration of processing time for jobs. Lee and Lin (2001) considered single machine scheduling problems involving repair and maintenance activities. They derived optimal policies for scheduling fixed length RMAs and job sequencing in an environment by machine breakdowns. Mosheiov and Sarig (2009) analyzed a single machine scheduling determining both sequencing of jobs and positioning of a RMA with common due-window assignment. Lee and Chen (2000) studied a parallel scheduling problem assuming that single RMA was processed for each machine in entire planning horizon. Zhao, Tang, and Cheng (2009) presented two parallel machines to minimize the makespan assuming that single RMA was processed for each machine. Iranpoor, Ghomi, and Zandieh (forthcoming) presented a single machine scheduling problem with sequence-dependent setup times and single RMA. A review of the above literature reveals that most of studies only focused on machine scheduling problems with deterioration or machine scheduling problem with RMAs, even if the deterioration of jobs and RMAs are interrelated with each other. Lodree and Geiger (2010) studied scheduling problems integrated with time-dependent processing times and single RMA. Under a certain condition, they provided the optimal policy determining optimal position of RMA and sequencing of jobs. Zhao and Tang (2012) considered single machine scheduling problem with positioning of single RMA and deterioration of jobs. Lodree and Geiger (2010) and Zhao and Tang (2012) defined RMA as an activity changing the normal processing times of the jobs following this activity, and assumed that the processing time of a job is a linear function of its starting time and the job-independent deterioration rates are identical for all jobs. Kim and Joo (2011) studied single machine scheduling model with multiple RMAs and the deterioration of jobs nonlinearly increased by the difference between the position of the job and the previous RMA. In their study, the RMAs are defined as a recovering process bringing back to a normal processing time. In this study, single machine scheduling problem with time-dependent deterioration and multiple RMAs are considered. The RMAs are defined as a recovering process bringing back to a normal processing time like Lee and Leon (2001) and Kim and Joo (2011). There are N independent jobs to be scheduled. Job j has original processing time pj and time-dependent deterioration rate rj. The actual processing time of job j is increased (deteriorated) depending upon the gap xj between recent RMA and starting time of the job, hence the time becomes pj+rjxjpj+rjxj. The deteriorated processing time of jobs is recovered to an original processing time by RMAs. The RMA time Q is assumed to be fixed. The working horizons between RMAs including horizons before the first and after the last RMAs are called buckets in this paper. The goal of the problem is to find a schedule minimizing the makespan which is the sum of each completion time Ck of all the assigned jobs in k th bucket and all RMA times. The schedule includes the assigning jobs to buckets and the sequencing of assigned jobs in each bucket, along with the positions of RMAs. Fig. 1 describes the scheduling of jobs in the example.The paper organized as follows. Section 2 presents the notations and a mathematical model finding the optimal solution for the problem. Three genetic algorithms (GAs) are proposed with different chromosome representations in Section 3. In Section 4, the performances of the GAs are evaluated through computational experiments. Finally, summary and further research areas are reviewed in Section 5.

In this paper, problems dealing with the integration of two emerging classes of scheduling problems, which are the class of scheduling problems with time-dependent processing times and the class of scheduling problems with rate-modifying activities (RMAs) are examined. The objective of the study is to find a schedule minimizing the makespan. The schedule includes the assigning jobs to buckets and the sequencing of assigned jobs in each bucket, along with the positions of RMAs. A mixed integer programming model is derived to search the optimal solution. While CPLEX can be used for solving models of small sized problems, it is inefficient and impractical for solving large sized problems due to the increased computational time requirement. In this paper, GAs with three different chromosome representations are proposed to increase solution efficiency: GA using chromosomes with special character (GA_SC), GA using chromosomes with truck sequence and door assignment (GA_DS), and intelligent GA using simple chromosomes with dispatching rule (GA_DR). The GAs are implemented to evaluate the performances of chromosome designs. The test results conclude that among all the implemented algorithms for machine scheduling problems with time-dependent deterioration and multiple RMAs, GA_DR provides the highest quality performance, in both effectiveness and efficiency.