NDLI: Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics

Content Provider	Springer Nature Link
Author	Wang, I Lin Wang, Yi Chi Chen, Chih Wei
Copyright Year	2012
Abstract	We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be calculated efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to effectively reduce the size of the MIP formulation. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job of the earliest due date to a machine with least recipe changeover (EDDLC) and try to re-optimize the solution by local search heuristics which involves interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually gives solutions very close to the exact optimum for smaller scheduling problems, and calculates good solutions for scheduling up to 200 jobs on 40 machines within 10 min.
Starting Page	343
Ending Page	366
Page Count	24
File Format	PDF
ISSN	19366582
Journal	Flexible Services and Manufacturing Journal
Volume Number	25
Issue Number	3
e-ISSN	19366590
Language	English
Publisher	Springer US
Publisher Date	2012-05-25
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Scheduling Mixed integer programming Dispatching rule Local search Manufacturing, Machines, Tools Production/Logistics/Supply Chain Operations Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Industrial and Manufacturing Engineering Management Science and Operations Research

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Scheduling movements in the network of an express service provider

A variable neighborhood descent heuristic for the problem of makespan minimisation on unrelated parallel machines with setup times

Modern heuristics for scheduling

New meta-heuristics for the resource-constrained project scheduling problem

Experimental evaluation of mixed integer programming models for the multi-port master bay plan problem

Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources

Scheduling job families on non-identical parallel machines with time constraints

A job-shop scheduling approach for optimising sugarcane rail operations

The resource-constrained project scheduling model of Bianco and Caramia: clarifications and an alternative model formulation

Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics

Similar Documents

Scheduling movements in the network of an express service provider

A variable neighborhood descent heuristic for the problem of makespan minimisation on unrelated parallel machines with setup times

Modern heuristics for scheduling

New meta-heuristics for the resource-constrained project scheduling problem

Experimental evaluation of mixed integer programming models for the multi-port master bay plan problem

Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources

Scheduling job families on non-identical parallel machines with time constraints

A job-shop scheduling approach for optimising sugarcane rail operations

The resource-constrained project scheduling model of Bianco and Caramia: clarifications and an alternative model formulation

Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics