Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem

DOI10.1016/j.amc.2013.05.004zbMath1298.90044OpenAlexW2204206022WikidataQ57185628 ScholiaQ57185628MaRDI QIDQ470933

Chengbin Chu, Imed Kacem, Racem Mellouli, Chérif Sadfi

Publication date: 13 November 2014

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2013.05.004

zbMATH Keywords

schedulingparallel machinestotal weighted completion timeavailability constraint

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (1)

A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints

Cites Work

• Parallel machines scheduling with machine maintenance for minsum criteria
• Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
• Approximation schemes for parallel machine scheduling with availability constraints
• Parallel machines scheduling with nonsimultaneous machine available time
• Single machine flow-time scheduling with scheduled maintenance
• Minimizing the sum of job completion times on capacitated two-parallel machines
• Approximation algorithms for single machine scheduling with one unavailability period
• Exponential inapproximability and FPTAS for scheduling with availability constraints
• Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times
• Single machine flow-time scheduling with a single breakdown
• Weighted flow time bounds for scheduling identical processors
• A new dynamic programming algorithm for the parallel machines total weighted completion time problem
• Capacitated two-parallel machines scheduling to minimize sum of job completion times
• Scheduling identical parallel machines to minimize total weighted completion time
• Parallel-machine scheduling with non-simultaneous machine available time
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times
• Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period
• Machine scheduling with an availability constraint
• Parallel Machine Scheduling by Column Generation
• Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem
• A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous-casting production
• New Bounds for the Identical Parallel Processor Weighted Flow Time Problem
• Solving Parallel Machine Scheduling Problems by Column Generation
• Steel-making process scheduling using Lagrangian relaxation
• Scheduling independent tasks to reduce mean finishing time

This page was built for publication: Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem