ابتکارات برای مشکلات برنامه ریزی شغلی ثابت عملیاتی با کار و گسترش محدودیت های زمانی

Operational fixed job scheduling problems select a set of jobs having fixed ready and processing times and schedule the selected jobs on parallel machines so as to maximize the total weight. In this study, we consider working time and spread time constrained versions of the operational fixed job scheduling problems. The working time constraints limit the total processing load on each machine. The spread time constraints limit the time between the start of the first job and the finish of the last job on each machine. For the working time constrained problem, we present a filtered beam search algorithm that evaluates the promising nodes of the branch and bound tree. For the spread time constrained problem we propose a two phase algorithm that defines the promising sets for the first jobs and finds a solution for each promising set. The results of our computational tests reveal that our heuristic algorithms perform very well in terms of both solution quality and time.

Fixed job scheduling (FJS) is an applied area of scheduling where tasks (jobs) with specified weights, ready times and deadlines are to be processed on parallel resources (machines). A task can be processed only between its ready time and deadline, and its processing time is exactly equal to the difference between these. The FJS problems are of two types: operational and tactical. The tactical fixed job scheduling (TFJS) problems aim to minimize the number or cost of the resources while processing all tasks. The operational fixed job scheduling (OFJS) problems aim is to select a subset of tasks for processing so that the total weight is maximized. The FJS problems have many application areas in manufacturing and service operations as mentioned in many reported work. Kovalyov et al. (2007) and Kolen et al. (2007) survey the potential applications of the FJS problems together with their theory. Bekki and Azizoglu (2008) study the OFJS problem on uniform parallel machines. Kroon (1990) and Kroon et al. (1995) mention the applications in assigning aircrafts to gates, and the capacity planning of maintenance personnel. Fischetti et al., 1987 and Fischetti et al., 1992 and Martello and Toth (1986) consider an application of the TFJS problem in scheduling the bus drivers whereas Wolfe and Sorensen (2000) consider an application of the OFJS problem in scheduling the earth-observing satellites. Other cited application areas include class scheduling (Kolen and Kroon, 1991), satellite data transmission (Faigle et al., 1999) and printed circuit board manufacturing (Spieksma, 1999). The machine operating time constraints in FJS are introduced by Fischetti et al., 1987 and Fischetti et al., 1989. These constraints are of two types: working time and spread time. Working time constraints impose a limit on the processing load of each machine, letting no machine operate for more than T time units. Spread time of a machine is defined as the time between the start of its first operation and the finish of its last operation, including the idle times in between. The spread time constraints limit this time span with an upper bound, S. The operating time constraints find their applications in both manufacturing and service operations. In manufacturing environments, it may not be economical to operate some high-precision/high-cost equipment for more than a prespecified time (working time) and/or the machines may be available for a particular specified time period (spread time). In service environments like car rental systems, hotel room reservations and personnel scheduling, the resources may have operation time constraints imposed by the technical or union regulations. Fischetti et al. show that the TFJS problems with working time and spread time constraints are strongly NP-hard, in their 1987 and 1989 studies, respectively. They develop lower bounds and branch and bound (B&B) algorithms and report on their satisfactory average-case performances based on the data generated close to the real-life situations. In their study, Fischetti et al. (1992) provide several polynomial time heuristic algorithms for both problems and report on their satisfactory worst-case performances. The research on the OFJS problem with operating time constraints is very limited despite its practical importance. Bouzina and Emmons (1996) study the OFJS problem under working time constraints. The authors prove that the preemptive problem is polynomially solvable when all job weights are equal; however it is NP-hard in the ordinary sense when the job weights are arbitrary. The OFJS problems with spread time and working time constraints are studied by Eliiyi and Azizoglu in their 2006 and 2010 studies, respectively. They show that both problems are NP-hard in the strong sense and report their several polynomially solvable special cases. They propose B&B algorithms with several problem size reduction mechanisms and dominance conditions. For both problems, the algorithms return optimal solutions for problem instances with up to 100 jobs and 4 machines. Solyali and Ozpeynirci (2009) study the OFJS problem with spread time constraints, and develop a branch and price algorithm that outweighs the B&B algorithm proposed by Eliiyi and Azizoglu (2006). Very recently Rossi et al. (2010) develop two heuristic algorithms, namely greedy heuristic and genetic algorithm and report on the satisfactory behavior of their algorithms. In this study, we consider the OFJS problem with working time and spread time constraints. For each problem, we develop several heuristic procedures that use efficient upper bounds and dominance conditions. Our aim is to find powerful lower bounds in reasonable times. There are two heuristic procedures that consider the spread time constraints (Rossi et al., 2010). We compare the performance of our heuristic algorithm with those procedures. Our computational study reveals that our algorithm outweighs greedy heuristic over all problem instances; however the genetic algorithm slightly outweighs our algorithm. To the best of our knowledge there is no reported heuristic study for the OFJS problem with working time constraints. As both problems have many practical applications and are to be solved quite frequently, our study fills an important gap in the literature and can be used for large problem size instances conveniently. The rest of the paper is organized as follows. We present the mathematical formulations of the problems in Section 2. We present our heuristic algorithms in Sections 3 and 4. Section 5 presents the results of our computational study designed to evaluate the performances of the algorithms. The conclusions are discussed in Section 6.

In this study we consider the operational fixed job scheduling problem under working time and spread time constraints. Both problems have important practical implications, and are shown to be NP-hard in the strong sense. We develop several polynomial time heuristics for both problems that employ powerful bounding procedures and reduction properties. An extensive computational study is carried out to observe the performances of the algorithms compared to the optimal solutions. Our algorithms perform very well for problems up to 100 jobs and 4 machines and 250 jobs and 3 machines, for the OFJSS problem and up to 500 jobs and 10 machines for the OFJSW problem. The computation times do not increase significantly with the problem size, hence the instances with many more jobs and machines could be solved. As the problems have many practical applications and are likely to be solved frequently due to their operational nature, our approximation algorithms may prove quite useful for practitioners. Our algorithms can be modified to the operational fixed job scheduling problems where working time and spread time constraints are imposed simultaneously.