MB6 - Scheduling 2

The nodes and edges of an activity-on-node project network represent the project activities and prescribed precedence relations between these activities, respectively. Executing an activity requires a specific amount of time and resources of different types. The total consumption of each resource type must not exceed its capacity. We address the problem of allocating the resources to the activities over time to minimize time-to-market. We propose enhancing existing integer programming formulations by incorporating redundant constraints that evaluate the workload to be processed before each activity begins. Our computational analysis confirms that these constraints considerably improve the relaxation-based lower bound.

In seaports, tugboats play a critical role in assisting vessels with mooring and unmooring operations. However, conventional diesel tugboats generate substantial emissions during operations, prompting seaport operators to adopt electric alternatives. This paper studies the electric tugboat scheduling problem to simultaneously optimize the working and charging schedules of electric tugboats. The complexity of this problem arises from (i) time consistency constraints that require multiple electric tugboats to work simultaneously, (ii) service sequence constraints that establish precedence relationships between different tugging services, and (iii) nonlinear charging profiles of electric tugboats. The problem is formulated as a mixed-integer programming model. A tailored branch-and-price (BP) algorithm is developed to solve the problem efficiently. To handle the time consistency constraints and service sequence constraints that incur interdependence among schedules in the BP framework, two types of customized feasibility branching strategies are introduced. Additionally, the BP algorithm is further enhanced through an improved restricted master problem that provides tighter lower bounds and a customized bi-directional labeling algorithm that solves pricing subproblems. The performance and effectiveness of the proposed model and solution method are evaluated using numerical experiments based on operational data from a container terminal in Shanghai. The computational results demonstrate the effectiveness and efficiency of the proposed model and algorithm.

We study a multi-period scheduling and routing problem where agents must perform localized tasks, some requiring simultaneous presence. The objective is to maximize the number of completed tasks weighted by priority.
We develop an integer linear programming formulation based on time discretization and spatial aggregation, and derive simplified formulations using additional aggregation and relaxation to improve scalability.

We address large-scale flexible personnel scheduling in the retail sector by developing a decomposition method. Employees and jobs are partitioned into balanced clusters through an MILP-based clustering matheuristic, which ensures qualification compatibility between them. The resulting independent subproblems are then solved in parallel, significantly reducing computational time while maintaining high solution quality.
Keywords: Personnel scheduling, clustering matheuristic, mixed-integer linear programming