記述言語：英語   掲載種別：研究論文（学術雑誌）  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Operations Research Society of Japan  

The two-dimensional strip packing problem arises in wide variety of industrial applications. In this paper, we focus on the bitmap shape packing problem in which a set of arbitrarily shaped objects represented in bitmap format should be packed into a larger rectangular container without overlap. The complex geometry of bitmap shapes and the large amount of data to be processed make it difficult to check for overlaps. In this paper, we propose an efficient method for checking for overlaps and design efficient implementations of two construction algorithms, which are based on the bottom-left strategy. In this strategy, starting from an empty layout, items are packed into the container one by one. Each item is placed in the lowest position where there is no overlap relative to the current layout. We consider two algorithms, the bottom-left and the best-fit algorithm, which adopt this strategy. The computational results for a series of instances that are generated from well-known benchmark instances show that the proposed algorithms obtain good solutions in remarkably short time and are especially effective for large-scale instances.

DOI： 10.15807/jorsj.61.132

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

In this paper, we optimize train stopping patterns during morning rush hour in Japan. Since trains are extremely crowded, we need to determine stopping patterns based not only on travel time but also on congestion rates of trains. We exploit a Wardrop equilibrium model to compute passenger flows subject to congestion phenomena and present an efficient local search algorithm to optimize stopping patterns which iteratively computes a Wardrop equilibrium. We apply our algorithm to railway lines in Tokyo including Keio Line with six types of trains and succeed in relaxing congestion with a small effect on travel time.

DOI： 10.4230/OASIcs.ATMOS.2017.13

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Japanese Society for Artificial Intelligence  

This paper proposes a method for searching cooking recipes by a procedure such as “a tomato is fried.” Although most of methods for cooking recipe search treat recipe text as Bag-of-Words (BoW), it misdetects such a recipe that “fry an onion deeply and serve it with a tomato cube (in which the tomato is not heated).” Our method converts a procedural text to a flow-graph automatically in advance using a dependency parsing technique. In the flow-graph, action sequence that will be performed to an ingredient is easily extracted by tracing the path from the node corresponding to the ingredient to the root node corresponding to the last action. We evaluate our method comparing with a task adapted BoW model as a baseline and the proposed method achieved a precision of 68.8% while the baseline method achieved it of 61.5%.

DOI： 10.1527/tjsai.WII-F

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：一般社団法人 日本機械学会  

In this paper, we propose a heuristic algorithm for a container loading problem for logistic platforms, which is the problem for the Challenge Renault/ESICUP 2015. The three-dimensional container loading problem involves packing a set of cuboid items into bins so as to minimize the total volume used. In this paper, we propose an effective approach to solve this problem based on a greedy strategy. We first generate high-quality stacks that consist of some items and then pack these stacks on the floor of bins, considering the resulting problem as a two-dimensional bin packing problem. The proposed algorithm is tested on a series of instances provided for the challenge. The computational results show that the proposed algorithm performs well on these instances.

DOI： 10.1299/jamdsm.2016jamdsm0041

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：AMER INST MATHEMATICAL SCIENCES-AIMS  

A union I = I-1 boolean OR I-2 boolean OR ... I-m of m sets of items is given, where for each i = 1,2, ... ,m, I-i - {I-ik vertical bar k = 1, 2,..., n} denotes a set of n items of the i-th type and I-ik denotes the k-th item of the i-th type. Each item I-ik has an integral weight w(ik) and an integral priority pik. The food mixture packing problem to be discussed in this paper asks to find a union I' = I-1' boolean OR I-2' boolean OR ... boolean OR I-m' of m subsets of items so that for each i = 1, 2,..., m, the sum weight of chosen items of the i-th type for I-i'subset of I-i is no less than an integral indispensable bound b(i), and the total weight of chosen items for I' is no less than an integral target weight t. The total weight of chosen items for I' is minimized as the primary objective, and further the total priority of chosen items for I' is maximized as the second objective. In this paper, the known time complexity O(mnt+mt(m)) is improved to O(mnt+mt(2)) for an arbitrary m >= 3 by a two-stage constitution algorithm with dynamic programming procedures. The improved time complexity figures out the weak NP-hardness of the food mixture packing problem.

DOI： 10.3934/jimo.2016.12.1057

Web of Science

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

