Selecting inversions in a chord progression with the triad by a lexicographic bi-criteria optimization

Abstract

We are given a sequence of m machines and an ordered set of n jobs. The n jobs are served by the m-machine system in their indexing order. We are also given a collection of pj machine subsets for each job j ∈ N, where N denotes the set of jobs. We are primarily asked to choose a machine subset from the pj options for each job j ∈ N so that the similarity sum over a series of chosen n machine subsets is maximized, where a degree of similarity of two machine subsets is defined to be the number of common machines between the two machine subsets. The series of chosen n machine subsets also induces a subsequence of machines for serving the n jobs. We call the length of an induced machine subsequence its stretch. We are secondarily asked to choose a machine subset from the pj options for each job j ∈ N so that the stretch of the induced machine subsequence is minimized. The lexicographic machine subset selection problem is motivated by a musical issue of selecting inversions in a chord progression with the triad. In this paper, we propose a polynomial time exact algorithm for the lexicographic machine subset selection problem. We also demonstrate the solutions on three examples of chord progressions with the triad, and on randomly generated instances.

Keywords

• lexicographic optimization
• machine subset selection
• chord progressions
• inversions
• dynamic programming
• iterative guessing
• polynomial time algorithms