Optimized appointment scheduling

In service systems, in order to balance the server’s idle times and the customers’ waiting times, one may fix the arrival times of the customers beforehand in an appointment schedule. We propose a procedure for determining appointment schedules in such a D/G/1-type of system by sequentially minimizing the per-customer expected loss. Our approach provides schedules for any convex loss function; for the practically relevant cases of the quadratic and absolute value loss functions appealing closed-form results are derived. Importantly, our approach does not impose any conditions on the service time distribution; it is even allowed that the customers’ service times have different distributions.     

大规模伤亡事件应对流程的前摄性调度优化

以死亡人数最少化为目标,研究大规模伤亡事件应对流程的前摄性调度优化问题。首先,使用伤情等级和伤情随机转化的马尔可夫链,建立伤员死亡概率与伤员处置时间的函数关系。随后,将研究问题转化为柔性作业车间静态调度问题,并设计遗传算法求解。最后用一个随机算例对算法进行仿真,结果表明：该算法可行有效;与现有研究中救援时间最短化的调度方法相比,伴随着可接受的救援时间跨度增加,该方法可大幅降低救援过程中的死亡人数。本文研究有助于决策者优化应急救援过程,有效减少死亡人员数量。     

转包且具有不同费用时间段的排序问题

本文研究制造商可以将工件转包给承包商加工的排序模型,承包商仅有一台机器,转包费用由分配给转包工件的不同时间段费用确定.本文分别研究制造商有一台单机及两台自由作业机器环境情形,需要确定被转包工件集及全部工件的加工顺序,使得工件最大完工时间与转包费用和最小.本文利用归约方法对制造商每个机器环境,证明问题NP困难性,并提出动态规划算法.     

The off-line group seat reservation problem

In this paper we address the problem of assigning seats in a train for a group of people traveling together. We consider two variants of the problem. One is a special case of two-dimensional knapsack where we consider the train as having fixed size and the objective is to maximize the utilization of the seats in the train. The second is a special case of two-dimensional bin packing where all requests must be accommodated while trying to minimize the number of passenger cars needed. For both variants of the problem we present a number of bounds and develop exact algorithms. Computational results are presented for various instances based on realistic data, and from the packing literature adapted to the problems addressed.     

Minimizing the number of machines for minimum length schedules

In this paper, we present a new objective function for scheduling on parallel machines: minimizing the number of machines for schedules of minimum length. We study its complexity and we prove the NP-completeness of this problem, even if there is no precedences or for unitary execution times. We propose several polynomial algorithms for various particular cases.     

Breaks, cuts, and patterns

We generalize the concept of a break by considering pairs of arbitrary rounds. We show that a set of home-away patterns minimizing the number of generalized breaks cannot be found in polynomial time, unless P=NP. When all teams have the same break set, the decision version becomes easy; optimizing remains NP-hard.     

Comments on “A bicriteria flowshop scheduling problem with setup times”

The aim of this paper is to point out that the integer programming model proposed by Eren and Güner [T. Eren, E. Güner, A bicriteria flowshop scheduling problem with setup times, Appl. Math. Comput. 183 (2006) 1292-1300] is incorrect. We propose a new integer programming model for the same scheduling problem based on their model.     

Dynamic Scheduling on a Single Batch Processing Machine with Split Compatibility Graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. Jobs have release dates. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases. Relating scheduling theory and graph theory appears to be an interesting and important concept.     

On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem

In this paper a comparison is made between two decomposition techniques to solve a staff scheduling problem with column generation. In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes place on the activities that have to be performed by the staff members. The resulting master LP is respectively a set partitioning problem and a capacitated multi-commodity flow problem. Both approaches have been implemented in a branch-and-price algorithm. We show a trade-off between modeling power and computation times of both techniques.