本研究では，料理名によりレシピを検索した結果得られた上位数件のレシピについて，それらのレシピ集合における各レシピの調理手順の典型性を評価するのと同時に，典型的な調理手順を生成する手法を提案する．レシピの調理手順文書は，我々が開発した手法を含む既存手法を活用することで，あらかじめ食材が葉，加工が節点，料理の完成品が根である無順序木に変換されているものと想定する．本研究ではまず，二つのレシピ間の類似度は，それらのツリーの間の編集距離により評価できると考え，2段階の処理により無順序木間の編集距離を算出するアルゴリズムを提案し，更にレシピに適応した編集コストを設定した．次に，集合内におけるあるレシピの典型性は，そのレシピのそれ以外のレシピに対する編集距離の平均により評価できることを示した．最後に，集合内のレシピから，それらよりもより典型的なレシピを生成する手法を提案した．

DOI： 10.14923/transinfj.2015dep0007

CiNii Research

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

A job is called just-in-time if it is completed exactly on its due date. Under multi-slot conditions, each job has one due date per time slot and has to be completed just-in-time on one of its due dates. Moreover, each job has a certain weight per time slot. We would like to find a just-in-time schedule that maximizes the total weight under multi-slot conditions. In this paper, we prove that this problem is NP-hard.

DOI： 10.1587/transinf.2015EDL8171

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

researchmap

記述言語：英語   出版者・発行元：JAPAN SOC MECHANICAL ENGINEERS  

DOI： 10.1299/jamdsm.2016jamdsm0034

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Japan Society of Mechanical Engineers  

DOI： 10.1299/jamdsm.2016jamdsm0034

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

In this paper, we propose a method for extracting a major workflow of cooking procedure from a Japanese recipe on the Web. It is utilized for various applications including recipe search, summarization, and visualization. This major workflow is represented as a tree in which each leaf corresponds to a food or a cooking tool, each intermediate node corresponds to a cooking action, and the root node corresponds to the final cooking action. We had already developed a method for converting a procedural text to a workflow as a directed acyclic graph, and the proposed method is based on the previous one. The results are evaluated by comparing with manually extracted major workflows as a ground truth.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：SPRINGER INT PUBLISHING AG  

A tiling of the plane is a set of figures, called tiles, that cover the plane without gaps or overlaps. On tiling we consider "Escherization problem": Given a closed figure in the plane, find a new closed figure that is similar to the original and can tile the plane. In this study, we give a new formulation of the problem with the weighted Procrustes distance and an algorithm to solve the problem optimally. We conduct computational experiments with animal shape tiles to confirm the effectiveness of the proposed method.

DOI： 10.1007/978-3-319-48532-4_12

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container, where a rectilinear block is a polygonal block whose interior angles are either 90 degrees or 270 degrees . This problem has many applications, such as VLSI design and timber cutting. In this paper, we propose a new solution representation, based on an order of items, to decide a layout of rectilinear blocks whose x-coordinates are fixed. When the shapes of given items have certain characteristics, our representation guarantees optimality. We also generalize this result to the case of general shapes. We then propose an exact algorithm that iteratively generates x-coordinates of items and finds the corresponding optimal layout. The computational results show that our algorithm obtains live exact and one heuristic solutions for six instances and it improves the running time of an existing algorithm.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：JAPAN SOC MECHANICAL ENGINEERS  

In this paper, we study an operational planning and scheduling problem in an automatic picking system. This problem was introduced as a practical benchmark problem arising in logistics and involves assignment and scheduling tasks. We first show the NP-hardness of the problem. We then propose a graph-based heuristic algorithm for computing a good schedule of requests for a given assignment of products. The computational results for benchmark instances show that good schedules of requests are obtained in short computation time.

DOI： 10.1299/jamdsm.2016jamdsm0039

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：PERGAMON-ELSEVIER SCIENCE LTD  

The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container, where a rectilinear block is a polygonal block whose interior angle is either 90 degrees or 270 degrees. There exist many applications of this problem, such as VLSI design, timber/glass cutting, and newspaper layout. In this paper, we design efficient implementations of two construction heuristics for rectilinear block packing. The proposed algorithms are tested On a series of instances, which are generated from nine benchmark instances. The computational results show that the proposed algorithms are especially efficient for large instances with repeated shapes. (C) 2014 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.cor.2014.06.021

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：SPRINGER  

A 2.75-approximation algorithm is proposed for the unconstrained traveling tournament problem, which is a variant of the traveling tournament problem. For the unconstrained traveling tournament problem, this is the first proposal of an approximation algorithm with a constant approximation ratio. In addition, the proposed algorithm yields a solution that meets both the no-repeater and mirrored constraints. Computational experiments show that the algorithm generates solutions of good quality.

DOI： 10.1007/s10479-012-1161-y

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：JAPAN SOC MECHANICAL ENGINEERS  

The lexicographic bi-criteria combinatorial optimization problem to be discussed in this paper is a mathematical model of the food mixture packing performed by so-called automatic combination weighers, and it is described as follows. We are given a union I = I-1 boolean OR I-2 boolean OR . . . boolean OR I-m of m sets of items, where for each i = 1, 2,...,m, I-i = {I-ik vertical bar k = 1,2,...,n denotes a set of n items of the i-th type and I-ik denotes the k-th item of the i-th type. Each item I-ik has an integral weight w(ik) and an integral priority gamma(ik). The problem asks to find a union = I' = I'(1) boolean OR I'(2) boolean OR . . . boolean OR I'(m) of m subsets of items where I'(i) subset of I-i so that the total weight of chosen items for I' is no less than an integral target weight T, and the sum weight of chosen items of the i-th type for is no less than an integral indispensable weight b(i). The total weight of chosen items for I' is minimized as the primary objective, and further the total priority of chosen items for I' is maximized as the second objective. For the case in which there are two types of items (i.e., m = 2), we propose an O(nT) time dynamic programming algorithm, applying a linear search technique. We also conduct numerical experiments to demonstrate the empirical performance.

DOI： 10.1299/jamdsm.2014jamdsm0065

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Operations Research Society of Japan  

This paper presents an efficient algorithm that enumerates all the bottom-left stable positions for a given layout of rectangles. Its time complexity is O((n + K) log n), where n is the number of placed rectangles (i.e., input size) and K is the number of bottom-left stable positions (i.e., output size). This is the first non-trivial algorithm that works for layouts without bottom-left stability and with overlap. In addition to the theoretical analysis of the time complexity, we evaluate the computation time of the proposed algorithm via computational experiments and confirm that it is applicable to very large-scale instances having one million rectangles. © The Operations Research Society of Japan.

DOI： 10.15807/jorsj.57.45

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

The two-dimensional strip packing problem arises in wide variety of industrial applications. In this paper, we focus on the bitmap shape packing problem where a set of arbitrary shaped objects represented in bitmap format should be packed into a larger rectangular container without overlap. The complex geometry of bitmap shapes and large amount of data to be processed make it difficult to check overlaps. For this reason, most of the algorithms in the literature only deal with small-scale instances. We propose an efficient method for checking overlaps and design efficient implementations of two construction algorithms, which are based on the bottom-left strategy. The computational results for a series of well-known benchmark instances show that the proposed algorithms obtain good solutions in remarkably short time and are effective for large-scale instances.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：16th Japan Conference on |rn|Discrete and Computational Geometry and Graphs  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本機械学会  

The rectilinear block packing problem involves packing a set of rectilinear blocks into a larger rectangular container, where a rectilinear block is a polygonal block whose interior angle is either 90° or 270°. This problem is relevant for many applications, such as VLSI design, timber/glass cutting, and newspaper layout. In this paper, we design efficient implementations of two construction heuristic algorithms for rectilinear block packing. The proposed algorithms are tested on a series of instances that are generated from nine benchmark instances. The computational results show that the proposed algorithms are especially efficient for large instances.

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本機械学会  

A job is called just-in-time if it is completed exactly on its due date. Under multi-slot conditions, each job has a due date per slot, and has to be completed just-in-time on one of its due dates. We would like to find a just-in-time schedule that maximizes the total weight under multi-slot conditions. In this paper, we prove that this problem is NP-hard.

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本機械学会  

The lexicographic bi-criteria combinatorial optimization problem to be discussed in this paper is a mathematical model of the food mixture packing performed by so-called automatic combination weighers, and it is described as follows. We are given a union I=I_1&xcup;I_2&xcup;・・・&xcup;I_m of m sets of items, where for i=1,2,・・・,m,I_i={I_<ik>|k=1,2,・・・,n] denotes a set of n items of the i-th type and I_<ik> denotes the k-th items of the i-th type. Each I_<ik> of mn items has an integral weight w_<ik> and an integral priority γ_<ik>. The problem asks to find a union I'=I'_1&xcup;I'_2&xcup;・・・&xcup;I'_m of m subsets of items, where I'_i&vsubne;I_i, so that the total weight of chosen items for I' is no less than an integral target weight T, and the sum weight of chosen items of the i-th type for I'_i is no less than an integral indispensable weight B_i. The total weight of chosen items for I' is minimized as the primal objective, and further the total priority of chosen items for I' is maximized as the second objective. For the case in which there are two types of items (i.e., m=2), and O(nT^2) time dynamic programming algorithm has been designed. In this paper, we improve from O(nT^2) to O(nT) the time complexity.

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：SPRINGER  

Vehicle routing and scheduling problems have a wide range of applications and have been intensively studied in the past half century. The condition that enforces each vehicle to start service at each customer in the period specified by the customer is called the time window constraint. This paper reviews recent results on how to handle hard and soft time window constraints, putting emphasis on its different definitions and algorithms. With these diverse time windows, the problem becomes applicable to a wide range of real-world problems.

DOI： 10.1007/s10479-012-1264-5

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer  

These days, there are more than a million recipes on the Web. When you search for a recipe with one query such as "nikujaga," the name of a typical Japanese food, you can find thousands of "nikujaga" recipes as the result. Even if you focus on only the top ten results, it is still difficult to find out the characteristic feature of each recipe because a cooking is a work-flow including parallel procedures. According to our survey, people place the most importance on the differences of cooking procedures when they compare the recipes. However, such differences are difficult to be extracted just by comparing the recipe texts as existing methods. Therefore, our system extracts (i) a general way to cook as a summary of cooking procedures and (ii) the characteristic features of each recipe by analyzing the work-flows of the top ten results. In the experiments, our method succeeded in extracting 54% of manually extracted features while the previous research addressed 37% of them. © 2013 Springer International Publishing.

DOI： 10.1007/978-3-319-03260-3_21

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：IEEE  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：IEEE  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Springer  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：PERGAMON-ELSEVIER SCIENCE LTD  

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard.
We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem.
We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods. (C) 2011 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.cor.2011.05.019

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：WILEY-BLACKWELL  

This article describes a node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function, and edge consumption functions. The problem is to find the maximum number of rooted in-trees, such that the total consumption of in-trees at each node does not exceed the capacity of the node. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We establish the computational complexity of the problem under various restrictions on consumption functions and graphs. For example, we consider general graphs, acyclic graphs, and complete graphs embedded in the d-dimensional space R-d having edge consumption functions depending only on distances between end nodes. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 59(1), 13-21 2012

DOI： 10.1002/net.20476

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

In this paper, we deal with duplex and quasi-duplex operations in automated food packing systems known as so-called automatic combination weighers. A typical food packing system possesses n weighing hoppers. Some amount of foods is thrown into each hopper, and it is called an item. In a duplex operation, two disjoint subsets I' and I" are simultaneously chosen from the set I of current n items to produce two packages of foods, while in a quasi-duplex operation, I' is first chosen from I and then I" from I - I'. The duplex food packing problem has been formulated as a lexicographic bi-criteria combinatorial optimization problem, and shown in theory to be solved in O(nT(2)) time, where T is an integer denoting the target weight for each package. In this paper, we implement a naive and an improved versions of the O(nT(2)) time algorithm, and examine their execution times by conducting numerical experiments. We also report the empirical performance of the quasi-duplex operation comparing with the duplex operation.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：SPRINGER  

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive away games and that of consecutive home games are at most k. When ka parts per thousand currency sign5, the approximation ratio of the proposed algorithm is bounded by (2k-1)/k+O(k/n) where n denotes the number of teams; when k &gt; 5, the ratio is bounded by (5k-7)/(2k)+O(k/n). For k=3, the most investigated case of the traveling tournament problem to date, the approximation ratio of the proposed algorithm is 5/3+O(1/n); this is better than the previous approximation algorithm proposed for k=3, whose approximation ratio is 2+O(1/n).

DOI： 10.1007/s00453-011-9579-1

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本オペレーションズリサーチ学会  

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard. Previously, we proposed a two-phase heuristic algorithm for this problem. The algorithm generates promising candidate in-trees to be packed in the first phase and computes the packing number of each in-tree in the second phase. In this paper, we improve the first phase algorithm by using Lagrangian relaxation instead of LP (linear programming) relaxation. We conducted computational experiments on graphs used in related papers and on randomly generated instances. The results indicate that our new algorithm generates in-trees faster than our previous algorithm and obtains better solutions than existing algorithms without generating many in-trees.

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Inderscience  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：SPRINGER JAPAN KK  

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k - 1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k - 1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy.

DOI： 10.1007/s00373-011-1014-5

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：SPRINGER JAPAN KK  

How do we most quickly fold a paper strip (modeled as a line) to obtain a desired mountain-valley pattern of equidistant creases (viewed as a binary string)? Define the folding complexity of a mountain-valley string as the minimum number of simple folds required to construct it. We first show that the folding complexity of a length-n uniform string (all mountains or all valleys), and hence of a length-n pleat (alternating mountain/valley), is O(lg(2) n). We also show that a lower bound of the complexity of the problems is Omega(lg(2) n/lg lg n). Next we show that almost all mountain-valley patterns require Omega(n/lg n) folds, which means that the uniform and pleat foldings are relatively easy problems. We also give a general algorithm for folding an arbitrary sequence of length n in O(n/lg n) folds, meeting the lower bound up to a constant factor.

DOI： 10.1007/s00373-011-1019-0

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：7th Hungarian-Japanese Symposium on Discrete |rn|Mathematics and Its Applications  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：INDERSCIENCE ENTERPRISES LTD  

This paper proposes a routing strategy for wireless sensor networks that is valid even when the sensor nodes are distributed non-uniformly. Energy efficiency is the most important consideration in wireless sensor networks; hence, global communication should be achieved by combinations of local messages. We first propose a new underlying graph called the almost Delaunay planar net, which can be calculated from information local to the sensor nodes. We statistically analyse the efficiency of existing routing strategies in the almost Delaunay planar net. We also propose a new routing strategy that always guarantees the reachability on planar graphs, including the almost Delaunay planar net. We show that the proposed routing strategy exhibits good performance if the underlying graph in the sensor network is the almost Delaunay planar net.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：SPRINGER HEIDELBERG  

Vehicle routing and scheduling problems have a wide range of applications and have been intensively studied in the past half century. The condition that enforces each vehicle to start service at each customer in the period specified by the customer is called the time window constraint. This paper reviews recent results on how to handle hard and soft time window constraints, putting emphasis on its different definitions and algorithms. With these diverse time windows, the problem becomes applicable to a wide range of real-world problems.

DOI： 10.1007/s10288-010-0144-6

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：8th International Conference on |rn|the Practice and Theory of Automated Timetabling  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Elsevier  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：SPRINGER-VERLAG BERLIN  

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least; 2k-1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k +ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that; in dimension d the required coverage is at most d(k-1) + 1. Lower bounds are also given for all of the above problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations.
From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast; with the planar case, for which this decision problem is easy.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

In this paper, we discuss a lexicographic bi-criteria combinatorial optimization problem arising in automated food packing systems known as so-called automatic combination weighers. A typical food packing system possesses n weighing hoppers. Some amount of foods is thrown into each hopper, and it is called an item. We deal with a duplex packing operation such that the food packing system chooses two disjoint subsets I′ and I″ from the set I of the current n items to produce two packages of foods. After choosing two subsets I′ and I″, the resulting empty hoppers are supplied with next new items, and the set I is updated. By repeating the duplex packing operation, a large number of packages are produced two by two. The primary objective of lexicographic bi-criteria duplex food packing problem is to minimize the total weight of chosen items for two packages, making the total weight of each package no less than a specified target weight T. The second objective is to maximize the total priority of chosen items for two packages so that items with longer durations in hoppers are preferably chosen. The priority of an item is given as its duration in hopper. In this paper, we prove that the lexicographic bi-criteria duplex food packing problem can be solved in O(nT 2) time by dynamic programming if all input data are integral. © 2010 IEEE.

DOI： 10.1109/INDIN.2010.5549629

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：WILEY-BLACKWELL  

The irregular strip-packing problem (ISP) requires a given set of non-convex polygons to be placed without overlap within a rectangular container having a fixed width and a variable length, which is to be minimized. As a core sub-problem to solve ISP, we consider an overlap minimization problem (OMP) whose objective is to place all polygons into a container with given width and length so that the total amount of overlap between polygons is made as small as possible. We propose to use directional penetration depths to measure the amount of overlap between a pair of polygons, and present an efficient algorithm to find a position with the minimum overlap for each polygon when it is translated in a specified direction. Based on this, we develop a local search algorithm for OMP that translates a polygon in horizontal and vertical directions alternately. Then we incorporate it in our algorithm for OMP, which is a variant of the guided local search algorithm. Computational results show that our algorithm improves the best-known values of some well-known benchmark instances.

DOI： 10.1111/j.1475-3995.2009.00707.x

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：International Network Optimization Conference  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：25th European Workshop on Computational Geometry  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：25th European Workshop on Computational Geometry  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

In hop-by-hop networks, provision of multipath routes for all nodes can improve fault tolerance and performance. In this paper we study the multipath route calculation by constructing a directed acyclic graph (DAG) which includes all edges in the network. We define new DAG construction problems with the objectives of 1) maximizing the minimum connectivity, 2) maximizing the minimum max-flow, and 3) maximizing the minimum max-flow as an extension of shortest path routing. A family of new algorithms called Maximum Alternative Routing Algorithms (MARAs) is described, proven formally to solve the problems optimally, and contrasted with existing multipath algorithms. MARAs are evaluated for the number of paths, the length of paths, the computational complexity, and the computation time, using simulations based on several real Internet Autonomous System (AS) network topologies. We show that MARAs run in sub-second times on moderate-speed processors and achieve a significant increase in the number of paths compared to existing multipath routing algorithms. These results should help further the process of deploying multipath routing in real-world networks.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：SPRINGER-VERLAG BERLIN  

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose an approximation algorithm for the traveling tournament; problem with the constraints such that both the number of consecutive away games and that; of consecutive home games are at most k. When k &lt;= 5, the approximation ratio of the proposed algorithm is bounded by (2k - 1)/k + O(k/n) where n denotes the number of teams; when k &gt; 5, the ratio is bounded by (5k - 7)/(2k) + O(k/n). For k = 3, the most investigated case of the traveling tournament problem to date, the approximation ratio of the proposed algorithm is 5/3 + O(1/n); this is better than the previous approximation algorithm proposed for k = 3, whose approximation ratio is 2 + O(1/n).

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：SPRINGER-VERLAG BERLIN  

