I need assistance solving a Flexible Job-Shop Scheduling Problem (FJSP) with a simple dataset involving 3 jobs and 3 machines. The goal is to minimize total weighted tardiness. The dataset includes job details, operations, processing times for each machine, due dates, and weights.
Deliverables:
- A fully solved Excel file using Excel Solver.
- A fully solved Xpress file.
This is a straightforward task given the small dataset. My maximum budget for this task is $40, and I need the completed files within 24 hours. No need for steps, explanations, or screenshots—just the final files with the solutions implemented. All necessary details are provided in the attached files. Thank you!
2
Problem Tackled:
The paper addresses the Flexible Job-Shop Scheduling Problem (FJSP) with
sequencing flexibility. The goal is to minimize weighted tardiness in a scheduling
environment where operations can be performed by multiple machines, and the precedence
between tasks is represented by a Directed Acyclic Graph (DAG) instead of a linear
sequence.
Problem Background:
The Flexible Job-Shop Scheduling Problem (FJSP) is an extension of the classical
Job-Shop Scheduling Problem (JSP), which allows for operations to be performed on
multiple machines with varying capabilities. In real-world manufacturing environments,
companies often face complexities due to mixed usage of old and new machines with
different capabilities. This creates challenges in optimally scheduling job orders to reduce
costs, improve time-to-market, and maintain customer satisfaction.
The concept of sequencing flexibility arises when the precedence constraints
between operations are not strictly linear but can be represented by a DAG, providing
opportunities to optimize resource allocation dynamically based on machine availability.
Mathematical Formulation:
The Mixed Integer Linear Programming (MILP) formulation for the FJSP is presented
as follows:
• Objective Function: Minimize the total weighted tardiness:
Where:
o Wj is the weight of job j (importance).
o Tj is the tardiness of job j.
• Assumptions:
1. Machines:
▪ All machines are available at the start (time 0).
▪ Each machine can perform only one operation at a time (no multitasking).
2. Jobs:
▪ All jobs are ready for scheduling at time 0.
▪ Jobs cannot be interrupted once started (no preemption).
3. Simplifications:
▪ Transportation time between operations is ignored.
▪ Setup time for machines is negligible.
• Parameters
▪ n: Number of jobs.
▪ m: Number of machines.
3
▪ uj: Total number of operations in job j.
▪ Ojk: The kth operation of job j.
▪ Pijk: Processing time of operation Ojk on machine i.
▪ dj: Due date of job j.
▪ Wj: Weight (importance) of job j.
• Decision Variables
• Constraints:
1. Operation Assignment: Each operation must be assigned to exactly one machine:
2. Precedence Relationships: Completion of a preceding operation must occur before
the start of a succeeding operation:
3. Machine Exclusivity: No two operations can occupy the same machine at the same
time:
4. Completion Time and Tardiness:
4
5. Feasibility of Machine Assignments: Only assign machines that can perform the
operation:
