Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for ‘on-line’ production scheduling and ‘last-minute’ changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems.     

作业时间依赖顺序的拆卸线平衡多目标优化

在废旧产品拆卸时无先后关系约束的任务之间可能存在拆卸干扰，使任务作业时间依赖于拆卸顺序，导致产品总作业时间不确定，从而影响拆卸线的平衡。为此，考虑拆卸过程中任务间的相互干扰，以最小化拆卸成本和环境危害为目标，构建作业时间依赖顺序的拆卸线平衡多目标优化模型，并提出一种Pareto人工蜂群算法进行求解，采用混合生成法保证种群质量与多样性，设计变邻域深度搜索策略以提高雇佣蜂局部开采效率，为降低侦察蜂探测的盲目性采用基于外部存档的单点变异算子进行搜索。最后通过算例与实例验证算法的有效性以及平衡任务在拆卸线上分配的重要性。     

Sequencing heuristics for dependent setups in a continuous process industry

In this paper we address the scheduling of Biaxially Oriented Polypropylene (BOPP) film production, which belongs to the plastics industry and is a continuous process. Scheduling problems in BOPP film production involve processing different thickness settings of films on a common facility. Customer orders of the same thickness setting are usually grouped together as a production batch and a setup time is incurred whenever the batch is switched. However, there is usually more than one batch for the same thickness setting because of the due date constraints of the orders. Therefore, there is a need to develop a batching and sequencing scheme that minimizes the total setup time, or equivalently the makespan, under the due date constraint. In this paper heuristics are developed to generate a near-optimal solution for the problem. The heuristics are evaluated by an optimal solution procedure and are tested by using the actual data from a plant making the BOPP film. Comparison of the heuristics with the results of the current system has demonstrated a significant reduction in total setup time.     

序列相关的流水车间成组调度仿真

针对经典调度中未考虑生产准备时间或将准备时间放入加工时间考虑的问题,结合生产实际,将生产准备时间 独立出来,关注准备时间与加工顺序相关的情况;考虑到工件加工过程的不确定性,以三角函数表示工件的加工时间。 在建立了序列相关的流水车间成组调度的模型的基础上,在Simio仿真环境中建立具体模型,按工件组加工时间的不同 设定6种调度方案,运行100次。实验结果表明Simio仿真软件可以很好的模拟序列相关的流水车间成组调度情况,并 发现生产准备时间总和越小则工件的完工时间越小,此结论推广至大规模调度问题时可在短时间内获得调度的最优解。