How do we most quickly fold a paper strip (modeled as a line) to obtain a desired mountain-valley pattern of equidistant creases (viewed as a binary string)? Define the folding complexity of a mountain-valley string as the minimum number of simple folds required to construct it. We show that the folding complexity of a length-n uniform string (all mountains or all valleys), and hence of a length-n pleat (alternating mountain/valley), is polylogarithmic in n. We also show that the maximum possible folding complexity of any string of length n is O(n/ lg n), meeting a previously known lower bound.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：11th International Conference on Humans |rn|and Computers  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Elsevier  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：7th International Conference on the Practice and Theory of Automated Timetabling  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：ELSEVIER SCIENCE BV  

We propose an iterated local search algorithm for the vehicle routing problem with time window constraints. We treat the time window constraint for each customer as a penalty function, and assume that it is convex and piecewise linear. Given an order of customers each vehicle to visit, dynamic programming (DP) is used to determine the optimal start time to serve the customers so that the total time penalty is minimized. This DP algorithm is then incorporated in the iterated local search algorithm to efficiently evaluate solutions in various neighborhoods. The amortized time complexity of evaluating a solution in the neighborhoods is a logarithmic order of the input size (i.e., the total number of linear pieces that define the penalty functions). Computational comparisons on benchmark instances with up to 1000 customers show that the proposed method is quite effective, especially for large instances. (C) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2007.04.022

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Three variants of the two dimensional packing problem are considered, where the items to be packed are (a) rectangles with fixed widths and heights, (b) rectangles with adjustable widths and heights, or (c) irregular shapes. All problems are solved by hybrid metaheuristics that combine local search and mathematical programming techniques of linear, nonlinear and/or dynamic programming. Basic ideas of these algorithms are explained on a unified basis, together with some computational results. It appears to indicate that mathematical programming is a vital tool for enhancing metaheuristic algorithms. © 2008 Springer-Verlag Berlin Heidelberg.

