アカウント名:
パスワード:
巡回セールスマン問題は、配達員では重要そうですが私の場合、巡回セールスマン問題は仕事であまり使うことはないのですがジョブショップスケジュール問題はよく必要に迫られます。
ジョブショップスケジューリング問題を古典コンピュータで解かせるアルゴリズムについて知っている方がいらしたら教えて下さい。
巡回セールスマン問題もジョブショップスケジューリング問題も NP 完全なので、評価関数を用意して総当たりor焼き鈍しor遺伝的アルゴリズムしかないんじゃないかな評価関数を組めれば、実現自体は出来ると思いますなお「特定の問題に関して量子コンピュータが圧倒的に高速」なだけで、古典コンピュータで解けない問題を量子コンピュータが解けるようになるわけではないです
巡回セールスマン問題はNP困難だけどNP完全ではない(NP完全問題より難しいかもしれない)のでは? (そもそも「はい」「いいえ」で答えられる問題でなければNP問題という概念が適用できないが巡回セールスマン問題は「最短経路を求めよ」という問題)
日々、「効率化」と「生産性」で検証がなされている分野ですのでそれに特化したアルゴリズムはありません。
今ホットなのは、量子計算の様に ばばっと定量計算をおこなって統計的にこっちの解の方がいいね?っていう従来の古典的なやり方からくる結果を利用した、未来判断を組み合わせたものが流行ってます
何が問題なのかを自分で良く考えれば対処法は見つかるのでは?
どうしても最適解が必要だから決定論的なアルゴリズムを求めているのか?今よりも良い解が得られるアルゴリズムを業務上必要としているのか?競合しているライバルよりも良い解を得て競争に勝とうとしているのか?ほんのちょっとだけ良い解が得られるアルゴリズムを自社で開発して商品の宣伝文句にしたいのか?最適解を必要としているわけではないが現実的な解を今よりも短時間で求めたいのか?
質問としては、どれが一番近いかと言うと最適解を求めるアルゴリズムです。(もし存在しているのであればお知恵を借りたくて書き込みました)
私は賢くないのでこういったアルゴリズムを自分で考えて対処できません。以前、ソートアルゴリズムの存在を知らず自分で考えましたが(後にバブルソートだとわかる)、後で知ったクイックソートには性能も悪いですし、アルゴリズムを知ったときは自分で考案できないなと思いました。
ジョブショップスケジュール問題の研究者でも無い私はアルゴリズム考案するほど余裕はありません。ただ生産管理において大きな壁であります。そういうものは先人の知恵を借りたほうが良いと思ったのです。
#4067055さんのように
特化したアルゴリズムはありません。
でもありがたい情報でした。#4067055さんありがとうございます。
> 質問としては、どれが一番近いかと言うと最適解を求めるアルゴリズムです。この問題での最適解を求めるのは(規模によるけど)現実的な時間では難しいですただ「それなりに最適だろう」という近似解であれば、既にある手法で可能です(最適解出すのに1ヶ月、近似解出すのに1時間とかそのぐらいの差がある)
必要なのは評価関数(スケジューリング A とスケジューリング B のどちらが優れているかの評価)なので、これさえあれば自分で頑張るでも他者/他社にお任せするも可能ですただどれにしても片手間でできることではないので、改善活動として社内で提言し予算や人を割いてもらうのがいいかと
組み合わせ最適化問題は、深く研究するつもりがないのなら、適当なソルバーに投げ渡してしまうのが手っ取り早い。
ソルバーには、有料/無料、最適解を求める(むっちゃ時間がかかる)/そこそこ良い解を求める(速い)、など色々あるけど、いずれにせよ、解きたい問題をソルバーが対応してる形の数式(大体は、多数の条件式と、最適化したい目的関数1つ)に落とし込んだら、後はよしなにやってくれる。
検索してとりあえず出てきた解説例だと組合せ最適化を使おう [qiita.com]とか。リンク先に組合せ最適化 - 典型問題 - ジョブショップ問題 [qiita.com]もあるね。
具体例も含めてご案内ありがとうございます。
参考になります。
今回いろいろな方から参考意見を聞くことが出来てよかったと思います。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
あつくて寝られない時はhackしろ! 386BSD(98)はそうやってつくられましたよ? -- あるハッカー
ジョブショップスケジューリング問題 (スコア:1)
巡回セールスマン問題は、配達員では重要そうですが
私の場合、巡回セールスマン問題は仕事であまり使うことはないのですが
ジョブショップスケジュール問題はよく必要に迫られます。
ジョブショップスケジューリング問題を古典コンピュータで解かせるアルゴリズムについて
知っている方がいらしたら教えて下さい。
Re:ジョブショップスケジューリング問題 (スコア:1)
巡回セールスマン問題もジョブショップスケジューリング問題も NP 完全なので、評価関数を用意して総当たりor焼き鈍しor遺伝的アルゴリズムしかないんじゃないかな
評価関数を組めれば、実現自体は出来ると思います
なお「特定の問題に関して量子コンピュータが圧倒的に高速」なだけで、古典コンピュータで解けない問題を量子コンピュータが解けるようになるわけではないです
Re: (スコア:0)
巡回セールスマン問題はNP困難だけどNP完全ではない(NP完全問題より難しいかもしれない)のでは? (そもそも「はい」「いいえ」で答えられる問題でなければNP問題という概念が適用できないが巡回セールスマン問題は「最短経路を求めよ」という問題)
Re:このあとむちゃくちゃラクロスした (スコア:0)
日々、「効率化」と「生産性」で検証がなされている分野ですので
それに特化したアルゴリズムはありません。
今ホットなのは、量子計算の様に ばばっと定量計算をおこなって
統計的にこっちの解の方がいいね?っていう従来の古典的なやり方
からくる結果を利用した、未来判断を組み合わせたものが流行ってます
Re: (スコア:0)
何が問題なのかを自分で良く考えれば対処法は見つかるのでは?
どうしても最適解が必要だから決定論的なアルゴリズムを求めているのか?
今よりも良い解が得られるアルゴリズムを業務上必要としているのか?
競合しているライバルよりも良い解を得て競争に勝とうとしているのか?
ほんのちょっとだけ良い解が得られるアルゴリズムを自社で開発して商品の宣伝文句にしたいのか?
最適解を必要としているわけではないが現実的な解を今よりも短時間で求めたいのか?
Re:ジョブショップスケジューリング問題 (スコア:1)
質問としては、どれが一番近いかと言うと最適解を求めるアルゴリズムです。
(もし存在しているのであればお知恵を借りたくて書き込みました)
私は賢くないのでこういったアルゴリズムを自分で考えて対処できません。
以前、ソートアルゴリズムの存在を知らず自分で考えましたが(後にバブルソートだとわかる)、
後で知ったクイックソートには性能も悪いですし、アルゴリズムを知ったときは自分で考案できないなと思いました。
ジョブショップスケジュール問題の研究者でも無い私はアルゴリズム考案するほど余裕はありません。
ただ生産管理において大きな壁であります。
そういうものは先人の知恵を借りたほうが良いと思ったのです。
#4067055さんのように
特化したアルゴリズムはありません。
でもありがたい情報でした。
#4067055さんありがとうございます。
Re: (スコア:0)
> 質問としては、どれが一番近いかと言うと最適解を求めるアルゴリズムです。
この問題での最適解を求めるのは(規模によるけど)現実的な時間では難しいです
ただ「それなりに最適だろう」という近似解であれば、既にある手法で可能です
(最適解出すのに1ヶ月、近似解出すのに1時間とかそのぐらいの差がある)
必要なのは評価関数(スケジューリング A とスケジューリング B のどちらが優れているかの評価)なので、これさえあれば自分で頑張るでも他者/他社にお任せするも可能です
ただどれにしても片手間でできることではないので、改善活動として社内で提言し予算や人を割いてもらうのがいいかと
Re: (スコア:0)
組み合わせ最適化問題は、深く研究するつもりがないのなら、適当なソルバーに投げ渡してしまうのが手っ取り早い。
ソルバーには、有料/無料、最適解を求める(むっちゃ時間がかかる)/そこそこ良い解を求める(速い)、など色々あるけど、
いずれにせよ、解きたい問題をソルバーが対応してる形の数式(大体は、多数の条件式と、最適化したい目的関数1つ)に落とし込んだら、後はよしなにやってくれる。
検索してとりあえず出てきた解説例だと組合せ最適化を使おう [qiita.com]とか。リンク先に組合せ最適化 - 典型問題 - ジョブショップ問題 [qiita.com]もあるね。
Re: (スコア:0)
具体例も含めてご案内ありがとうございます。
参考になります。
今回いろいろな方から参考意見を聞くことが出来てよかったと思います。