Tactical fixed job scheduling with spread-time constraints

DOI10.1016/J.COR.2014.02.001zbMATH Open1348.90339arXiv1402.1881OpenAlexW2170425807MaRDI QIDQ337014FDOQ337014

Bo Chen, Xiandong Zhang, Shuyu Zhou, Steef van de Velde

Publication date: 10 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Abstract: We address the tactical fixed job scheduling problem with spread-time constraints. In such a problem, there are a fixed number of classes of machines and a fixed number of groups of jobs. Jobs of the same group can only be processed by machines of a given set of classes. All jobs have their fixed start and end times. Each machine is associated with a cost according to its machine class. Machines have spread-time constraints, with which each machine is only available for $L$ consecutive time units from the start time of the earliest job assigned to it. The objective is to minimize the total cost of the machines used to process all the jobs. For this strongly NP-hard problem, we develop a branch-and-price algorithm, which solves instances with up to $300$ jobs, as compared with CPLEX, which cannot solve instances of $100$ jobs. We further investigate the influence of machine flexibility by computational experiments. Our results show that limited machine flexibility is sufficient in most situations.

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

Recommendations

• Spread time considerations in operational fixed job scheduling
• Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm
• A metaheuristic for the fixed job scheduling problem under spread time constraints
• The Fixed Job Schedule Problem with Spread-Time Constraints
• Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem

zbMATH Keywords

machine schedulingneighborhood searchbranch and priceflexible manufacturingspread-time constraint

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Integer programming (90C10)

Cites Work

• Branch-and-price: Column generation for solving huge integer programs
• Algorithms for the set covering problem
• An effective and simple heuristic for the set covering problem
• Scheduling trainees at a hospital department using a branch-and-price approach
• Interval scheduling: A survey
• Principles on the Benefits of Manufacturing Process Flexibility
• A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes
• Sequencing surgical cases in a day-care environment: an exact branch-and-price approach
• A Heuristic Method for the Set Covering Problem
• Exact and approximation algorithms for the operational fixed interval scheduling problem
• Working time constraints in operational fixed job scheduling
• A fixed job scheduling problem with machine-dependent job weights
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• A heuristic approach to the bus driver scheduling problem
• License class design: Complexity and algorithms
• A branch-and-price approach to \(p\)-median location problems
• Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm
• Spread time considerations in operational fixed job scheduling
• The Fixed Job Schedule Problem with Spread-Time Constraints
• An Optimal Solution for the Channel-Assignment Problem
• Approximation Algorithms for Fixed Job Schedule Problems
• Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem

Cited In (6)

• Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm
• Spread time considerations in operational fixed job scheduling
• The Fixed Job Schedule Problem with Spread-Time Constraints
• A Triplet-Based Exact Method for the Shift Minimisation Personnel Task Scheduling Problem
• Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times
• A Lagrangian relaxation algorithm for stochastic fixed interval scheduling problem with non-identical machines and job classes

Uses Software

• CPLEX

This page was built for publication: Tactical fixed job scheduling with spread-time constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q337014)