DOI： 10.1007/978-3-540-78295-7_7

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：7th Metaheuristics International Conference  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：SPRINGER-VERLAG BERLIN  

The traveling tournament problem considers scheduling round-robin tournaments that minimize traveling distance, which is an important issue in sports scheduling. Various studies on the traveling tournament problem have appeared in recent years, and there are some variants of this problem. In this paper, we deal with the constant distance traveling tournament problem, which is a special class of the traveling tournament problem. This variant is essentially equivalent to the problem of 'maximizing breaks' and that of 'minimizing breaks', which is another significant objective in sports scheduling. We propose a lower bound of the optimal value of the constant distance traveling tournament problem, and two constructive algorithms that produce feasible solutions whose objective values are close to the proposed lower bound. For some size of instances, one of our algorithms yields optimal solutions.

Web of Science

researchmap

出版者・発行元：Chapman and Hall/CRC  

DOI： 10.1201/9781420010749.ch36

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：ELSEVIER SCIENCE BV  

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization. (c) 2006 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2006.04.009

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：6th International Conference on the Practice and Theory of Automated Timetabling  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本機械学会  

The irregular strip packing problem asks to place a set of polygons within a rectangular strip of fixed height without overlap, so as to minimize the strip width required. We consider an overlap minimization problem which minimizes the amount of overlap penalty for all pairs of polygons within a given bound of strip width. We propose a local search algorithm which translates a polygon in horizontal and vertical directions iteratively, and incorporate it in metaheuristic approaches called the iterated local search and the guided local search. Computational results show that our algorithm is competitive with other existing algorithms.

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：ELSEVIER SCIENCE BV  

