Tetsuya Fujie

In this paper, we discuss a two-machine flowshop problem with the objective of minimizing the total flow time subject to minimum makespan. The problem is known as one of the hierarchical multicriteria scheduling problems which are a variant of the multicriteria scheduling problems. The problem is known to be NP-hard in general. T'kindt et al. provided a branch-and-bound algorithm to find an optimal schedule for the problem and reported that their algorithm solved problem instances effectively with up to 23 jobs. The purpose of this paper is to improve the branch-and-bound algorithm based on a generalization of a subproblem representation and new dominance relations. In most branch-and-bound algorithms for scheduling problems, a subproblem representation which fixes some jobs at the head of the schedule is used. In this paper, we use a more flexible subproblem representation in which jobs both at the head and at the end of the schedule are fixed. We show that existing dominance relations can be generalized and then propose some new relations. Dominance tests based on the dominance relations are incorporated into the branch-and-bound algorithm. The computational result shows that our algorithm works successfully to solve problem instances with up to 29 jobs. Furthermore, our algorithm outperforms an algorithm proposed by T'kindt et al. and a recent mixed integer programming solver.

Given an undirected graph G, the Maximum-Leaf Spanning Tree Problem is to find a spanning tree in G, whose number of leaves (degree-1 vertices) is maximum. The problem is NP-hard, and several approximation algorithms, that is, lower bounding computations, are proposed. This paper concerns with upper bounding computations. First, we provide two kinds of 0-1 integer programming formulations of the problem. Next, we give necessary and sufficient conditions that the constraints in each formulation define facets of a polytope which is defined as a convex hull of the set of feasible solutions. Finally, relaxation problems are considered.