F Algorithm

Brief Description

F is a new best-first-search algorithm. It is called F because it Finds a solution. F is a heuristic search algorithm with an iterative constructive and backtracking phases. It is based on trial and error paradigm and it maintains a partial feasible schedule until finding the complete one.

F has five features that distinguish it from existing iterative constructive backtracking techniques.

• F’s selection rule chooses jobs according to a merit value that reflects the job’s current position and corrective value. Thus, the merit value is independent from the instance parameters. This is in contrast to existing approaches, which select jobs according to variable ordering and problem dependent heuristics.

• F’s construction phase stops when F can’t position the current job on-time or the current partial solution violates a new theoretical property. This second stopping condition has neither been applied.

• F’s backtracking phase destroys only the last part of the current partial schedule and preserves the first part for future use. Thus, F avoids rebuilding solutions from scratch and reduces its search time.  This feature distinguishes F from existing heuristics, which remove all the jobs of the current partial schedule. To choose the job to be removed from the partial solution, F’s backtracking uses a merit function. This is neither the systematic job removal adopted by existing backtracking methods nor the chronological backtracking via back jumping of exact approaches.

• F’s random exploration of the state-space avoids  the time-consuming systematic scanning of the search tree, applied in exact approaches.

• The finite range of F’s merit function makes F’s corrective actions more realistic and meaningful than those applied by other heuristics.

In addition to its five distinguishing features, F avoids three major drawbacks : 

• First, studying F’s Completeness in lieu of its probabilistic approximate Completeness is possible. F uses a deterministic technique to select the next job (except random breaking of ties when two jobs have identical merit values). Existing approaches are probabilistic.

• Second, F is parameter-free; thus, avoids the parameters’ tuning required by meta-heuristics. 

• Third, while existing meta-heuristics guide the search via problem-dependent heuristics, F’s search is totally independent of the instance; a property that defines its uniqueness in the class of heuristics.

Research Perspectives

We strongly believe that the new F algorithm constitutes a new way to solve scheduling  and optimization problems rather than usual metaheuristics and exact algorithms with exponential space complexity.  Research directions include the generalization to other scheduling and optimization problems, proof of completeness, and dealing with large scale instances.

Reference :

Yacine Laalaoui, Rym M'Hallah:

A problem-independent search heuristic for single machine scheduling with release dates and deadlines. SSCI 2022: 782-789