The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form, For this problem. we have previously presented local search algorithms using a pair of permutations of rectangles to represent a solution. In this paper. we propose speed-up techniques to evaluate solutions in various neighborhoods. Computational results for the rectangle packing problem and a real-world scheduling problem exhibit good prospects of the proposed techniques, (c) 2004 Elsevier B.V. All rights reserved.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：6th Metaheuristics International Conference  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Springer  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：INST OPERATIONS RESEARCH MANAGEMENT SCIENCES  

W e propose local search algorithms for the vehicle routing problem with soft time-window constraints. The time-window constraint for each customer is treated as a penalty function, which is very general in the sense that it can be nonconvex and discontinuous as long as it is piecewise linear. In our algorithm, we use local search to assign customers to vehicles and to find orders of customers for vehicles to visit. Our algorithm employs an advanced neighborhood, called the cyclic-exchange neighborhood, in addition to standard neighborhoods for the vehicle routing problem. After fixing the order of customers for a vehicle to visit, we must determine the optimal start times of processing at customers so that the total penalty is minimized. We show that this problem can be efficiently solved by using dynamic programming, which is then incorporated in our algorithm. We report computational results for various benchmark instances of the vehicle routing problem. The generality of time-window constraints allows us to handle a wide variety of scheduling problems. As an example, we mention in this paper an application to a production scheduling problem with inventory cost, and report computational results for real-world instances.

