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.