記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

DOI： 10.1007/s10696-018-9320-3

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

The purpose of this study is to propose an exact algorithm for the unrestricted block relocation problem with distinct priorities. In this problem, a storage area is considered where blocks of the same size are stacked vertically in tiers. Because we can access only topmost blocks, relocations of blocks are required when other blocks are retrieved. The objective is to minimize the total number of such relocations necessary for retrieving all the blocks one by one according to a specified order. In the restricted version of this problem, only the topmost block above the target block is relocatable. On the other hand, no such restriction is imposed on the unrestricted problem, which is considered in this study. We also assume that each block is assigned a distinct retrieval priority and the retrieval order of blocks is unique. To improve the efficiency of a branch-and-bound algorithm for this problem, we propose several dominance properties to eliminate unnecessary nodes in the search tree. Furthermore, we propose a new lower bound of the total number of relocations. The effectiveness of the proposed exact algorithm is verified by numerical experiments for benchmark instances in the literature.

DOI： 10.1016/j.cor.2018.02.019

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

Container terminals around the world regularly re-sort the containers they store according to their retrieval times in a process called pre-marshalling, thus ensuring containers are efficiently transferred through the terminal. State-of-the-art algorithms struggle to find optimal solutions for real-world sized pre-marshalling problems. To this end, we introduce an improved exact algorithm using an iterative deepening branch and bound search, including a novel lower bound computation, a new branching heuristic, new dominance rule and a new greedy partial solution completion heuristic. Our approach finds optimal solutions for 161 more instances than the state-of-the-art algorithm on two well known, difficult pre-marshalling datasets, and solves all instances in three other datasets in just several seconds. Furthermore, we find optimal solutions for a majority of real-world sized instances, and feasible solutions with very low relaxation gaps on those instances where no optimal could be found. (C) 2017 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ejor.2017.05.046

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

A multi-car elevator system is an elevator system that has more than one car installed in each elevator shaft. This system enables us to improve the transportation capability without increasing the occupied floor space. The primary purpose of this study is to consider the group control problem of operating cars efficiently without collision nor reversal in a multi-car elevator system, based on a detailed and realistic model where floor stoppage time of cars cannot be known in advance. In the context of elevator systems, reversal means that a car travels in the direction opposite to the desired direction of on-board passengers, which is prohibited because it makes passengers uncomfortable. We first propose an optimization-based collision and reversal avoidance method to operate cars in the same shaft. Next, we construct simple methods to allocate calls to individual cars under immediate and delayed guidance policies. Under the immediate guidance policy a call is allocated to a car immediately after it is registered, while under the delayed guidance policy the allocation may be changed until it is actually served. The effectiveness of the proposed group control method is examined by computer simulation.

DOI： 10.1007/s10696-016-9238-6

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

We consider the flowshop problem on two machines with sequence-independent setup times to minimize total completion time. Large scale network flow formulations of the problem are suggested together with strong Lagrangian bounds based on these formulations. To cope with their size, filtering procedures are developed. To solve the problem to optimality, we embed the Lagrangian bounds into two branch and-bound algorithms. The best algorithm is able to solve all 100-job instances of our testbed with setup times and all 140-job instances without setup times, thus significantly outperforming the best algorithms in the literature. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ejor.2016.02.003

Web of Science

researchmap

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

This study addresses the single-machine scheduling problem with a finite capacity input buffer where storage locations in the buffer are considered. The problem to minimize the size of the input buffer is first formulated as a mixed-integer linear programming problem, and next we propose a method that determines the starting times on the machine and the locations in the buffer separately by the corresponding MILP problems. The effectiveness of the proposed method is demonstrated by numerical experiment. It is also shown that considering storage locations does not affect the minimum buffer size at least for the instances considered in this study.

Web of Science

researchmap

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