DOI： 10.1287/trsc.1030.0085

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：スケジューリング学会  

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, and propose a local search algorithm, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general, and can treat various scheduling problems, e.g., with earliness and tardiness costs, and flexible processing time. In our algorithm, local search is used to determine routes. After fixing the route for a vehicle, we must determine the optimal start times of processing at customers so that the total cost is minimized. This subproblem is NP-hard when cost functions are general, and can be efficiently solved with dynamic programming when traveling cost functions are convex. We then report computational results for benchmark instances, and confirm the usefulness of the proposed generalization.

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：5th Metaheuristics International Conference  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：SPRINGER-VERLAG  

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms.

DOI： 10.1007/s10107-003-0427-1

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：5th Metaheuristics International Conference  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：INT INST INFORMATICS & SYSTEMICS  

We consider the two dimensional cutting stock problem, which arises in many industries. In recent industrial applications, it is argued that the setup costs for changing patterns become more dominant and it is impractical to use many different patterns. Therefore, we consider the pattern restricted two dimensional cutting stock problem, in which the total number of applications of cutting patterns is minimized while the number of different cutting patterns is given as a parameter n. For this problem, we develop a local search algorithm. As the size of the neighborhood plays a crucial role in determining the efficiency of local search, we propose to use linear programming techniques for the purpose of restricting the number of solutions in the neighborhood. To determine a cutting pattern in each solution, we have to place all products (rectangles) in the two dimensional area without mutual overlap. For this purpose, we develop a heuristic algorithm using an existing rectangle packing algorithm with a coding scheme called sequence pair. Finally, we generate random test instances of this problem, and conduct computational experiments to see the effectiveness of the proposed algorithm.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：4th Metaheuristics International Conference  

researchmap

記述言語：英語   著書種別：学術書

researchmap

記述言語：英語   出版者・発行元：一般社団法人電子情報通信学会  

CiNii Books

researchmap

記述言語：英語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：英語   出版者・発行元：京都大学  

CiNii Books

researchmap

その他リンク： http://hdl.handle.net/2433/172987

記述言語：英語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：日本語   出版者・発行元：一般社団法人情報処理学会  

本研究では,頂点容量制約付き有向全域木パッキング問題を扱う.この問題は入力として, 有向グラフ,ルート頂点,頂点容量,辺の始点側と終点側それぞれに消費量が与えられる.目的はルート頂点に流入する有向全域木のパッキング回数を最大化することである.ただし,有向全域木の各頂点に対する消費量の合計は,頂点容量を超えてはいけない.以前,我々はこの問題に対して2段階の発見的解法を提案した.このアルゴリズムは,1段階目に木の候補を生成し,2段階目に木のパッキング回数を決定する.本研究では,ラグランジュ緩和を用いることで1段階目を改善した.計算実験により,提案アルゴリズムは以前のアルゴリズムより速く木を生成でき,少ない木の候補でもよい解を得ることを確認した.

CiNii Books

researchmap

