Lagrangian bounds for just-in-time job-shop scheduling

We study the job-shop scheduling problem with earliness and tardiness penalties. We describe two Lagrangian relaxations of the problem. The first one is based on the relaxation of precedence constraints while the second one is based on the relaxation of machine constraints. We introduce dedicated algorithms to solve the corresponding dual problems. The second one is solved by a simple dynamic programming algorithm while the first one requires the resolution of an NP-hard problem by branch and bound. In both cases, the relaxations allow us to derive lower bounds as well as heuristic solutions. We finally introduce a simple local search algorithm to improve the best solution found. Computational results are reported.     

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem

This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules.     

A Lagrangian approach to single-machine scheduling problems with two competing agents

In this paper, we develop branch-and-bound algorithms for several hard, two-agent scheduling problems, i.e., problems in which each agent has an objective function which depends on the completion times of its jobs only. Our bounding approach is based on the fact that, for all problems considered, the Lagrangian dual gives a good bound and can be solved exactly in strongly polynomial time. The problems addressed here consist in minimizing the total weighted completion time of the jobs of agent A, subject to a bound on the cost function of agent B, which may be: (i) total weighted completion time, (ii) maximum lateness, (iii) maximum completion time. An extensive computational experience shows the effectiveness of the approach.     

Two-stage hybrid flow shop scheduling with dynamic job arrivals

Motivated by applications in semiconductor manufacturing industry, we consider a two-stage hybrid flow shop where a discrete machine is followed by a batching machine. In this paper, we analyze the computational complexity of a class of two-machine problems with dynamic job arrivals. For the problems belonging to P we present polynomial algorithms. For the NP-complete problems we propose the heuristics, and then establish the upper bounds on the worst case performance ratios of the heuristics. In addition, we give the improved heuristics that can achieve better performances.     

Meta-heuristics for stable scheduling on a single machine

This paper presents a model for single-machine scheduling with stability objective and a common deadline. Job durations are uncertain, and our goal is to ensure that there is little deviation between planned and actual job starting times. We propose two meta-heuristics for solving an approximate formulation of the model that assumes that exactly one job is disrupted during schedule execution, and we also present a meta-heuristic for the global problem with independent job durations.     

Scheduling for stability in single-machine production systems

Robust scheduling aims at the construction of a schedule that is protected against uncertain events. A stable schedule is a robust schedule that changes only little when variations in the input parameters arise. This paper presents a model for single-machine scheduling with stability objective and a common deadline. We propose a branch-and-bound algorithm for solving an approximate formulation of the model. The algorithm is exact when exactly one job is disrupted during schedule execution.     

Scheduling with a common due-window: Polynomially solvable cases

The single machine scheduling problem to minimize maximum weighted absolute deviations of job completion times from a common due-date, is known to be NP-hard. However, two special cases have been shown to have polynomial time solutions: the case of unit processing time jobs, and the case of due-date assignment for a given job sequence. We extend both cases to a setting of a common due-window. We show that the unit-job problem includes 12 different sub-cases, depending on the size and location of the (given) due-window. Scheduling and due-window assignment for a given job sequence is solved for a single machine, for parallel identical machines and for flow-shops. For each of the above cases, an appropriate special-structured linear program is presented.     

An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved.     

A dynamic programming algorithm for days-off scheduling with sequence dependent labor costs

This paper presents a dynamic programming (DP) algorithm for solving a labor scheduling problem with several realistic days-off scheduling constraints and a cost structure that depends on the work sequence for each employee. The days-off scheduling constraints include the following: (1) each employee is assigned no more than three workdays per week, (2) each employee is assigned at least two consecutive off days per week, and (3) any work stretch cannot exceed four consecutive workdays. The sequence-dependent cost structure assumes that the daily wage of each employee depends on two factors: (1) whether the given workday is weekend or a regular workday, and (2) the sequence of work patterns assigned in previous days. A DP algorithm suited to instances of moderate size is used to determine the optimum work assignments that minimize the total labor cost, while satisfying the work demand under the stated constraints.     

具有恶化效应和学习效应的单机成组调度问题

讨论了一类具有恶化效应和学习效应的单机成组调度问题, 其中工件的加工时间为开工时间和组内工序的函数. 通过对问题性质的分析以及多项式时间算法的描述, 得出如下结论: 在单机成组调度问题中, 即便工件的加工时间同时受恶化效应和学习效应的制约, 极小化完工时间问题以及极小化总资源消耗的问题仍是多项式时间可解的.     

A new heuristic algorithm for the operating room scheduling problem

Due to the great importance of operating rooms in hospitals, this paper studies an operating room scheduling problem with open scheduling strategy. According to this strategy, no time slot is reserved for a particular surgeon. The surgeons can use all available time slots. Based on Fei et al.’s model which is considered to be close to reality, we develop a heuristic algorithm to solve it. The idea of this heuristic algorithm is from dynamic programming by aggregating states to avoid the explosion of the number of states. The objective of this paper is to design an operating program to maximize the operating rooms’ use efficiency and minimize the overtime cost. Computational results show that our algorithm is efficient, especially for large size instances where our algorithm always finds feasible solutions while the algorithm of Fei et al. does not.     

Preemption in single machine earliness/tardiness scheduling

We consider a single machine earliness/tardiness scheduling problem with general weights, ready times and due dates. Our solution approach is based on a time-indexed preemptive relaxation of the problem. For the objective function of this relaxation, we characterize cost coefficients that are the best among those with a piecewise linear structure with two segments. From the solution to the relaxation with these best objective function coefficients, we generate feasible solutions for the original non-preemptive problem. We report extensive computational results demonstrating the speed and effectiveness of this approach.     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

Scheduling with compressible and stochastic release dates

In this work we study a one-machine scheduling problem which is featured by: (a) the release date of each job is compressible and stochastic, (b) each job has to be delivered before its due date (deadline) and (c) the manufacturer can expedite the production through overtime at an extra cost. The objective function of the scheduling problem is to minimize the total cost which includes the compressing cost and the overtime production cost. We propose a heuristic algorithm in which the stochastic problem is converted to the deterministic problem by a release-time “converting policy”. We coin a concept of a job's late-release-impact factor (LRIF) and we propose a LRIF based converting policy. We compare the LRIF based converting policy with the ones used in practice, and the numerical test shows that the LRIF based converting policy can obtain the schedule with the lowest actual total cost.     

Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness

In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time.     

考虑时间因素的0-1背包调度问题

文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为w_i,连续加工时间为t_i),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长t_i后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500s内得到比动态规划算法更好的结果。