装箱问题的理论与算法

结题报告
项目介绍
AI项目解读

基本信息

  • 批准号：
    10971192
  • 项目类别：
    面上项目
  • 资助金额：
    23.0万
  • 负责人：
    张国川
  • 依托单位：
    浙江大学
  • 学科分类：
    A0406.离散优化
  • 结题年份：
    2012
  • 批准年份：
    2009
  • 项目状态：
    已结题
  • 起止时间：
    2010-01-01 至2012-12-31

项目摘要

装箱（Bin Packing）是组合优化的一个经典问题。以其为基本模型构成的装箱问题类有强烈的实际背景和深刻的算法理论意义。本项目研究若干具体装箱问题的算法结构和性质，通过对带个数限制的在线装箱、元素有区间约束的装箱、二维带状装箱、一般费用下的装箱以及传感器安置等问题的深入探讨，刻画相应问题的内在特性以及可行装箱的充分条件和必要条件。利用这些条件分析和估计算法的上下界，试图在算法设计与分析的思想上有所突破。在此基础上取得重要算法结果。

结项摘要

装箱问题一直是组合优化领域的热点研究问题。经典的遗留问题不断需要我们在算法设计与分析上创新，而各种组合优化模型大多与装箱问题相关，如平行机调度、背包以及树覆盖等问题。本项目的研究内容可以分成三个层面，一是装箱问题的各种变形，包括带容量限制的平行机调度、多带状装箱、在线背包、双层背包优化等；二是调度算法的研究，如多核处理器的调度问题、带加速资源的调度问题以及两个代理的流水作业问题；三是由算法设计过渡到机制设计，首次研究了厌恶性选址问题的算法机制。.在模型方面提出了双层背包优化和带加速资源的调度，前者刻画了博弈环境下的两阶段背包问题，后者描述了计算机信息处理环境下的资源分配模型，得到了相应的深刻算法结果。在算法理论和方法方面准确分析了带容量限制平行机调度和带资源扩展的在线背包问题的最优解结构，分别设计了EPTAS（有效的多项式时间近似方案）和最优的在线算法，丰富了近似方案的设计思想和在线算法的分析手段。在算法机制设计方面我们抓住了厌恶性选址问题诚实机制的核心，利用直径定位、就近分类的思想，从特殊到一般网络分别给出了相应的有效机制。项目所得到的所有算法成果是相应问题的最好结果。.依托本项目，我们培养了优秀的博士研究生和博士后研究人员，加强和拓展了广泛的国际学术交流，项目负责人近两年也先后受邀担任重要国际学术期刊《Omega-The International Journal of Management Science》和《Journal of Scheduling》的编委。

项目成果

期刊论文数量（8）
专著数量（0）
科研奖励数量（0）
会议论文数量（0）
专利数量（0）
Approximation algorithms for a bi-level knapsack problem
双层背包问题的近似算法
  • DOI：
    10.1016/j.tcs.2012.08.008
  • 发表时间：
    2013-07-29
  • 期刊：
    THEORETICAL COMPUTER SCIENCE
  • 影响因子：
    1.1
  • 作者：
    Chen, Lin;Zhang, Guochuan
  • 通讯作者：
    Zhang, Guochuan
Strategy-proof approximation mechanisms for an obnoxious facility game on networks
网络上令人讨厌的设施博弈的策略证明近似机制
  • DOI：
    10.1016/j.tcs.2011.11.041
  • 发表时间：
    2013-07
  • 期刊：
    Theoretical Computer Science
  • 影响因子：
    1.1
  • 作者：
    Cheng, Yukun;Yu, Wei;Zhang, Guochuan
  • 通讯作者：
    Zhang, Guochuan
On-line scheduling of multi-core processor tasks with virtualization
基于虚拟化的多核处理器任务在线调度
  • DOI：
    10.1016/j.orl.2010.04.002
  • 发表时间：
    2010-07
  • 期刊：
    OPERATIONS RESEARCH LETTERS
  • 影响因子：
    1.1
  • 作者：
    Ye, Deshi;Zhang, Guochuan
  • 通讯作者：
    Zhang, Guochuan
Online knapsack with resource augmentation
资源增强的在线背包
  • DOI：
    10.1016/j.ipl.2010.08.013
  • 发表时间：
    2010-10
  • 期刊：
    INFORMATION PROCESSING LETTERS
  • 影响因子：
    0.5
  • 作者：
    Iwama, Kazuo;Zhang, Guochuan
  • 通讯作者：
    Zhang, Guochuan
Approximation schemes for two-machine flow shop scheduling with two agents
两个智能体的两机流水车间调度近似方案
  • DOI：
    10.1007/s10878-011-9378-2
  • 发表时间：
    2011-01
  • 期刊：
    Journal of Combinatorial Optimization
  • 影响因子：
    1
  • 作者：
    Luo, Wenchang;Chen, Lin;Zhang, Guochuan
  • 通讯作者：
    Zhang, Guochuan

