Extensive research works have been carried out in resource constrained project scheduling problem. However, scarce researches have studied the problems in which a setup cost must be incurred if activities are preempted. In this research, we investigate the resource constrained project scheduling problem to minimize the total project cost, considering earliness-tardiness and preemption penalties. A mixed integer programming formulation is proposed for the problem. The resulting problem is NP-hard. So, we try to obtain a satisfying solution using simulated annealing (SA) algorithm. The efficiency of the proposed algorithm is tested based on 150 randomly produced examples. Statistical comparison in terms of the computational times and objective function indicates that the proposed algorithm is efficient and effective. 1. Introduction Preemptive project scheduling problems are those in which the accomplishing of an activity is temporarily preempted and restarted afterwards. In the previous literature on preemptive project scheduling, preempted activities simply are resumed from the moment at which preemption occurred without any cost. However, this situation is not always true in reality. It is probable that, in some situations, a certain setup or delay cost should be considered. The literature on solution approaches for the preemptive resource constrained project scheduling problem with weighted earliness-tardiness and preemption penalties (PRCPSP-WETPP) is scant. Of course, several papers have been devoted to machine scheduling considering preemption costs. Potts and van Wassenhove [1] integrated preemptive scheduling with batching and lot-sizing model. Monma and Potts [2] and Chen [3] suggested the heuristics for parallel machine scheduling problem subject to preemption and batch setup times. Zdrzalka [4], Schuurman and Woeginger [5], and Liu and Cheng [6] studied preemptive scheduling with job release dates and job-dependent setup times. Julien et al. [7] proposed generalized preemption models for single-machine dynamic scheduling problems. Rebai et al. [8] developed some metaheuristics and exact methods for minimization of earliness-tardiness penalties on a single machine to schedule preventive maintenance tasks. They used linear programming and branch and bound to obtain exact solutions. Also, they developed a local search approach as well as a genetic algorithm as metaheuristics for solving hard scheduling problems. Vanhoucke [9] and Vanhoucke et al. [10] have proposed an exact method for the weighted earliness-tardiness project scheduling problem
References
[1]
C. N. Potts and L. N. van Wassenhove, “Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity,” Journal of the Operational Research Society, vol. 43, pp. 395–406, 1992.
[2]
C. L. Monma and C. N. Potts, “Analysis of heuristics for preemptive parallel machine scheduling with batch setup times,” Operations Research, vol. 41, no. 5, pp. 981–993, 1993.
[3]
B. Chen, “A better heuristic for preemptive parallel machine scheduling with batch setup times,” SIAM Journal on Computing, vol. 22, no. 6, pp. 1303–1318, 1993.
[4]
S. Zdrza？ka, “Preemptive scheduling with release dates, delivery times and sequence independent setup times,” European Journal of Operational Research, vol. 76, no. 1, pp. 60–71, 1994.
[5]
P. Schuurman and G. J. Woeginger, “Preemptive scheduling with job-dependent setup times,” in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 759–767, January 1999.
[6]
Z. Liu and T. C. E. Cheng, “Scheduling with job release dates, delivery times and preemption penalties,” Information Processing Letters, vol. 82, no. 2, pp. 107–111, 2002.
[7]
F. M. Julien, M. J. Magazine, and N. G. Hall, “Genralized preemption models for single-machine dynamic scheduling problems,” IIE Transactions, vol. 29, no. 5, pp. 359–372, 1997.
[8]
M. Rebai, I. Kacem, and K. H. Adjallah, “Earliness-tardiness minimization on a single machine to schedule preventive maintenance tasks: metaheuristic and exact methods,” Journal of Intelligent Manufacturing, vol. 23, no. 4, pp. 1207–1224, 2012.
[9]
M. Vanhoucke, Exact algorithms for various types of project scheduling problems non-regular objectives and time/cost trade-offs [Ph.D. dissertation], Katholieke Universiteit Leuven, 2001.
[10]
M. Vanhoucke, E. Demeulemeester, and W. Herroelen, “An exact procedure for the resource constrained weighted earliness-tardiness project scheduling problem,” Annals of Operations Research, vol. 102, pp. 179–196, 2000.
[11]
M. Vanhoucke, E. Demeulemeester, and W. Herroelen, “Maximizing the net present value of a project with progress payments,” Research Report 0028, Department of Applied Economics, Katholieke Universiteit Leuven, 2000.
[12]
B. Afshar Nadjafi and S. Shadrokh, “A branch and bound algorithm for the weighted earliness-tardiness project scheduling problem with generalized precedence relations,” Scientia Iranica, vol. 16, no. 1, pp. 55–64, 2009.
[13]
M. Ranjbar, M. Khalilzadeh, F. Kianfar, and K. Etminani, “An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem,” Computers and Industrial Engineering, vol. 62, no. 1, pp. 264–270, 2012.
[14]
Y. Khoshjahan, A. A. Najafi, and B. Afshar-Nadjafi, “Resource constrained project scheduling problem with discounted earliness-tardiness penalties: mathematical modeling and solving procedure,” Computers and Industrial Engineering, vol. 66, no. 2, pp. 293–300, 2013.
[15]
L. A. Kaplan, Resource constrained project scheduling with preemption of jobs [Ph.D. thesis], University of Michigan, 1988.
[16]
E. L. Demeulemeester and W. S. Herroelen, “An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 90, no. 2, pp. 334–348, 1996.
[17]
B. Afshar-Nadjafi, “A solution procedure for preemptive multi-mode project scheduling problem with mode changeability to resumption,” Applied Computing and Informatics, 2014.
[18]
K. Bülbül, P. Kaminsky, and C. Yano, “Preemption in single machine earliness/tardiness scheduling,” Journal of Scheduling, vol. 10, no. 4-5, pp. 271–292, 2007.
[19]
P. Baptiste, J. Carlier, A. Kononov, M. Queyranne, S. Sevastyanov, and M. Sviridenko, “Structural properties of optimal schedules with operation interruptions,” Diskretnyi Analizi Issledovanie Operatsii, vol. 16, no. 1, pp. 3–36, 2009.
[20]
P. Baptiste, J. Carlier, A. Kononov, M. Queyranne, S. Sevastyanov, and M. Sviridenko, “Properties of optimal schedules in preemptive shop scheduling,” Discrete Applied Mathematics, vol. 159, no. 5, pp. 272–280, 2011.
[21]
J. H. Patterson, “A comparison of exact procedures for solving the multiple constrained resource project scheduling problem,” Management Science, vol. 30, no. 7, pp. 854–867, 1984.
[22]
J. Blazewicz, J. K. Lenstra, and A. H. G. Rinnooy Kan, “Scheduling subject to resource constraints: classification and complexity,” Discrete Applied Mathematics, vol. 5, no. 1, pp. 11–24, 1983.
[23]
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
[24]
B. Abbasi, S. Shadrokh, and J. Arkat, “Bi-objective resource-constrained project scheduling with robustness and makespan criteria,” Applied Mathematics and Computation, vol. 180, no. 1, pp. 146–152, 2006.
[25]
K. Bouleimen and H. Lecocq, “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version,” European Journal of Operational Research, vol. 149, no. 2, pp. 268–281, 2003.
[26]
Z. He, N. Wang, T. Jia, and Y. Xu, “Simulated annealing and tabu search for multi-mode project payment scheduling,” European Journal of Operational Research, vol. 198, no. 3, pp. 688–696, 2009.
[27]
J. Józefowska, M. Mika, R. Ró？ycki, G. Waligóra, and J. W？glarz, “Simulated annealing for multi-mode resource-constrained project scheduling,” Annals of Operations Research, vol. 102, pp. 137–155, 2001.
[28]
M. Mika, G. Waligóra, and J. W？glarz, “Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models,” European Journal of Operational Research, vol. 164, no. 3, pp. 639–668, 2005.
[29]
A. Rahimi, H. Karimi, and B. Afshar-Nadjafi, “Using meta-heuristics for project scheduling under mode identity constraints,” Applied Soft Computing, vol. 13, no. 4, pp. 2124–2135, 2013.
[30]
M. Lundy and A. Mees, “Convergence of an annealing algorithm,” Mathematical Programming, vol. 34, no. 1, pp. 111–124, 1986.
[31]
B. Naderi and H. Sadeghi, “A multi-objective simulated annealing algorithm to solving flexible no-wait flow shop scheduling problems with transportation times,” Journal of Optimization An Industrial Engineering, vol. 5, no. 11, pp. 33–41, 2012.
[32]
R. Kolisch, A. Sprecher, and A. Drexl, “Characterization and generation of a general class of resource-constrained project scheduling problems,” Management Science, vol. 41, pp. 1693–1703, 1995.
[33]
F. Forouzanfar and R. Tavakkoli-Moghaddam, “Using a genetic algorithm to optimize the total cost for a location-routing-inventory problem in a supply chain with risk pooling,” Journal of Applied Operational Research, vol. 4, no. 1, pp. 2–13, 2012.
[34]
P. Chen and S. M. Shahandashti, “Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints,” Automation in Construction, vol. 18, no. 4, pp. 434–443, 2009.
