Impact of Hyperparameters on Quantum Approximate Optimization Algorithm (QAOA) While Solving The Single Machine Scheduling Problem with Weighted Tardiness as the Performance

Creative Commons License

Çağlar Gençosman B., Özmutlu S.

ARCENG VII. INTERNATIONAL SCIENTIFIC RESEARCH CONGRESS, İstanbul, Türkiye, 27 - 28 Haziran 2026, cilt.1, ss.229-240, (Tam Metin Bildiri)

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 1
  • Basıldığı Şehir: İstanbul
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.229-240
  • Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
  • Bursa Uludağ Üniversitesi Adresli: Evet

Özet

Quantum Computing has been a facilitator in solving intractable problems since the 2000s. In search of a faster alternative, researchers began applying quantum computing to solve NP-hard scheduling problems. The Single Machine Weighted Tardiness Problem (SMWTP) is an important NP-hard problem in the scheduling literature and is well-suited to quantum computing solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm that can be used to solve SMWTP; however, hyperparameter tuning may be important in its application. This study aims to identify the impact of hyperparameters on QAOA’s performance to solve the SMWTP. The SMWTP is first modeled as a mathematical program, then converted to a Quadratic Binary Optimization (QUBO) format to be solved by quantum methods. Then, the QUBO format is expressed as Ising-Hamiltonians, i.e., the cost and mixer Hamiltonians.  After obtaining the Ising Hamiltonian, the QAOA circuit is executed by alternately applying the cost and mixing Hamiltonians, followed by measurement and subsequent classical evaluation of the weighted tardiness values. Four algorithm parameters for QAOA might affect solution performance: the Cost Hamiltonian parameter, the Mixer Hamiltonian parameter, the number of layers, and the penalty multiplier. To measure the impact of hyperparameters on QAOA performance, test instances in which algorithm parameters are systematically varied for comprehensive experimentation are run. Three metrics are used to measure hyperparameter performance: the distribution of the best results across hyperparameter levels, the average optimality gap, and the percentage of feasible schedules. The hyperparameter analysis reveals that the mixer parameter (β) is the primary determinant of the recovery of feasible solutions. Results indicate that using β=0.1 decreases the optimality gap and increases the percentage of feasible solutions.