Practicable Scheduling Algorithm to Meet Due Times

本研究发展出实用的排程演算法，以满足交货期的需求。调度的基本假设是，每一个工件都应该在顾客要求的预定时间之前或刚好在预定时间完成，并且在预定时间同时离开车间。任何工作都不允许迟到，如果一项工作提前完成，那么车间将保留该工作，并产生提前保留成本。本研究取得的主要成果如下：1.研究了零时间可行的无拖期工件单机排序问题。提出了一种以减少加工时间为目标的启发式算法，以最小化紧急生产的库存费用和减少费用之和为目标，近似地确定一个可行的生产计划.工件有准备时间和交货期约束，机器有停机约束，工件之间的准备时间与顺序相关的单机排序问题。停机是一种破坏性事件，如假期、休息或机器维护，并具有预先指定的机器中断时间。提出了一种基于分枝定界法的最小化最大拖期的优化算法。此外，还提出了以最大拖期为目标的后处理算法，该算法控制停机期的开始时间.研究了具有交货期约束、零时间可行性和停机约束的单机排序问题。提出了一种减少停机次数的启发式算法，近似地使停机次数下的持有成本和减少成本之和最小.研究了加工时间可变、准备时间和交货期受限的单机排序问题。提出了一种启发式算法，以使每个工件的库存费用和生产费用之和近似最小为目标，得到一个包含加工时间确定的满足交货期的调度方案。

This research developed the practicable scheduling algorithms to meet due times. The basic assumption in the scheduling is that every job should be completed before or just on the due time when the customer requires it and leave the shop simultaneously on the due time. No jobs are permitted to be tardy, and if a job is completed earlier than its due time, then the shop holds the job and incurs the holding cost for earliness. The results obtained in this research are summarized as follows :1. The single machine scheduling subject to no tardy jobs and time zero feasibility was considered. A heuristic algorithm with reduction in processing time was developed to determine a feasible schedule approximately to minimize the sum of the holding cost and the reduction cost for crash production.2. The single machine scheduling with ready and due times constraints on jobs, shutdown constraints on the machine and sequence dependent setup times among jobs. The shutdown is a disruptive event such as holiday, breaks or machine maintenance, and has a prespecified period when the machine will be interrupted. An optimization algorithm based on the branch-and-bound method was developed to minimize the maximum tardiness. Furthermore, the post-processing algorithm was developed so as to ****ce the maximum tardiness, which manipulates the starting time of the shutdown period.3. The single machine scheduling with due times constrains, time zero feasibility and shutdown constraints was considered. A heuristic algorithm with reduction in shutdown times was developed approximately to minimize the sum of the holding cost and the reduction cost in shutdown times.4. The single machine scheduling with variable processing times and with ready and due times constraints was considered. A heuristic algorithm was developed to obtain a schedule to meet due times involving the processing time determination so as to minimize approximately the sum of the holding cost and the production cost for every job.