Article Preview
TopIntroduction
Scheduling is a decision-making process that deals with the allocation of resources to tasks over given time periods with the all constraints provided (Baker, 1974). It is also considered as the optimization of a problem, with the goal of optimizing one or more objectives. Scheduling is widely used on a regular basis in many manufacturing and service industries. Often, the process includes some limitations like the capacity of vehicles, working time of employees, limited funds etc. Scheduling problems differ markedly from case to case (Đumić, Šišejković, Čorić, & Jakobović, 2018).
One of the most intractable classical combinatorial optimization problems in the context of scheduling is resource constrained project scheduling problem (RCPSP). It was proved to be strongly NP-hard (Blazewicz, Lenstra, & Kan, 1983). The main objective is to schedule the activities such that the project completion time (makespan) can be minimized, while involving precedence (temporal) and resources constraints (Chen, 2011).
As an active research area, the RCPSP has a wide range of applications in logistics, manufacturing and project management (Bukata, Šůcha, & Hanzálek, 2015). It is also at the core of many project scheduling problems arising in a variety of industries and other applications, which include software development, rolling ingots production in aluminium industry, medical research scheduling, sports league scheduling, audit scheduling, scheduling of port operations, market research interviewers scheduling, assembly shop scheduling, instruction scheduling for parallel processors, batch production scheduling, employee scheduling, school and university timetabling, and resource-constrained scheduling for disaster and recovery, among many others (Riley & Rego, 2018).
Many real-life problems can be formulated as RCPSP, and due to its complexity, RCPSP became a very attractive field for researchers either in scheduling field or in operations research. Numerous numbers of researches have proposed various approaches which can be dispatched into three main classes: deterministic (or exact), heuristics and meta-heuristic methods (Hartmann & Briskorn, 2010).
Exact approaches have been explored firstly to solve the RCPSP such as Integer Programming, Implicit Enumeration, Branch-and-bound, Dynamic Programming (Đumić et al. 2018). Exact approaches are typically used to solve relatively small-sized instances optimally since the execution time needed increases impractically with the size of the problem (Akbari, Zeighami, & Akbari, 2012). Therefore, heuristics or a meta-heuristic would be more suitable for the large-sized problems in a satisfactory manner. These methods find the optimal or near optimal schedule in reasonable amount of time and memory space (Đumić et al., 2018).
Several heuristics approaches have been developed and try to provide good solutions by considering two main components, namely the Priority Rule based heuristics and Schedule Generation Scheme (SGS) (Fahmy, Hassan, & Bassioni, 2014). Priority rules are particularly useful in cases where cheaper, more intuitive solutions are preferred over optimality, something that is commonly seen in smaller manufacturing environments. Priority rules are mainly used to arrange the activities list in an order which will generate a good solution. Various priority rules have been proposed such as: latest start time (LST), latest finish time (LFT), resource scheduling method (RSM), improved resource scheduling method (IRSM), worst case sack (WCS), shortest processing time (SPT), minimum slack (MSLK), most immediate successors (MIS), most total successors (MTS), least float per successor (LFS), greatest rank positional weight (GRPW), most total successors (MTS), longest path following (LPF), and random (Rand) (Kolisch & Hartmann, 1999). The schedule generation scheme (SGS) is used to create a schedule depending on priority rule. There are two different types of SGS: Serial SGS based on activity incrementation, and Parallel SGS based on time incrementation (Kolisch & Hartmann, 1999). Priority based-methods can solve large-sized RCPSP problem within acceptable time, but they are hard to adapt to the constraints of problems dynamically (Chen, 2011).