Single machine scheduling with periodic machine availability

Single Machine Scheduling with Periodic Machine Availability ∗ Paz Perez-Gonzalez1, Jose M. Framinan1 1Industrial Management, School of Engineering, University of Seville, Ave. Descubrimientos s/n, E41092 Seville, Spain, {pazperez,framinan}@us.es Abstract In this paper we address the problem of scheduling jobs on a single machine with cyclical machine availability periods. In this problem, the scheduling horizon is composed of periods where the machine is available followed by other periods where no operation can be performed. In the literature, the problem is denoted as scheduling with periodic maintenance, as it is usually assumed that these unavailability periods are employed to perform maintenance activities. Another situation is the one inspiring our research, i.e. the need of completing manufacturing operations within a shift. More specifically, we focus the single machine scheduling problem with makespan objective subject to periodic machine availability. There are several contributions proposing approximate procedures due to the NP-hardness shown for the problem. However, we are not aware of a computational evaluation among these procedures. Furthermore, the problem is similar to the classical bin packing problem, so it is of interest to explore the relation between both problems. In this paper, we address these two issues, and propose new approximate solution procedures for the problem. Keywords: Single machine scheduling, makespan, Heuristics, periodic maintenance, periodic machine availability ∗This is an Accepted Manuscript of an article published by Elsevier in Computers and Industrial Engineering Volume 123, September 2018, Pages 180-188, available online: http://dx.doi.org/10.1016/j.cie.2018.06.025 1 1 Introduction In many manufacturing companies, operations are not performed continuously over the scheduling horizon, since resources stop cyclically due to the end of the shifts, hours/days off (e.g. nights or weekends), periodic maintenance activities, etc. Regardless the cause of the unavailability of the resources, this problem is known in the literature as scheduling with periodic maintenance (Low et al., 2010a; Yu et al., 2014). In our case, the research is inspired by a manufacturing process within the aerospace industry, more specifically the assembly of wiring harness. This rather complex operation is performed manually by specialized teams, and it is not desirable that a task started by one team is completed by another, as this usually decreases the efficiency and quality of the task. Therefore, schedules are built so all tasks starting within a working shift must be also completed in this shift. Our objective is to minimise the maximum completion time across all jobs, or makespan. Note that this problem is NP-hard in the strong sense when cyclical availability periods are included (Lee, 1996), even if its classical counterpart is trivial. For this problem, several approximate solution procedures, many of them based on bin packing methods, have been presented in the literature: Ji et al. (2007); Hsu et al. (2010); Yu et al. (2014) develop several constructive heuristics and Low et al. (2010a) propose a metaheuristic. However, it seems that these procedures have been developed in an independent manner, and consequently no computational analysis has been carried out to compare them. Therefore, their relative efficiency has not been established and the state of the art remains unclear. Furthermore, the problem is clearly related to the well-known bin packing problem, however, such relationship has not been analysed in the literature. Our paper is aimed towards filling these gaps: First we explore the relations between the bin packing problem and our problem by comparing the solutions provided by mixed integer linear programming models for both problems. Second, we carry out a computational experimentation among the heuristics proposed in the literature for the problem under consideration. Based on the excellent results obtained by two fast constructive heuristics, we include them in a local search procedure and propose two new heuristics. The computational experience carried out shows that our proposals outperform the constructive heuristics and the metaheuristic existing for the problem while requiring less CPU time. 2 Figure 1: Proposed problem Ji et al. (2007) The rest of the paper is organised as follows. Section 2 includes the notation for the problem and the state-of-the-art. Section 3 describes the mathematical models employed to compare the bin packing problem and the proposed problem. In Section 4 we review and classify the constructive heuristics identified in the literature, and in Section 5 we describe the new heuristics proposed. In Section 6 we discuss the set of instances employed to carry out the computational experience, and present the results obtained. Finally, in Section 7 the main conclusions are presented, along with future research lines. 2 Problem statement and background The decision problem consists on scheduling njobs, J1, . . . , Jnon a single machine with processing times pj,j= 1, . . . , n. The machine is not available at any time in all the scheduling horizon, which is composed of availability periods of Ttime units followed by a non-availability period of ttime units (see Figure 1). In the literature, the availability periods are denoted batches, bins or blocks (we will use this last term in the paper). Jobs have non-resumable operations, so it has to be assumed that T≥ pj∀j= 1, . . . , n in order to guarantee the feasibility of the problem. Additionally, we consider makespan minimization, so this problem is denoted 1|nr −pm|Cmax by Ji et al. (2007) according to the standard notation. 1 means that we are considering a single machine layout, nr −pm indicates that periodical maintenance (pm) unavailability periods are considered as constraint, and jobs are non-resumable (nr), that means, jobs must not be interrupted (or if it, it must be completely processed again). Finally Cmax indicates that the minimization objective is the completion time of the last job in the machine. 3 For a given schedule, we denote the slack of a block as the idle time of each block, i.e. the difference between Tand the sum of the processing times of all jobs assigned to that block. Additionally, the load of a block refers to the total processing time of all jobs assigned to that block. To the best of our knowledge, the 1|nr −pm|Cmax problem was considered firstly by Ji et al. (2007). They propose an algorithm –labelled LPT (Longest Processing Time first)– consisting in first sorting the jobs in descending order of their processing times and then assigning them according to the First Fit bin packing policy, i.e, to the first block with sufficient slack. They also show that the worst-case ratio of the LPT algorithm is 2. Low et al. (2010a) propose a Particle Swarm Optimization (PSO) algorithm for the 1|nr − pm|Cmax problem. They use different constructive heuristics (for descriptions see Section 4) to generate an initial population with 10 individuals, and compare different versions of the PSO algorithm. From their experiments, it turns out that one of these versions yields the best results. Finally, Yu et al. (2014) provide three constructive heuristics for 1|nr−pm|Cmax, called LS, LPT and MLPT: The List Scheduling algorithm (LS) generates a random order and applies the already mentioned First Fit algorithm; LPT has been described previously since it was proposed by Ji et al. (2007). Finally, MLPT is an adaptation done by Yu et al. (2014) of a method originally applied to the bin packing problem by Yue and Zhang (1995). The complexity of these three algorithms is proved by Yu et al. (2014) to be O(n2), showing that all three have a worst case bound of 2. Additionally, they compare the performance bounds, concluding that MLPT is the best among them. However, they do not carry out computational experiments due to the theoretical approach of their paper. Other related problems have been addressed in the literature. Hsu et al. (2010) study a version of the problem where the machine stops for maintenance after Tunits of time or after processing Kjobs. Clearly, this problem is equivalent to 1|nr −pm|Cmax for K=n. For this problem, Hsu et al. (2010) present two approaches. Firstly, a two-stage BIP (Binary Integer Programming) model is proposed in order to optimally solve the problem. In this model, the authors determine the minimum number of blocks Lrequired for processing the njobs in the first stage and minimize the total slack within the first L−1 blocks (which is equivalent to minimize the makespan) in the second stage. Secondly, they present two heuristics. The first heuristic –called Decreasing order 4 with Best Fit– sorts the jobs according to LPT and then assigned them to the block with the current minimum slack, i.e. using the Best Fit bin packing policy. The second heuristic, called Butterfly order with Best Fit, sorts the jobs in the so-called butterfly order (given the jobs in LPT, select first the largest one, then the smallest, the second largest, the second smallest, and so on) and then applies the Best Fit bin packing policy. In their experiments, they show that the butterfly order performs better than the decreasing order when K≤ dn 2e, and the opposite otherwise. Low et al. (2010b) study another related problem where the periodic maintenance period are not fixed, but they are flexible, being each maintenance done within a given time window. Additionally, they include the same constraint considered by Hsu et al. (2010) regarding the maximum number Kof jobs assigned to an availability period. They propose six constructive heuristics obtained by combining a sequencing priority list (random order, SPT order and LPT order) with the First Fit or Best Fit policies. Additionally, they provide theoretical results about worst case ratios of some of the proposed algorithms for different special cases. The problem 1|nr −pm, sij|Cmax, with sij the sequence dependent setup-time of job ischeduled prior to job j, is studied by Angel-Bello et al. (2011) and Pacheco et al. (2012). Angel-Bello et al. (2011) develop a MILP (Mixed Integer Linear Programming) model and show that it can only be used for small-sized instances. Therefore, they propose a GRASP improved by a Tabu Search phase. Pacheco et al. (2012) provide a MILP too, and a Multi-Start Tabu algorithm (MST). The authors conclude that MST is better than the GRASP by Angel-Bello et al. (2011) for the biggest instances. Finally, additional contributions on scheduling with availability constraints can be consulted in Ma et al. (2009). After reviewing the literature, the following conclusions can be stated: On the one hand, to the best of our knowledge, the relationship between this problem and the well-known bin packing problem has been hardly studied. Ji et al. (2007) identify such relationship as the availability period can be seen as a bin with capacity T(see Figure 1). Taking into account Property 1 by Ji et al., 2007, the optimal schedule has the minimum number of blocks, corresponding to an optimal solution for the bin packing problem. Therefore, although both problems provide different solutions (since 1|nr −pm|Cmax tries to minimize the load of the last block), it might be that the solution of the bin packing problem can be used to obtain high-quality solutions for the 1|nr −pm|Cmax problem. 5 To analyse this issue, we propose a MILP model for the problem, and compare the results provided by this model with the results obtained by the mathematical model of the classical bin-packing problem. These models are presented in Section 3, and the computational results in Section 6. On the other hand, regarding to approximate methods, to the best of our knowledge there are no comparison assessing the performance of the different methods proposed. In addition, there has been no exhaustive analysis on whether different choices of sorting criteria would yield better results (for instance, the LS algorithm proposed by Yu et al., 2014 could be tested with the Best Fit bin packing heuristic as suggested by Low et al., 2010a instead of with the First Fit). Furthermore, the same method has been employed with different names, resulting in an unclear state of the art. Since most of the proposed methods follow the same structure, we believe that a template can be developed to classify existing methods. The template could also serve to identify unexplored combinations of heuristics to be tested. In Section 4, we present and classify these methods in order to carry out a computational evaluation in Section 6. As a result of these experiments, we detect some opportunities to develop fast heuristics to further improve the results obtained by existing methods. These proposals are presented in Section 5. 3 Mathematical model In this section we present two mixed integer linear programming (MILP) models: •BP-MILP model. This model, proposed by Martello, Silvano; Toth (1990) for the bin packing problem, and using the notation considered for the problem 1|nr −pm|Cmax, assigns the jobs to the blocks minimizing the number of blocks. •PM-MILP model. This model is an adaptation of the previous model for the problem 1|nr − pm|Cmax. For the PM-MILP model, we have not adapted the model by Hsu et al. (2010) since they consider the problem with a maximum number of jobs Kscheduled in each block, proposing a formulation based on two stages (i.e. they solve two models). The notation used for BP-MILP and PM-MILP models is the following: 6 •Data: –nthe number of jobs; –pjthe processing time of jobs, 1 ≤j≤n; –Tthe availability period (size of blocks). •Variables: –bibinary variables indicating if block iis occupied, 1 ≤i≤n; –xij binary variables indicating if job jis assigned to block i, 1 ≤j≤n, 1 ≤i≤n. Note that we do not consider the value of t(see Section 1) since it does not affect to the optimal solution, according to the aforementioned Property 1 by Ji et al. (2007). 3.1 BP-MILP model min n X i=1 bi(1) s.t. n X j=1 pjxij ≤Tbi,1≤i≤n(2) n X i=1 xij = 1,1≤j≤n(3) xij, bi∈ {0,1},1≤i, j ≤n(4) Equation (1) is the objective function to be minimized, i.e, the number of blocks to be occupied. Constraints (2) impose that the sum of the processing times of jobs assigned to the block imust be lower or equal to T, for all blocks. Constraints (3) impose that each job must be assigned to one and only one block, for all jobs. Finally, Constraints (4) define the binary variables used in the model. The solution obtained for this model is the assignment of jobs to blocks. In order to generate an (approximate) solution for the 1|nr −pm|Cmax problem, the makespan can be computed in the 7 following way: Let kbe the occupied block with lowest load, then the makespan is the number of occupied blocks minus one multiplied by Tplus the load the block kas it is shown in Equation (5). Cmax =T· n X i=1 bi−1!+ n X j=1 pjxkj (5) 3.2 PM-MILP model PM-MILP model is based in the previous model, but taking into account the following new information: Mis a parameter with a high value (M≥T), max slack is a continuous variable which computes the maximum slack (empty space) of the blocks, and finally δiare binary variables indicating if the maximum slack is given by the block i. min T· n X i=1 bi−max slack (6) s.t. n X j=1 pjxij ≤Tbi,1≤i≤n(7) n X i=1 xij = 1,1≤j≤n(8) max slack ≤M(1−δi)+T bi− n X j=1 pjxij,1≤i≤n(9) n X j=1 xij ≥bi,1≤i≤n(10) n X i=1 δi= 1 (11) δi≤bi,1≤i≤n(12) xij, bi, δi∈ {0,1},1≤i, j ≤n(13) max slack ≥0 (14) Equation (6) is the objective to be minimized, i.e, the makespan given by Tmultiplied by the number of occupied blocks minus the maximum slack of the blocks. Constraints (7) and (8) are the same constraints than Constraints (2) and (3) respectively. Constraints (9) set the maximum slack 8 among the used blocks. For each block, Constraints (10) imply that, if a block is not occupied, then no job is assigned to this block. Constraint (11) states that only one block provides the maximum slack, and Constraints (12) imply that, if a block is not occupied, then this block does not provide the maximum slack. Finally, Constraints (13) and (14) define the binary and continuous variables used in the model, respectively. It is clear that, among all optimal solutions for the BP-MILP model, the one containing the block with the greatest slack value is an optimal solution for the PM-MILP model. In this regard, the optimal solutions for the PM-MILP model are a subset of the optimal solutions for the BPMILP. Therefore, although both problems are different, it is possible that, in practice, the solutions provided by the two models are very similar, which would indicate that, essentially, the 1|nr − pm|Cmax problem is a bin packing problem and that solution procedures borrowed from the latter could be used to solve the former. This idea is used in the next section, where a constructive heuristic that employs concepts from the bin-packing problem is proposed for our problem. 4 Existing Heuristics: Analysis and Classification In this section, we classify the constructive heuristics from different authors into a common template. As a part of this classification effort, new variants of these constructive heuristics are proposed to be subsequently tested. The constructive heuristics employed in the literature consist of two phases. In the first phase, jobs are sorted by certain sorting criterion depending on the processing times of the jobs. In the second phase, a specific bin packing policy is adopted. Therefore, a general template for the constructive heuristics can be proposed to classify the existing heuristics for the problem. Regarding the first phase, without loss of generality, let us assume that the processing times of the jobs to be scheduled are given in non decreasing order, i.e. pi≤pi+1,i= 1, . . . , n−1. Therefore, the so-indexed jobs can be sorted according to the following sorting criteria: •Random (R), i.e. sorting the jobs randomly. •Decreasing (D), i.e. sorting the jobs according to the LPT (Longest Processing Time first) rule. More specifically: pn, . . . , p1 9 FFA, FFHILO, FFLOHI and MFFD), and the three versions of the new heuristic (NEW, NEW BF and NEW FF). We have solved all instances for all methods. Table 2 shows the ARPD values obtained for each heuristic for LOW and MOD sets of instances, for the different cases of nand the Total. ARPD results are shown graphically in Figures 3 and 4, giving the 95% confidence intervals for each method. It can be seen that, for both sets of instances, the best ARPD is obtained by MILP, although it does not provide the optimal values for all instances. In fact, in both set of instances, it does not provide the minimum for all instances, mainly for the biggest instances of MOD. The best heuristics among the tested algorithms are NEW BF and NEW FF. Note that NEW does not provide good results, so the Local Search is not the key aspect of our new heuristic, but its combination with the operators BF or FF. It is worth to note that the average ARPD of NEW BF is lower than that of the rest of the heuristics for all values of n. Note also that MFFD by Yu et al. (2014) provides the same results than FFD for LOW (ARPD are shown in the same row). The explanation is that both methods provide the same makespan values unless ∃pj>T 2. For MOD set of instances, these heuristics yield different ARPD values since this set of instances provides tighter values of T, and it can be seen that MFFD is not better than FFD. Regarding the computation times, only the best methods with the lowest ARPD values have been considered: BFD, FFD, MFFD, NEW BF, NEW FF and MILP. Table 3 shows the average for each value of n. It can be seen that the MILP is the slowest method, requiring more CPU times for MOD than for LOW. However MILP provides optimal solutions for LOW in less than one minute for sizes up to 80 jobs. The constructive heuristics are almost instantaneous, and, although the three new heuristics need higher computation times, these are negligible as compared to that required by MILP. For LOW, the average computation times for NEW BF and NEW FF are similar (2.183 and 2.112 respectively). In the case of MOD, the average computation times for LOW are 2.892 and 2.364 on average for NEW BF and NEW FF respectively. For both sets of instances, NEW FF is the fastest method. In order to see the ARPD differences in a clearer way, we analyse the seven algorithms with the lowest ARPD values. For LOW (see Figure 5), the best overall results are provided by MILP, although it requires much higher computation times than the rest (see Table 2). The best results 16 Figure 3: 95% Confidence Interval for ARPD: All heuristics and MILP. Case LOW Set of Instances among the heuristics are provided by NEW BF and NEW FF. These two heuristics are statistically significant different to the rest and have the lowest standard deviation, which highlights their robustness. A similar pattern can be observed for MOD (see Figure 6). The main differences are that, in this case, there are no statistically significant differences among MILP, NEW BF and NEW FF, and among FFD, BFD. Finally, the worst results are obtained by MFFD, being statistically significant. 17 N Method 10 20 30 40 50 60 70 80 90 100 150 200 250 300 Total LOW Set of Instances NEW 0.695 1.258 1.124 1.472 1.219 0.712 0.791 1.254 1.422 1.294 1.308 1.590 1.264 1.967 1.241 NEW BF 0.000 0.035 0.087 0.049 0.085 0.062 0.029 0.037 0.038 0.020 0.008 0.004 0.002 0.001 0.033 NEW FF 0.000 0.035 0.088 0.056 0.096 0.083 0.048 0.061 0.053 0.035 0.009 0.004 0.004 0.002 0.041 BFR 4.240 3.232 2.871 1.981 2.255 1.472 1.709 1.538 1.409 1.299 0.921 0.775 0.727 0.696 1.795 BFD 0.651 0.738 0.415 0.265 0.236 0.161 0.107 0.093 0.072 0.057 0.010 0.004 0.004 0.002 0.201 BFI 8.996 9.805 9.577 10.655 10.316 10.067 10.273 10.700 10.363 11.278 10.792 11.125 10.859 10.899 10.407 BFHILO 3.238 3.451 4.367 3.975 4.043 3.528 3.703 3.628 3.818 3.618 3.534 3.894 3.862 3.574 3.731 BFLOHI 3.858 3.539 4.066 4.130 4.558 3.955 3.815 4.187 3.971 3.694 3.576 3.879 3.865 3.529 3.902 BFV 5.929 5.168 5.094 5.752 5.578 4.885 5.109 5.233 5.282 5.562 5.332 5.544 5.391 5.348 5.372 BFA 1.639 1.450 1.035 0.781 0.621 0.458 0.281 0.305 0.336 0.217 0.109 0.087 0.053 0.034 0.529 FFR 4.240 3.274 3.006 2.041 2.289 1.589 1.775 1.620 1.465 1.409 1.044 0.985 0.809 0.796 1.882 FFD\MFFD 0.565 0.698 0.415 0.278 0.239 0.176 0.113 0.098 0.075 0.060 0.011 0.006 0.005 0.002 0.196 FFI 8.996 9.805 9.577 10.655 10.316 10.067 10.273 10.700 10.363 11.278 10.792 11.125 10.859 10.899 10.407 FFHILO 3.238 3.451 4.297 4.064 4.043 3.528 3.754 3.651 3.843 3.626 3.580 3.922 3.902 3.587 3.749 FFLOHI 3.858 3.689 4.066 4.130 4.637 4.014 3.815 4.282 4.035 3.680 3.609 3.867 3.888 3.542 3.937 FFV 5.929 5.168 5.094 5.884 5.578 4.885 5.109 5.233 5.282 5.562 5.332 5.544 5.391 5.348 5.381 FFA 1.639 1.446 1.038 0.803 0.618 0.472 0.308 0.314 0.343 0.231 0.118 0.096 0.054 0.037 0.537 MILP 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.002 0.006 0.037 0.043 0.085 0.012 MOD Set of instances NEW 4.314 7.775 8.395 17.005 13.464 12.382 13.151 15.351 18.182 14.780 21.734 21.685 24.622 27.919 15.768 NEW BF 0.151 0.422 0.474 0.384 0.365 0.459 0.241 0.172 0.101 0.112 0.031 0.007 0.008 0.003 0.209 NEW FF 0.206 0.448 0.607 0.450 0.510 0.557 0.313 0.223 0.155 0.122 0.043 0.028 0.021 0.017 0.264 BFR 7.841 7.318 7.129 5.977 5.899 5.808 5.239 5.264 4.290 4.054 3.419 3.103 2.933 2.732 5.072 BFD 1.846 1.293 0.871 0.691 0.671 0.655 0.365 0.285 0.237 0.157 0.050 0.036 0.030 0.023 0.515 BFI 21.292 25.256 28.502 29.821 31.210 31.808 30.809 30.312 30.885 30.889 31.335 32.628 31.755 32.235 29.910 BFHILO 6.198 6.802 7.182 7.679 9.439 8.485 7.950 8.010 8.136 8.011 7.052 8.010 8.000 8.854 7.843 BFLOHI 7.314 8.168 7.960 8.287 10.205 9.486 8.446 8.305 8.426 8.449 7.288 8.173 8.285 8.935 8.409 BFV 7.740 11.858 12.958 13.267 13.853 14.943 14.281 14.117 14.501 14.509 14.855 15.947 15.423 15.777 13.859 BFA 8.177 8.280 8.554 8.848 8.054 8.301 6.847 6.631 7.202 5.443 5.762 7.140 7.520 7.208 7.426 FFR 7.812 8.747 8.335 7.114 6.704 6.225 5.637 6.364 5.101 4.725 4.118 3.864 3.653 3.685 5.863 FFD 1.825 1.191 0.875 0.621 0.653 0.658 0.367 0.283 0.221 0.156 0.045 0.037 0.026 0.021 0.499 FFI 21.292 25.256 28.502 29.821 31.210 31.808 30.809 30.312 30.885 30.889 31.335 32.628 31.755 32.235 29.910 FFHILO 6.000 6.930 7.245 7.679 9.397 8.542 8.001 8.025 8.200 8.116 7.052 8.090 8.032 8.879 7.871 FFLOHI 7.449 8.716 8.152 8.287 10.207 9.654 8.559 8.305 8.492 8.527 7.288 8.206 8.302 8.948 8.507 FFV 7.740 12.074 12.958 13.360 13.853 15.018 14.281 14.117 14.620 14.549 14.829 15.929 15.423 15.805 13.897 FFA 7.360 7.708 8.496 8.776 8.111 8.233 6.919 6.668 7.261 5.465 5.787 7.150 7.526 7.227 7.335 MFFD 2.084 1.880 1.643 1.698 1.311 1.723 0.970 1.186 1.219 0.765 0.687 0.694 0.848 0.924 1.259 MILP 0.000 0.000 0.000 0.002 0.000 0.001 0.025 0.010 0.052 0.128 0.344 0.762 0.741 0.850 0.208 Table 2: Average RPD depending on nfor each method. 18 N Method 10 20 30 40 50 60 70 80 90 100 150 200 250 300 Total LOW Set of Instances NEW BF 0.000 0.000 0.008 0.017 0.041 0.072 0.105 0.169 0.241 0.341 1.003 2.517 8.938 17.103 2.183 NEW FF 0.000 0.000 0.008 0.017 0.040 0.072 0.102 0.153 0.217 0.313 0.986 2.516 8.539 16.607 2.112 BFD 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.001 0.001 0.001 0.000 FFD\MFFD 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.001 0.000 0.000 0.000 0.000 0.000 MILP 0.064 0.327 18.739 0.698 6.634 7.987 41.710 48.328 151.300 209.599 369.508 704.783 887.438 901.835 239.211 MOD Set of Instances NEW BF 0.001 0.003 0.007 0.018 0.040 0.069 0.110 0.164 0.265 0.345 1.261 3.784 10.888 23.527 2.892 NEW FF 0.000 0.002 0.007 0.016 0.031 0.059 0.087 0.134 0.222 0.293 1.058 2.902 9.093 19.192 2.364 BFD 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.001 0.002 0.000 FFD 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 MFFD 0.001 0.002 0.002 0.003 0.004 0.004 0.005 0.006 0.006 0.008 0.012 0.015 0.012 0.021 0.007 MILP 0.091 1.256 34.289 97.395 241.888 400.628 471.155 735.963 834.422 811.741 874.694 900.409 900.878 901.630 514.746 Table 3: CPU Times in seconds depending on nfor each method. 19 Figure 4: 95% Confidence Interval for ARPD: All heuristics and MILP. Case MOD Set of Instances Figure 5: 95% Confidence Interval for ARPD: Best constructive heuristics and MILP. Case LOW Set of Instances 20 Figure 6: 95% Confidence Interval for ARPD: Best constructive heuristics and MILP. Case MOD Set of Instances 21 7 Conclusions In this paper we have addressed the single machine scheduling problem with cyclic availability of machines (usually denoted as periodic maintenance in the literature). This problem is NP-hard when the objective is the makespan, and several approximate procedures were proposed, but they have not been compared up to now. In this work we first explore the relationship between our problem and the classical bin packing problem. To do so, we develop an MILP model for each problem, named PM-MILP model (for the proposed problem), and BP-MILP model (for the bin-packing problem). The optimal solutions of the PM-MILP model are a subset of the optimal solutions of the BPMILP model. Therefore, we can borrow some ideas from approximate methods for the bin packing problem to develop constructive heuristics for the proposed problem. More specifically, we develop new heuristics that use bin packing assignment rules as operators on a job sequence. These operators are embedded into a local search. The idea is to apply the bin-packing operators before evaluating each schedule obtained in the simple local search method. In this manner, three new heuristics are tested: NEW, NEW BF and NEW FF using different bin-packing assignment policies. NEW does not apply any bin-packing operator and it is used as a base heuristic for comparison, while the other two use the Best Fit (BF) and First Fit (FF) bin-packing assignment rules, respectively. These proposals are compared with constructive heuristics existing in the literature, together with some new variants proposed. In total, 12 heuristics are tested against our heuristics. To assess the efficiency of our proposals, an exhaustive computational evaluation is conducted using two different sets of instances. The results show that NEW BF and NEW FF are the best methods in terms of quality of solutions and in CPU time requirements. For future research lines, and due to the practical interest of scheduling problems with periodic maintenance, it could be useful to study this problem in other layouts as flowshop or parallel machines. Additionally, other objectives different to makespan have not been considered in the literature, so it could be another interesting option for future research. 22 References Angel-Bello, F., Alvarez, A., Pacheco, J., and Mart´ınez, I. (2011). A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times. Computers & Mathematics with Applications, 61(4):797–808. Framinan, J., Leisten, R., and Rajendran, C. (2003). Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem. International Journal of Production Research, 41(1):121–148. Framinan, J. M., Leisten, R., and Garc´ıa, R. R. (2014). Manufacturing scheduling systems: An integrated view on models, methods and tools, volume 9781447162. Hsu, C.-J., Low, C., and Su, C.-T. (2010). A single-machine scheduling problem with maintenance activities to minimize makespan. Applied Mathematics and Computation, 215(11):3929–3935. Ji, M., He, Y., and Cheng, T. (2007). Single-machine scheduling with periodic maintenance to minimize makespan. Computers & Operations Research, 34(6):1764–1770. Lee, C.-Y. (1996). Machine scheduling with an availability constraint. Journal of Global Optimization, 9(3-4):395–416. Low, C., Hsu, C.-J., and Su, C.-T. (2010a). A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance. Expert Systems with Applications, 37(9):6429–6434. Low, C., Ji, M., Hsu, C.-j., and Su, C.-t. (2010b). Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. APPLIED MATHEMATICAL MODELLING, 34(2):334–342. Ma, Y., Chu, C., and Zuo, C. (2009). A survey of scheduling with deterministic machine availability constraints. COMPUTERS & INDUSTRIAL ENGINEERING, 58(2):199–211. Martello, Silvano; Toth, P. (1990). Bin-packing problem. In Knapsack Problem. Algorithms and Computer Implementation, chapter 8, page 221. John Wiley and Sons Ltd. 23 Pacheco, J., Angel-Bello, F., and Alvarez, A. (2012). A multi-start tabu search method for a singlemachine scheduling problem with periodic maintenance and sequence-dependent set-up times. Journal of Scheduling, 16(6):661–673. Yu, X., Zhang, Y., and Steiner, G. (2014). Single-machine scheduling with periodic maintenance to minimize makespan revisited. Journal of Scheduling, 17(3):263–270. Yue, M. and Zhang, L. (1995). A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica, 11(3):318–330. 24