Timetabling is an NP-Hard problem that searches for periodic scheduling of events that must meet a set of hard and soft constraints. Because of the difficulty in finding an exact solution, the use of heuristics to address the problem is a common practice. When only the hard constraints are considered, the timetabling problem can be reduced to graph vertex coloring. This similarity between both problems has motivated the use of graph coloring heuristics as a means to solve the timetabling problem. We propose the use of the Quantum Approximate Optimization Algorithm as a heuristic to solve the school timetabling problem. The QAOA is a hybrid quantum-classical algorithm that can be used to address combinatorial optimization problems. We simulated QAOA in a minimal example with 42 qubits using the Ket Quantum Programming Language and our results showed that it is possible to apply QAOA to the school timetabling problem.

This paper presents an approach for Web service (WS) composition that enables the automatic adjustment of the composition at run-time to deal with WS execution flaws, e.g., WS unavailability, failure to execute properly or to produce desired results. The WS composition problem is converted into a nondeterministic planning problem which, by its turn, is mapped to SAT. Afterwards, a SAT solver obtains all the possible WS compositions with a maximum length N, which are then fused into a contingency strategy (CS) according to compatibility criteria. Such strategy enables the process execution engine to readily choose the most suitable WS composition to enact, and switch to an alternative composition with minimum adaptation cost in case of any WS execution flaw.