The block relocation problem, which is also known as the container relocation problem, is an optimization problem to find an optimal sequence of operations for retrieving blocks (containers) from a container yard in a given order. The objective function to be minimized is the number of necessary relocations. In this study, we propose an efficient exact algorithm for two variants of the block relocation problem, those with distinct and duplicate retrieval priorities. In the former problem, the retrieval order of blocks is uniquely provided, whereas in the latter problem, it is given only among groups of blocks. The primary contribution of this study is a tighter lower bound of the number of relocations than existing ones. This enables us to construct a faster branch-and-bound algorithm. Its effectiveness is demonstrated by extensive numerical experiments.

DOI： 10.1109/TASE.2015.2434417

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

The block (container) relocation problem is an optimization problem to minimize the number of relocation operations necessary for retrieving blocks (containers) stacked in tiers, according to a given order. Most of the existing exact approaches for this problem considered the restricted version of the problem where the block to be relocated next is uniquely determined. However, the unrestricted version of the problem without such a restriction is more preferable in order to reduce the number of required relocation operations. The purpose of this study is to derive dominance properties for the unrestricted block relocation problem, which enable us to exclude some of feasible solutions. Their effectiveness will be demonstrated by embedding them in a branch-and-bound algorithm and applying it to benchmark instances.

DOI： 10.1109/CoASE.2015.7294130

Web of Science

researchmap

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

The block (container) relocation problem is an optimization problem that typically arises in container terminals. Its objective is to minimize the number of relocation operations necessary for retrieving all blocks (containers) stacked in tiers according to a given order. In our previous study, we considered the unrestricted version of the problem where no restriction is imposed on relocatable blocks, and proposed two dominance properties for it. However, they considered only two successive operations. The purpose of this study is to extend them for any two operations. They enable us to improve the efficiency of the branch-and-bound algorithm for the problem, which will be verified by numerical experiment.

DOI： 10.1109/IEEM.2015.7385641

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

In this paper efficient exact algorithms are proposed for the planted (l, d)-motif search problem. This problem is to find all motifs of length l that are planted in each input string with at most d mismatches. The "quorum" version of this problem is also treated in this paper to find motifs planted not in all input strings but in at least q input strings. The proposed algorithms are based on the previous algorithms called qPMSPruneI and qPMS7 that traverse a search tree starting from a l-length substring of an input string. To improve these previous algorithms, several techniques are introduced, which contribute to reducing the computation time for the traversal. In computational experiments, it will be shown that the proposed algorithms outperform the previous algorithms.

DOI： 10.1109/TCBB.2014.2306842

Web of Science

researchmap

記述言語：日本語   出版者・発行元：自動制御連合講演会  

宇宙太陽光発電では，宇宙空間で発電した電力を大規模なフェーズドアレイアンテナによりマイクロ波に変換し，地上の受電設備へ無線伝送する．著者らはすでに，損失のあるディジタル移相器を用いたフェーズドアレイアンテナにおいて，各素子の励振位相を適切に調整して望ましい方向への伝送電力を最大化する問題を組合せ最適化問題として定式化するとともに，効率のよいアルゴリズムを提案している．本研究では，各素子の励振振幅も同時に最適化する問題に対して本アルゴリズムを拡張する．そして，計算機実験を用いてその有効性を検証する．

DOI： 10.11511/jacc.57.0_1935

CiNii Article

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Institute of Electronics, Information and Communication, Engineers, IEICE  

An efficient beamforming algorithm for large-scale phased arrays with lossy digital phase shifters is presented. This problem, which arises in microwave power transmission from solar power satellites, is to maximize the array gain in a desired direction with the gain loss of the phase shifters taken into account. In this paper the problem is first formulated as a discrete optimization problem, which is then decomposed into element-wise subproblems by the real rotation theorem. Based on this approach, a polynomial-time algorithm to solve the problem numerically is constructed and its effectiveness is verified by numerical simulations. Copyright © 2014 The Institute of Electronics, Information and Communication Engineers.