数据更新时间：{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI：
    {{ item.doi || "--"}}
  • 发表时间：
    {{ item.publish_year || "--" }}
  • 期刊：
    {{ item.journal_name }}
  • 影响因子：
    {{ item.factor || "--"}}
  • 作者：
    {{ item.authors }}
  • 通讯作者：
    {{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ monograph.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ patent.updateTime }}

其他文献

基于受灾人员损失的多受灾点、多商品应急物资分配模型
  • DOI：
    --
  • 发表时间：
    --
  • 期刊：
    系统管理学报
  • 影响因子：
    --
  • 作者：
    葛洪磊;刘南;张国川;俞海宏
  • 通讯作者：
    俞海宏
负载均衡问题
  • DOI：
    10.15960/j.cnki.issn.1007-6093.2019.03.001
  • 发表时间：
    2019
  • 期刊：
    运筹学学报
  • 影响因子：
    --
  • 作者：
    张国川;陈林
  • 通讯作者：
    陈林

其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI：
    {{ item.doi || "--" }}
  • 发表时间：
    {{ item.publish_year || "--"}}
  • 期刊：
    {{ item.journal_name }}
  • 影响因子：
    {{ item.factor || "--" }}
  • 作者：
    {{ item.authors }}
  • 通讯作者：
    {{ item.author }}
empty
内容获取失败，请点击重试
重试联系客服
title开始分析
查看分析示例
此项目为已结题，我已根据课题信息分析并撰写以下内容，帮您拓宽课题思路：

AI项目思路

AI技术路线图

张国川的其他基金

疾病治疗方案的优化及博弈机制
  • 批准号：
    12271477
  • 批准年份：
    2022
  • 资助金额：
    46 万元
  • 项目类别：
    面上项目
新型计算环境下的排序问题
  • 批准号：
    11271325
  • 批准年份：
    2012
  • 资助金额：
    50.0 万元
  • 项目类别：
    面上项目
在线问题的新模型与新方法
  • 批准号：
    60573020
  • 批准年份：
    2005
  • 资助金额：
    21.0 万元
  • 项目类别：
    面上项目
组合优化中困难问题的有效算法
  • 批准号：
    19801032
  • 批准年份：
    1998
  • 资助金额：
    5.0 万元
  • 项目类别：
    青年科学基金项目

相似国自然基金

{{ item.name }}
  • 批准号：
    {{ item.ratify_no }}
  • 批准年份：
    {{ item.approval_year }}
  • 资助金额：
    {{ item.support_num }}
  • 项目类别：
    {{ item.project_type }}

相似海外基金

{{ item.name }}
{{ item.translate_name }}
  • 批准号：
    {{ item.ratify_no }}
  • 财政年份：
    {{ item.approval_year }}
  • 资助金额：
    {{ item.support_num }}
  • 项目类别：
    {{ item.project_type }}
{{ showInfoDetail.title }}

作者：{{ showInfoDetail.author }}

知道了

AI项目解读示例

课题项目：调控A型流感病毒诱导IFN-β表达的机制研究

AI项目摘要：

本研究聚焦于TRIM2蛋白在A型流感病毒诱导的IFN-β表达中的调控机制。A型流感病毒是全球性健康问题，其感染可导致严重的呼吸道疾病。IFN-β作为关键的抗病毒因子，其表达水平对抗病毒防御至关重要。然而，TRIM2如何调控IFN-β的表达尚未明确。本研究假设TRIM2通过与病毒RNA或宿主因子相互作用，影响IFN-β的产生。我们将采用分子生物学、细胞生物学和免疫学方法，探索TRIM2与A型流感病毒诱导IFN-β表达的关系。预期结果将揭示TRIM2在抗病毒免疫反应中的作用，为开发新的抗病毒策略提供理论基础。该研究对理解宿主抗病毒机制具有重要科学意义，并可能对临床治疗流感病毒感染提供新的视角。

AI项目思路：

科学问题：TRIM2如何调控A型流感病毒诱导的IFN-β表达？
前期研究：已有研究表明TRIM2参与抗病毒反应，但其具体机制尚不明确。
研究创新点：本研究将深入探讨TRIM2在IFN-β表达中的直接作用机制。
技术路线：包括病毒学、分子生物学、细胞培养和免疫检测技术。
关键技术：TRIM2与病毒RNA的相互作用分析，IFN-β启动子活性检测。
实验模型：使用A型流感病毒感染的细胞模型进行研究。

AI技术路线图

        graph TD
          A[研究起始] --> B[文献回顾与假设提出]
          B --> C[实验设计与方法学准备]
          C --> D[A型流感病毒感染模型建立]
          D --> E[TRIM2与病毒RNA相互作用分析]
          E --> F[TRIM2对IFN-β启动子活性的影响]
          F --> G[IFN-β表达水平测定]
          G --> H[TRIM2功能丧失与获得研究]
          H --> I[数据收集与分析]
          I --> J[结果解释与科学验证]
          J --> K[研究结论与未来方向]
          K --> L[研究结束]
关闭
close
客服二维码