Scheduling of Software Test to Minimize the Total Completion Time

Man-Ting Chao and Bertrand M. T. Lin ()
Additional contact information
Man-Ting Chao: Institute of Information Management, National Yang Ming Chiao Tung University, Hsinchu 300, Taiwan
Bertrand M. T. Lin: Institute of Information Management, National Yang Ming Chiao Tung University, Hsinchu 300, Taiwan

Mathematics, 2023, vol. 11, issue 22, 1-17

Abstract: This paper investigates a single-machine scheduling problem of a software test with shared common setup operations. Each job has a corresponding set of setup operations, and the job cannot be executed unless its setups are completed. If two jobs have the same supporting setups, the common setups are performed only once. No preemption of any processing is allowed. This problem is known to be computationally intractable. In this study, we propose sequence-based and position-based integer programming models and a branch-and-bound algorithm for finding optimal solutions. We also propose an ant colony optimization algorithm for finding approximate solutions, which will be used as the initial upper bound of the branch-and-bound algorithm. The computational experiments are designed and conducted to numerically appraise all of the proposed methods.

Keywords: single-machine scheduling; shared common setups; total completion time; integer programming; branch-and-bound; ant colony optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/22/4705/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/22/4705/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:22:p:4705-:d:1284005

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().