Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines

DOI10.1016/j.ejor.2018.11.039zbMath1430.90275arXiv1808.10661OpenAlexW2949596481WikidataQ128816475 ScholiaQ128816475MaRDI QIDQ1711446

Manuel Iori, Mauro Dell'Amico, Arthur Kramer

Publication date: 18 January 2019

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.10661

zbMATH Keywords

schedulingparallel machinesweighted completion timearc-flow formulations

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time, An exact framework for the discrete parallel machine scheduling location problem, Arc-flow approach for single batch-processing machine scheduling, Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations, Unrelated parallel machine scheduling problem with special controllable processing times and setups, Dynamic scheduling of patients in emergency departments, Novel formulations and modeling enhancements for the dynamic berth allocation problem, Tool switching problems with tool order constraints, Arc flow formulations based on dynamic programming: theoretical foundations and applications, Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events, Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers, Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization, New exact techniques applied to a class of network flow formulations

Cites Work

• Unnamed Item
• Unnamed Item
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
• Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms
• Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations
• Weighted flow time bounds for scheduling identical processors
• A time indexed formulation of non-preemptive single machine scheduling problems
• Exact solution of bin-packing problems using column generation and branch-and-bound
• Scheduling identical parallel machines to minimize total weighted completion time
• Variable neighborhood search
• Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
• On the minimization of total weighted flow time with identical and uniform parallel machines
• LP models for bin packing and cutting stock problems
• GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times
• An exact extended formulation for the unrelated parallel machine total weighted completion time problem
• Parallel Machine Scheduling by Column Generation
• Convex quadratic and semidefinite programming relaxations in scheduling
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
• An improved branching scheme for the branch and bound procedure of schedulingnjobs onmparallel machines to minimize total weighted flowtime
• An Algorithm for Two-Dimensional Cutting Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Solving Parallel Machine Scheduling Problems by Column Generation
• Scheduling independent tasks to reduce mean finishing time
• The Schedule-Sequencing Problem
• The Meet-in-the-Middle Principle for Cutting and Packing Problems
• A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching
• Recursive Computational Procedure for Two-dimensional Stock Cutting