Minimizing makespan on a single machine subject to random breakdowns

We investigate optimal sequencing policies for the expected makespan problem with an unreliable machine, where jobs have to be reprocessed in their entirety if preemptions occur because of breakdowns. We identify a class of uptime distributions under which LPT minimizes expected makespan.     

Redefining Event Variables for Efficient Modeling of Continuous-Time Batch Processing

We define events so as to reduce the number of events and decision variables needed for modeling batch-scheduling problems such as described in [15]. We propose a new MILP formulation based on this concept, defining non-uniform time periods as needed and decision variables that are not time-indexed. It can handle complicated multi-product/multi-stage machine processes, with production lines merging and diverging, and with minimum and maximum batch sizes. We compare it with earlier models and show that it can solve problems with small to medium demands relative to batch sizes in reasonable computer times.     

带到达时间的单机排序中的资源分配问题

讨论两个单机排序的资源分配问题1｜rj,pj=bj-ajuj,Cmax≤｜∑uj和1｜rj,prec,pj=bj-ajuj C max≤｜∑uj并给出求其最优资源分配的多项式算法.     

机器具有准备时间的双目标平行机排序问题

本文讨论机器具有准备时间的双目标平行机排序问题，目标函数为完工时间和最优条件下极小化最大完工时间．通过对SPT排序的性质的分析，给出了最优排序的下界．在此基础上证明了SPT排序的误差界为3／2，并且是紧界．     

单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$（t,t+\Delta（t）]$内到达工件的信息,这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长,其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in（0,1）$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。     

成组加工中的加工全程和延误工件数问题

本文在同组工件连续加工的条件下考虑了单机加工中的二个排序问题,其目标函数分别为极小加工全程和延误工件数。文中在不同的条件下对它们给出了多项式时间算法。     

Optimal makespan schedule for three jobs on two machines

This paper deals with the problem of scheduling three jobs on two machines in order to minimize the makespan, when operation preemptions are forbidden and routes are fixed and may vary per job. It is shown that this problem can be solved by anO(r ⁴) algorithm, wherer is the maximal number of operations per job. Supported by Belarussian Fundamental Research Found, Project Φ60–242, and Deutsche Forschungsgemeinschaft, Project ScheMA     

A Flexible On-line Scheduling Algorithm for Batch Machine with Infinite Capacity

We study on-line scheduling on a batch machine with infinite capacity. We present a flexible on-line scheduling algorithm that aims at minimizing the makespan and achieves the optimal competitive ratio of . This research is substantially supported by a grant from City University of Hong Kong (Grant No. 7001119). The second author is supported by this grant and by the Natural Science Foundation of China.     

A Branch-and-Bound Algorithm to Minimize the Makespan in a Flowshop with Blocking

This work addresses the minimization of the makespan criterion for the flowshop problem with blocking. In this environment there are no buffers between successive machines, and therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. We propose a lower bound which exploits the occurrence of blocking. A branch-and-bound algorithm that uses this lower bound is described and its efficiency is evaluated on several problems. Results of computational experiments are reported.     

Local search procedures for improving feasible solutions to the sequential ordering problem

Given a digraphG=(V, A), a weight for each node inV and a weight for each arc inA, the Sequential Ordering Problem (SOP) consists of finding a Hamiltonian path, such that a release date and a deadline for each node and precedence relationships among nodes are satisfied and a linear function is minimized. In our case, the objective function is the maximum cumulated potential of the nodes (also, the so-called makespan). The SOP has a broad range of applications, mainly in production planning and manufacturing systems. Nodes represent jobs (to be processed on a single machine), arcs represent sequencing of the jobs, the nodes' weights are the processing time for the jobs, the arcs' weights are the setup times for two consecutive jobs, and the cumulated potential of a node is the completion time of a job. The goal is to produce a feasible scheduling of the jobs so that the makespan is minimized. We present an approximate algorithm for improving feasible solutions to the SOP. The algorithm is based on two local search-opt procedures to reduce the makespan while satisfying the time window (i.e. release date and deadline) and precedence constraints, for=3 and 4. The complexity of the algorithm isO(bn ⁴), wheren denotes the number of nodes andb is the average number of precedences per node. Extensive computational experience and implementation aspects are reported for very large-scale instances up to 3000 nodes and 9000 precedences. Experience with real-life cases is also reported.