DOI： 10.1587/transcom.E97.B.783

Web of Science

Scopus

researchmap

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

The block relocation problem, which is also known as the container relocation problem, is to find an optimal sequence of operations for retrieving blocks (containers) from a container bay composed of several stacks. The primary contribution of this study is that a lower bound better than those in the existing studies is proposed. This enables us to construct a faster branch-and-bound algorithm than the exact algorithms in the literature. Its effectiveness will be demonstrated by extensive numerical experiments.

DOI： 10.1109/CoASE.2014.6899296

Scopus

J-GLOBAL

researchmap

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

This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors' previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness-tardiness problems, and most instances with 100 jobs of the former problem. © 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ejor.2013.02.048

Scopus

CiNii Article

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved. (C) 2012 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.cor.2012.07.004

Web of Science

CiNii Article

researchmap

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

An efficient algorithm was developed for transmitting power maximization of phased arrays including amplitude degradation. A large-scale phased array will be adopted as transmitting antenna of a solar power satellite project. The amplitude of each antenna element will be degraded at every phase shift due to long-term operation and failure of antenna units. This array problem is formulated as a discrete optimization problem, and decomposed into element-wise subproblems by utilizing the real rotation theorem. Then a polynomial-time algorithm to solve the problem numerically was constructed.

Web of Science

researchmap

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

The purpose of this study is to model the car operation problem in multi-car elevator systems. The multi-car elevator system is such a system that more than one car is installed in every elevator shaft. To take its full advantage, intelligent car operation is necessary so that neither collisions nor reversal occurs. In this paper we will propose a mathematical model for the car operation problem in multi-car elevator systems. First, it will be formulated as a mixed-integer linear programming problem, and next a branch-and-bound algorithm will be proposed. Then, the validity of the model and the effectiveness of the algorithm will be examined by numerical experiments.

DOI： 10.1109/SMC.2013.45

Web of Science

J-GLOBAL

researchmap

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

The purpose of this study is to examine how idle time treatment in the single-machine scheduling problem with distinct (unequal) release dates affects schedules. For this purpose, two types of settings are considered: any idle time is permitted and unforced idle time is forbidden. In the latter setting, idle time is permitted only when no jobs are available, that is, release dates of unprocessed jobs are larger than the current time instant. Under these two idle time settings, the problem is solved both offline and online. In offline scheduling, all job information is known in advance and the schedule is optimized only once at time zero while in online scheduling, the schedule is re-optimized for only currently available jobs every time when a new job becomes available at its release date. Benchmark instances in the literature are solved by these approaches and the effect of idle time treatment on the obtained schedules is examined.

DOI： 10.1115/ISFA2012-7172

Web of Science

J-GLOBAL

researchmap

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

researchmap

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

This paper proposes an efficient exact algorithm for the general single-machine scheduling problem where machine idle time is permitted. The algorithm is an extension of the authors' previous algorithm for the problem without machine idle time, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. We first extend our previous algorithm to the problem with machine idle time and next propose several improvements. Then, the proposed algorithm is applied to four types of single-machine scheduling problems: the total weighted earliness-tardiness problem with equal (zero) release dates, that with distinct release dates, the total weighted completion time problem with distinct release dates, and the total weighted tardiness problem with distinct release dates. Computational experiments demonstrate that our algorithm outperforms existing exact algorithms and can solve instances of the first three problems with up to 200 jobs and those of the last problem with up to 80 jobs.

DOI： 10.1007/s10951-011-0242-0

Web of Science

CiNii Article

researchmap

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

The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast. (C) 2011 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.cor.2011.06.005

Web of Science

CiNii Article

researchmap

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

In multi-car elevator systems, several cars are installed in each elevator shaft to improve the transportation capability without increasing the occupied floor space. In our previous studies, we proposed an optimization-based method to avoid collisions between cars in the same shaft of multi-car elevator systems. However, it was applicable only to the systems with two cars in each shaft. In this study we will improve this method so that it can handle more than two cars. Then, its effectiveness will be examined by computer simulation.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：システム制御情報学会  