出版者・発行元：京都大学  

CiNii Books

researchmap

その他リンク： http://hdl.handle.net/2433/171697

記述言語：日本語   出版者・発行元：FIT(電子情報通信学会・情報処理学会)運営委員会  

CiNii Books

researchmap

記述言語：日本語   出版者・発行元：京都大学  

CiNii Books

researchmap

その他リンク： http://hdl.handle.net/2433/170509

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：日本評論社  

CiNii Books

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：英語   出版者・発行元：一般社団法人情報処理学会  

本研究では，有向グラフ，根，点容量関数，枝消費関数が与えられたとき，根付き全域内向木をいくつ詰め込めるかという問題を扱う．枝消費関数によって根付き全域内向木の各点における消費が決まる．制約は，各点において，根付き内向木の消費の合計が点容量を超えないことである．この問題を点容量付き内向木詰込問題とよぶことにする．この問題は，センサーネットワークの研究における最も重要な問題である，ネットワークライフタイム問題の1つである．本研究では，グラフが非巡回的な場合，消費関数が距離に依存する場合，などにおける点容量付き内向木詰込問題の計算複雑度を明らかにした．In this paper, we deal with a vertex capacitated arborescence packing problem. The input consists of a directed graph, a root vertex, a vertex capacity function and edge consumption functions. The problem is to find the maximum number of rooted arborescences such that the total consumption of arborescences at each vertex does not exceed the capacity of the vertex. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We reveal the computational complexity of the problem in several cases; e.g., the given graph is acyclic or not, the instance is metric dependent.

CiNii Books

researchmap

その他リンク： http://id.nii.ac.jp/1001/00031601/

記述言語：英語   出版者・発行元：一般社団法人情報処理学会  

長方形配置問題は 与えられた長方形を重なりなく できる限り密に配置することを目的とする問題である.本問題に対する発見的解法の一つとして Burkeらによって提案されたbest-fit 法[Operations Research 52 (2004) 655--671]があり その性能が広く注目されている.本研究では best-fit法の効率的な実現法を提案し 計算量の観点での最適性を示す.我々の実現法は 長方形数をnとすると O(n)の領域と O(n log n)の計算量を必要とする.また 数値実験を通して best-fit 法の実用性について論じる.We investigate the best-fit heuristic algorithm by Burke et al. [Operations Research 52 (2004) 655--671] for the rectangular strip packing problem. For its simplicity and good performance, the best-fit heuristic has become one of the most significant algorithms for the rectangular strip packing. In this paper, we propose an efficient implementation of the best-fit heuristic that requires linear space and O(n log n) time, where n is the number of rectangles. We prove that this time complexity is optimal, and show practical usefulness of our implementation via computational experiments.

CiNii Books

researchmap

その他リンク： http://id.nii.ac.jp/1001/00031656/

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：英語   出版者・発行元：京都大学  

CiNii Books

researchmap

その他リンク： http://hdl.handle.net/2433/24859

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：日本語   出版者・発行元：京都大学  

CiNii Books

researchmap

その他リンク： http://hdl.handle.net/2433/42658

記述言語：日本語   出版者・発行元：一般社団法人情報処理学会  

長方形詰込み問題とは 様々な大きさの長方形を二次元平面上に互いに重ならないように配置する問題であり NP 困難であることが知られている.我々は 以前この問題に一般的な配置コストを導入し 局所探索法に基づくアルゴリズムを提案した.この問題は非常に汎用的であり 様々な配置問題やスケジューリング問題を扱うことが可能である.また 提案アルゴリズムの特徴として 順列対表現を用いて解を表現し 低次の多項式時間で順列対から配置を求めるという点が挙げられる.本研究では このアルゴリズムをもとに 局所探索における様々な近傍において 解一つ当りの評価を高速に行う手法を提案する.配置問題や実際のスケジューリング問題を用いた数値実験を行い 提案手法が従来のアルゴリズムと比較して優れていることを確認した.The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we had proposed local search algorithms which used a pair of permutations of rectangles to represent a solution. In this paper, we propose new speed-up techniques to evaluate solutions in various neighborhoods, and report computational results for two types of problems, one is that of area minimization and the other is taken from real-world scheduling, which exhibit good prospects of the proposed techniques.

CiNii Books

researchmap

その他リンク： http://id.nii.ac.jp/1001/00031953/

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

CiNii Books

researchmap

記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語   会議種別：口頭発表（招待・特別）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：英語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：英語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語  

researchmap

記述言語：日本語   会議種別：公開講演，セミナー，チュートリアル，講習，講義等  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap