Project Scheduling Algorithm Addressing Shared Due Dates

We study the single-mode Resource-Constrained Project Scheduling Problem (RCPSP) with renewable resources. The RCPSP schedules start times for activities of a project subject to temporal constraints on the execution order of activities and resource constraints on the availability of resources. We investigate the RCPSP with the objective of weighted tardiness, where the objective is to minimize the overall delays in meeting assigned due dates. While many different industries utilize the RCPSP, we focus on two specific applications to motivate our research: pharmaceutical drug development portfolio scheduling and chemical plant turnaround scheduling. In the pharmaceutical industry, [1] establishes that the median research and development cost of 63 drugs developed between 2009 and 2018 was $985 million. Efficiently scheduling pharmaceutical research and development tasks can reduce both the cost and the time to market of new drugs, as demonstrated by a multitude of recent works [2-5]. Additionally, we motivate project scheduling in the context of turnarounds in the chemical industry. Necessary, but costly, turnarounds stop production for maintenance and other preventative work executable only in the shutdown state. During the maintenance period, workers execute a set of complex and interlinked activities that can be modeled by the RCPSP. Effective scheduling of tasks within shutdowns can utilize resources more efficiently and reduce overall cost [6]. In consideration of these two motivating applications, we introduce shared due dates into the RCPSP and design an algorithm to efficiently solve the RCPSP with shared due dates.

The RCPSP is an NP-hard problem and requires the use of heuristics to tractably produce solutions for problems of practical size and complexity [7]. We employ the serial and parallel schedule generation schemes in conjunction with priority rules to construct solutions for the RCPSP. We introduce shared due dates to the RCPSP where the tardiness penalty of a due date shared by a set of activities is the maximum tardiness of any activity in the set of activities assigned to a shared due date. We show that prominent priority rules in literature [8, 9] perform poorly on instances with shared due dates. To address this gap, we create a novel priority rule that utilizes information regarding shared due dates in its priority assignment. In the algorithm, we approximate project progress against due dates and consider activity slack to prioritize activities. We parameterize our priority rule to allow flexibility to our algorithm with respect to at what point in the scheduling procedure we use shared due date information to schedule activities and to what degree we consider slack in the priority assignment. Our priority rule is dynamic in the schedule generation scheme, i.e., it dynamically updates as scheduling progresses. Using our priority rule in the schedule generation schemes, we construct feasible schedules in milliseconds for problems with 120 activities.

We benchmark our algorithm against existing priority rules in literature on instances from the literature standard j120 PSPLIB data set [10] extended with shared due date assignments. We assess the performance of the priority rules in both the serial and parallel schedule generation schemes. We show that our novel priority rule algorithm outperforms all priority rules prominent in literature including priority rules defined for single due dates [11]. Last but not least, we examine the performance of our priority rule against the performance of a commercial solver used on a MILP model of the problem [5]. We show that our priority rule achieves good solution quality while requiring significantly less execution time than the exact algorithm.

[1] O. J. Wouters, M. McKee, and J. Luyten, “Estimated Research and Development Investment Needed to Bring a New Medicine to Market, 2009-2018,” JAMA, vol. 323, no. 9, pp. 844–853, 2020, doi: 10.1001/jama.2020.1166.

[2] M. Colvin and C. T. Maravelias, “R&D pipeline management: Task interdependencies and risk management,” Eur. J. Oper. Res., vol. 215, no. 3, pp. 616–628, 2011.

[3] M. Colvin and C. T. Maravelias, “Scheduling of testing tasks and resource planning in new product development using stochastic programming,” Comput. Chem. Eng., vol. 33, no. 5, pp. 964–976, 2009.

[4] M. Colvin and C. T. Maravelias, “A stochastic programming approach for clinical trial planning in new drug development,” Comput. Chem. Eng., vol. 32, no. 11, pp. 2626–2642, 2008.

[5] H. Wang et al., “Portfolio-wide optimization of pharmaceutical R&D activities using mathematical programming,” Rev., 2020.

[6] N. Megow, R. H. Möhring, and J. Schulz, “Decision support and optimization in shutdown and turnaround scheduling,” Inf. J. Comput., vol. 23, no. 2, pp. 189–204, 2011.

[7] R. Pellerin, N. Perrier, and F. Berthaut, “A survey of hybrid metaheuristics for the resource-constrained project scheduling problem,” Eur. J. Oper. Res., vol. 280, no. 2, pp. 395–416, 2020.

[8] S. Chand, Q. Huynh, H. Singh, T. Ray, and M. Wagner, “On the use of genetic programming to evolve priority rules for resource constrained project scheduling problems,” Inf. Sci., vol. 432, pp. 146–163, 2018.

[9] S. Hartmann, “A competitive genetic algorithm for resource-constrained project scheduling,” Nav. Res. Logist. NRL, vol. 45, no. 7, pp. 733–750, 1998.

[10] R. Kolisch and A. Sprecher, “PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program,” Eur. J. Oper. Res., vol. 96, no. 1, pp. 205–216, 1997.

[11] F. Ballestín, V. Valls, and S. Quintanilla, “Due Dates and RCPSP,” in Perspectives in Modern Project Scheduling, J. Józefowska and J. Weglarz, Eds. Boston, MA: Springer US, 2006, pp. 79–104.