The purpose of this study is to construct a solution algorithm for the two-machine permutation flowshop problem based on the dynasearch. The dynasearch is an efficient local search algorithm that employs a special neighborhood structure called dynasearch swap neighborhood. Its primary advantage is that the neighborhood of a solution can be explored in polynomial time although it is composed of an exponential number of solutions. The dynasearch for machine scheduling was originally developed for the single-machine total weighted tardiness problem. Then, it was extended to the problem with idle time and setup times. This study further extends the dynasearch to the two-machine permutation flowshop problem and its effectiveness is examined by numerical experiments for both total weighted tardiness and total weighted earliness-tardiness objectives.

DOI： 10.5687/iscie.24.23

CiNii Article

CiNii Books

researchmap

その他リンク： http://repository.kulib.kyoto-u.ac.jp/dspace/handle/2433/171961

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

This paper is devoted to the scheduling problem with rejection. This problem is to determine which jobs should be accepted or rejected, and then to schedule the accepted jobs on machines so that total rejection cost plus schedule cost is minimized, or total revenue minus schedule cost is maximized. The latter equivalent maximization problem is called the order acceptance and scheduling problem. The main result of this paper is very simple. The scheduling problem with rejection in which the schedule cost is the sum of job completion costs can be converted into the ordinary scheduling problem with slightly modified job completion costs. This enables us to apply algorithms developed for ordinary scheduling problems to the corresponding scheduling problems with rejection. The effectiveness of the proposed conversion method will be demonstrated by numerical experiment: Several types of single-machine scheduling problems with rejection are solved by our exact algorithms for ordinary single-machine scheduling problems. As a result, the proposed method is shown to outperform the best branch-and-bound algorithm so far. © 2011 IEEE.

DOI： 10.1109/CASE.2011.6042459

Scopus

J-GLOBAL

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

A large-scale phased array antenna will be adopted as a microwave power transmitter of solar power satellites. The objective of the present study is to maximize transmitting power of a large-scale phased array antenna including lossy digital phase shifters. In the present paper, we describe a newly developed algorithm for transmitting power maximization, and demonstration experiments of a one-dimensional 12-elements phased array antenna including 4-bit lossy digital phase shifters. We confirmed effectiveness of the developed algorithm through the demonstration experiments as well as numerical simulations. © 2011 IEEE.

DOI： 10.1109/URSIGASS.2011.6050554

Scopus

J-GLOBAL

researchmap

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

A multi-car elevator system is such an elevator system that more than one car is installed in every elevator shaft. In this study we consider a call allocation problem in group control for a multi-car elevator system with non-immediate passenger guidance. In nonimmediate passenger guidance the car allocated to a passenger is indicated to him/her just before the car arrives at the floor where he/she is waiting. On the other hand, in immediate passenger guidance the car is indicated immediately after a call is registered at an elevator hall. We will propose a simple call allocation algorithm by a local search for nonimmediate passenger guidance and compare its transportation capability with that of immediate passenger guidance by computer simulation.

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

CiNii Article

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

The closest string problem that arises in both computational biology and coding theory is to find a string that minimizes the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as an integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Numerical experiments will show the effectiveness of the proposed algorithm.

DOI： 10.1109/ICSMC.2010.5641888

Web of Science

J-GLOBAL

researchmap

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

DOI： 10.1007/s10951-008-0093-5

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

In this study we improve our previous exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. The previous algorithm successfully solved 89 out of 100 open benchmark instances with 60 jobs, but 11 instances were left open due to shortage of memory space although we did not restrict the computational time. To cope with it, we improve the algorithm to reduce memory usage and then it is applied to the 11 open instances. Numerical experiments will show that 9 instances are now optimally solved.

CiNii Article

CiNii Books

researchmap

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

In this study the routing problem for unit-load automated storage and retrieval systems (AS/RSs) with separate input and output points is considered under the shared storage policy. The problem is to find an optimal travel route of a S/R (storage and retrieval) machine to process given storage and retrieval requests so that the total travel time is minimised, where the input and output points are possibly separate and the shared storage policy is assumed. We first give two types of formulations as 0-1 integer linear programming problems corresponding to two types of dwell point settings: the dwell point is the input point and the output point. Next, we propose a simple but efficient exact solution algorithm based on the formulations that utilises a general MILP (Mixed Integer Linear Programming) solver. Its efficiency is then demonstrated by numerical experiments. Instances with 400 items (200 for each storage and retrieval) are solved within 100 s.

DOI： 10.1080/00207540701644177

Web of Science

CiNii Article

researchmap

その他リンク： http://repository.kulib.kyoto-u.ac.jp/dspace/handle/2433/88084

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

CiNii Article

researchmap

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

The purpose of this paper is to propose a new branch-and-bound algorithm for a class of scheduling problems to minimize total tardiness on identical parallel machines. In this algorithm, the Lagrangian relaxation technique is applied to obtain a tight lower bound. In addition, the job dominance conditions for the single machine total tardiness problem are utilized for both restricting branches and improving the lower bound. As will be shown by computational experiments, instances with up to 25 jobs and with any number of machines are optimally solved by the proposed algorithm. (C) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ijpe.2007.10.006

Web of Science

researchmap

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

In this paper we propose an exact algorithm for the general single-machine scheduling problem where machine idle time is permitted. The algorithm is an extension of the authors' previous algorithm for the problem without machine idle time, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In this algorithm a lower bound is computed by applying dynamic programming to a Lagrangian relaxation of the original problem and then it is successively improved by imposing additional constraints on the relaxation until the gap between lower and upper bounds diminishes. Unnecessary dynamic programming states are eliminated in the course of the algorithm to reduce both computational efforts and memory usage. Experimental results show that the proposed algorithm can solve 200 jobs instances of the single-machine total weighted earliness-tardiness problem.

DOI： 10.1109/COASE.2008.4626508

Web of Science

J-GLOBAL

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

This paper proposes a hybrid algorithm for the input/output scheduling problem of multi-shuttle automated storage and retrieval systems (AS/RSs). This problem is to find a minimum travel route of a multi-shuttle storage and retrieval (S/R) machine to process given storage and retrieval requests for a storage rack. The proposed algorithm is based on the exact algorithm previously proposed by the author. In the first stage of the algorithm, a tabu search is used to improve the solutions obtained while column and cut generation is applied to an LP relaxation of the problem. The tabu search solutions are utilized in the second stage as columns of a set-partitioning formulation of the problem, and it is solved by a general MILP solver. The effectiveness of the proposed algorithm is examined by numerical experiments.

DOI： 10.1109/SICE.2007.4421438

Web of Science

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：The Society of Instrument and Control Engineers  

In this paper we propose an exact algorithm for the input/output scheduling problem in an end-of-aisle multi-shuttle automated storage/retrieval system (AS/RS) with dedicated storage. This problem is to determine an optimal travel route of a multi-shuttle stacker crane to meet a given set of storage and retrieval orders, and it can be formulated as a class of capacitated vehicle routing problems. In our algorithm, column and cut generation is applied to a linear relaxation problem of the original problem to obtain a good lower bound. In the course of the lower bound calculation, we apply a greedy heuristics and a local search to a solution of the relaxed problem in order to obtain a good upper bound (a heuristic solution). If there is a gap between the lower and upper bounds, we try to obtain an exact solution by solving a binary programming problem with a restricted number of columns. We examine the effectiveness of our algorithm by numerical experiments.

DOI： 10.9746/sicetr1965.42.1058

CiNii Article

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

出版者・発行元：システム制御情報学会  

本研究では，乗客がエレベータホールで自分の行き先階を直接登録する行き先階登録方式エレベータにおいて，乗客を各エレベータに割り当てる方法を提案する．具体的には，エレベータがホールに到着する直前に乗客に乗車を案内する，非即時案内表示方式を用いるものとし，エレベータの停車回数および乗客のサービス完了時間を考慮した乗客の割り当て方法を提案する．そして，シミュレーテッド・アニーリング法による乗客割り当てと比較する．

DOI： 10.11509/sci.SCI06.0.236.0

CiNii Article

researchmap

出版者・発行元：システム制御情報学会  

本研究では、乗客がエレベータホールで直接行き先階を登録する、行き先階登録方式エレベータシステムの群管理を扱う。本研究では「エレベータホールで行き先階が登録されていないときのみボタンを押す」という現実的状況を考慮し、乗客推定を用いた、効率的な割り当て方法（乗客を各エレベータに割り当てる方法）を検討する。そして、その有効性を数値実験により検討する。

DOI： 10.11509/sci.SCI06.0.234.0

CiNii Article

researchmap

出版者・発行元：システム制御情報学会  

本稿では、生産スケジューリング問題の１つである１機械重み付き納期遅れ和最小化問題に対し、分枝限定法による厳密解法を提案する。分枝限定法における下界値は、仕事の出現回数をラグランジュ緩和した緩和問題を動的計画法により解くことで求める。さらに隣接２仕事間の先行制約を考慮することによって下界値を改善している点が本解法の特徴である。計算機実験により、本下界値計算法の有効性およびそれを用いた分枝限定法の有効性を検討する。

DOI： 10.11509/sci.SCI06.0.129.0

CiNii Article

researchmap

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

The purpose of this two-part study is to investigate the operation problem of single-car elevator systems with destination hall call registration. Destination hall call registration is such a system in which passengers register their destination floors at elevator halls before boarding the car, while in the ordinary systems passengers specify only the directions of their destination floors at elevator halls and register destination floors after boarding the car. In this part of the study, we formulate the operation problem as a dynamic optimization problem and demonstrate by computer simulations that dynamically optimized operation considerably improves the transportation capability compared to conventional selective collective operation. How to solve the dynamic optimization problem is given in the second part of this study. (c) 2004 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ejor.2004.04.038

Web of Science

researchmap

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

In this study we consider the elevator operation problem of single-car elevator systems with destination hall call registration. In this part we construct a branch-and-bound algorithm to solve the dynamic operation optimization problem formulated in the first part. To calculate lower bounds of the subproblems generated in the course of the branch-and-bound algorithm, we first relax some of the constraints of the subproblems and decompose the relaxed subproblems into three parts. Then, we apply the Lagrangian relaxation method to the decomposed subproblems. (c) 2004 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ejor.2004.04.039

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

The purpose of this study is to extend the well-known decomposition theorem for the single-machine total tardiness problem to the case when a precedence constraint between a pair of jobs is set. Since the decomposition theorem forms the basis of strict solution algorithms for the ordinary single-machine total tardiness problem, it is expected that we can construct efficient solution algorithms by the extended decomposition theorem even for the problem with a precedence constraint. We also extend the elimination rules to restrict the possible job positions in an optimal schedule that are also utilized in strict solution algorithms. Then, we construct a simple strict solution algorithm for our problem and show the effectiveness of our results by numerical experiments.

Web of Science

J-GLOBAL

researchmap

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

We construct two types of branch-and-bound algorithms to minimize total tardiness on identical parallel machines. The one is an improvement of the existing algorithm, and the other is based on the dynamic programming model for general parallel-machine scheduling problems. Computational experiments show that our algorithms can handle instances with up to 20 jobs while the existing algorithm can only handle instances with up to 12 jobs.

CiNii Article

CiNii Books

researchmap

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

The purpose of this study is to examine what types of objective functions should be dynamically optimized to improve overall operation efficiency of a single-car elevator system with destination hall call registration. Here, destination hall call registration is such an elevator system that passengers can register their destination floors directly at elevator halls. We propose a method to apply Simulated Annealing to this dynamic operation optimization problem. Then, we show by numerical experiments that the weighted averages of two types of objective functions such as the weighted average service time and the maximum service time are effective, where the service time of a passenger is the time from when he/she pushes a button at an elevator hall till when he/she leaves the car at his/her destination floor.

DOI： 10.1109/ICSMC.2004.1401384

Web of Science

J-GLOBAL

researchmap

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

In this paper we propose a branch-and-bound algorithm for the single-machine earliness-tardiness scheduling problem where weights for earliness and tardiness are independent of jobs. Here, machine idle times are allowed. In our branch-and-bound algorithm, the search tree is generated by fixing the processing order of jobs from the first to the last, or, from the last to the first. To improve the efficiency of the algorithm,. we propose new lower bounds. We also show dominance properties that are utilized both for reducing branches in the search tree and for improving the lower bounds. Then, we show the effectiveness of our algorithm by numerical experiments.

Web of Science

researchmap

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

In this paper, we propose a new method to obtain the optimal cost ( the in mum of the achievable H(infinity) norm of a closed-loop system) for discrete linear periodically time-varying (LPTV) systems. This method reduces via the lifting technique the original problem to the H(infinity) problems of linear time-invariant (LTI) systems without the causality constraint, and therefore the optimal cost can be easily calculated. It is one of the primary advantages over other existing methods. We also show, by applying our method to LTI systems, that the optimal cost for the H(infinity) problem of discrete LTI systems cannot be improved even if we use a class of noncausal controllers. An intriguing implication of this fact is further shown in the context of causal controllers.

DOI： 10.1137/S0363012900376517

Web of Science

researchmap

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

DOI： 10.5687/iscie.12.614

CiNii Article

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

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

The authors study the filtering problem under the assumption that sampling is unreliable; i.e. some of the measurement data are not obtained at some sampling instants. The minimum-variance estimator is derived and its stability is studied in connection with the degree of unreliability of the sampling.

DOI： 10.1049/el:19970651

Web of Science

researchmap

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

In this paper we study the filtering problem under the assumption that the sampling is unreliable; i.e., some of the measurement data are not obtained at some sampling instants. The minimum-variance estimator is derived and its stability is studied in connection with the degree of the unreliability of the sampling.

Web of Science

researchmap

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

DOI： 10.1541/ieejeiss1987.114.3_393

CiNii Article

CiNii Books

researchmap

記述言語：日本語  

researchmap

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

本研究では,マルチカーエレベータシステムにおいて,衝突や逆走が発生しないようかごの運行を決定する問題を対象とする.本研究では,乗客のかごへの割り当ては与えられているものとして1本のシャフトに注目し,乗客が次々に割り当てられるという状況下でかごの運行を決定するオンライン運行決定問題を,混合整数線形計画問題として定式化する.そして,汎用ソルバを用いた計算機シミュレーションを行って,本研究におけるシステムモデルの有効性や,マルチカーエレベータシステムの特性を検討する.

CiNii Article

CiNii Books

researchmap

記述言語：日本語   出版者・発行元：システム制御情報学会  

CiNii Article

researchmap

記述言語：日本語  

CiNii Article

CiNii Books

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（学術雑誌）   出版者・発行元：システム制御情報学会  

DOI： 10.11509/isciesci.54.10_385

CiNii Article

CiNii Books

J-GLOBAL

researchmap

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

記述言語：日本語   出版者・発行元：システム制御情報学会  

CiNii Article

CiNii Books

researchmap

記述言語：日本語  

CiNii Article

CiNii Books

researchmap

researchmap

researchmap

researchmap

researchmap

受賞国：日本国

researchmap

受賞国：日本国

researchmap