The aim of solving a scheduling problem is to create a valid schedule, where all the operation of jobs are assigned to machines with an exact starting and ending time. A schedule is considered to be appropriate, if optimal solution can be achieved for a certain objective, for example: minimizing the makespan (total required time for completing all jobs of the production plan).
It examines the result of the heuristics, and the optimization algorithm combination. The production planning is introduced, and the scheduling as a part of the production planning.
The processes of the enterprise resource planning (ERP) systems were examined. There is a difference between the usage of the’’scheduling” concept in an ERP system and in a scheduling problem. The thesis highlights the difference, and points out the challenges, and the methods which used in ERP systems like SAP and QAD. The IBM ILOG CPLEX Studio, and the MS Excel Solver pros and contras were examined, and compared to each other.
The job shop problems and its classification were introduced, in particular the deterministic job shop problems.
Scheduling algorithms can be classified in two groups based on their solution methods. One of the group is based on approximation, heuristic methods and the other group uses advanced mathematical optimization techniques. Optimization techniques based on mathematical methods can be time-consuming, but may provide and prove the best feasible solution for scheduling problems. The former usually provide a valid schedule in a short run-time, but the problem’s optimum point cannot be reached in most of the cases. The heuristic Dispatching Rule algorithms, and the Failure Directed Search optimization algorithm (which is used by the IBM ILOG CPLEX Studio), were examined.
The basic aim of the thesis is to shorten the computational time of the optimization heuristic approximation technique pre-optimizing the input data. A starting schedule is provided with a constructive and quick method (DR), before starting the calculation of the actual scheduling with FDS.
My algorithm performance was tested on widely spread benchmark problems, proposed by Taillard, and was compared to other publicized research and algorithm’s results.