摘要:单机调度问题（Single machine scheduling problem，SMSP）是在生产调度领域的一种非常重要的问题，作为一个基础的调度问题，常常为更复杂的调度问题的研究奠定了基础，在制造业中的起着重要作用。基本问题可以描述为多个独立的任务的需要在一台机器上顺序加工的，各任务都有处理时间，交货时间和其他参数，调度目标是在满足一些约束条件的要求下找到一个最优的任务序列使得设定的某些指标最小。单机调度问题具有广泛的实际应用背景，深入单机调度问题的研究，解决积累的经验和知识的问题可以为生产经营提供了宝贵的指导意见，研究调度也具有一定的现实意义。

考虑提前、拖期费用的生产排序与调度问题是当今调度领域的一个热点话题, 这种思想与日本的 JIT(Just-In-Time)准时生产制的逐渐兴起密切相关。在市场经济的今天,厂家无论是提前完工或者拖期完工，只要不在顾客所定的交货期内完工，厂家就要接受违约的惩罚。因此，生产厂家能否在顾客所提出的交货期完工具有意义非常重大。

本文首先对JIT的形成发展，车间调度，单机调度问题进行概述。然后对基于JIT的单机提前_拖期调度问题进行问题描述及数学建模，根据相关的参数，决策变量及约束条件确定目标函数，最终目标是总惩罚量值最小。最后算法研究了比较一般的情况, 即顾客所设置的交货期为一个时间窗口, 也给出了交货期窗口下的多项式时间算法, 确定了加工任务的最优调度, 计算实例说明了本文提出的算法的有效性。

关键词：准时生产；最优调度；单机；交货期

目录

摘要

Abstract

1 绪论1

1.1 研究背景及意义1

1.2 国内外研究现状1

1.3 本文的主要研究内容1

2 准时制单机生产车间调度问题综述3

2.1 JIT的形成及发展回顾3

2.2 JIT生产管理方式及主要研究内容3

2.3 车间调度问题的概述3

2.4 单机调度问题概述4

3 问题描述和数学建模6

3.1 问题描述6

3.2 数学建模6

4 Due-Date下的最优调度算法8

4.1 算法原理及步骤8

4.2 计算实例9

结    论11

参 考 文 献12

致    谢13